Абстрактное синтаксическое дерево

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

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

Особенности

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

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

См. также

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

Литература

• Статья «[doi.acm.org/10.1145/1083142.1083143 Исследование эволюции кода с использованием сравнения абстрактных синтаксических деревьев]» Юлиана Немтью (англ. Iulian Neamtiu), Джеффри Фостера (англ. Jeffrey S. Foster) и Михаэля Хикса (англ. Michael Hicks)
• Статья «[seal.ifi.uzh.ch/fileadmin/User_Filemount/Publications/fluri-changedistilling.pdf Извлечение изменений: Поиск различий в деревьях для высокоточного определения изменений в исходном коде]» Бита Флури (англ. Beat Fluri), Михаэля Вурщ (англ. Michael Würsch), Мартина Пинцгера (англ. Martin Pinzger) и Гаральда Галла (англ. Harald C. Gall)
• Дипломная работа Михаэля Вурща (англ. Michael Würsch) «[seal.ifi.unizh.ch/137/ Улучшение распознавания изменений в исходых кодах с помощью абстрактных синтаксических деревьев]»
• Статья «[blogs.msdn.com/vcblog/archive/2006/08/16/702823.aspx Мысли о абстрактном синтаксическом дереве в Visual C++]» Джейсона Лукаса (англ. Jason Lucas)
• Учебное пособие «[www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf Стандарт метамодели абстрактных синтаксических деревьев]»

Ссылки

• [www.eclipse.org/jdt/ui/astview/index.php AST View], плагин для Eclipse показывает абстрактное синтаксическое дерево программ на языке Java;
• [www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html Полезная информация о представлении абстрактных синтаксических деревьев в Eclipse и манипулировании исходным кодом Java];
• [www.cs.utah.edu/flux/flick/current/doc/guts/gutsch6.html Представление CAST];
• [eli-project.sourceforge.net/elionline4.4/idem_2.html Abstract Syntax Tree Unparsing] (недоступная ссылка с 13-05-2013 (4004 дня) — история).