WikiSort.ru - Не сортированное

Абстрактное синтаксическое дерево (АСД) — в информатике конечное помеченное ориентированное дерево, в котором внутренние вершины сопоставлены (помечены) с операторами языка программирования, а листья — с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы.

Синтаксические деревья используются в парсерах для промежуточного представления^[en] программы между деревом разбора^[en] (конкретным синтаксическим деревом) и структурой данных, которая затем используется в качестве внутреннего представления в компиляторе или интерпретаторе компьютерной программы для оптимизации и генерации кода. Возможные варианты подобных структур описываются абстрактным синтаксисом.

Особенности

Абстрактное синтаксическое дерево отличается от дерева разбора тем, что в нём отсутствуют узлы и рёбра для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером такого отсутствия являются группирующие скобки, так как в АСД группировка операндов явно задаётся структурой дерева.

Для языка, который описывается контекстно-свободной грамматикой, какими являются почти все языки программирования, создание абстрактного дерева в синтаксическом анализаторе является тривиальной задачей. Большинство правил в грамматике создают новую вершину, а символы в правиле становятся рёбрами. Правила, которые ничего не привносят в АСД (например, группирующие правила), просто заменяются в вершине одним из своих символов. Кроме того, анализатор может создать полное дерево разбора и затем пройти по нему, удаляя узлы и рёбра, которые не используются в абстрактном синтаксисе, для получения АСД.

См. также

• Абстрактный семантический граф
• Компоновщик
• Document Object Model
• Алгоритм сортировочной станции

Литература

• Статья «Исследование эволюции кода с использованием сравнения абстрактных синтаксических деревьев» Юлиана Нямтиу (англ. Iulian Neamtiu), Джеффри Фостера (англ. Jeffrey S. Foster) и Майкла Хикса (англ. Michael Hicks)
• Статья «Извлечение изменений: Поиск различий в деревьях для высокоточного определения изменений в исходном коде» Бита Флури (нем. Beat Fluri), Михаэля Вюрша (нем. Michael Würsch), Мартина Пинцгера (нем. Martin Pinzger) и Гаральда Галла (нем. Harald C. Gall) (прямая ссылка на PDF)
• Дипломная работа Михаэля Вюрша (нем. Michael Würsch) «Улучшение распознавания изменений в исходых кодах с помощью абстрактных синтаксических деревьев»
• Статья «Высокоточное определение изменений в исходном коде» Жана-Реми Фэлари (фр. Jean-Rémy Falleri), Флореаля Морэндата (фр. Floréal Morandat), Завьи Блена (фр. Xavier Blanc), Матиаса Мартинеса (фр. Matias Martinez) и Мартина Монпеуса (фр. Martin Monperrus)
• Статья «Мысли о абстрактном синтаксическом дереве в Visual C++» Джейсона Лукаса (англ. Jason Lucas)
• Учебное пособие «Стандарт метамодели абстрактных синтаксических деревьев»

Ссылки

• AST View, плагин для Eclipse показывает абстрактное синтаксическое дерево программ на языке Java;
• Полезная информация о представлении абстрактных синтаксических деревьев в Eclipse и манипулировании исходным кодом Java;
• Представление CAST;
• Abstract Syntax Tree Unparsing  (недоступная ссылка с 13-05-2013 [2078 дней] — история).

Это заготовка статьи о компьютерах. Вы можете помочь проекту, дополнив её. Это примечание по возможности следует заменить более точным.