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

Абстрактное синтаксическое дерево для алгоритма Евклида, приведённого ниже:

while b ≠ 0

if a > b

a := a − b

else

b := b − a

return a

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

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

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

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

Литература

• Iulian Neamtiu, Jeffrey S. Foster, Michael Hicks. Understanding source code evolution using abstract syntax tree matching (англ.) // Proceedings of the 2005 international workshop on Mining software repositories (MSR ’05). — 2005. — doi:10.1145/1083142.1083143.
• Beat Fluri, Michael Würsch, Martin Pinzger, Harald C. Gall. Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction (англ.) // IEEE Transactions on Software Engineering. — 2007. — Vol. 33, no. 11. — P. 725—743.
• Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, Martin Monperrus. Fine-grained and Accurate Source Code Differencing (англ.) // Proceedings of the International Conference on Automated Software Engineering. — 2014. — P. 313—324. — doi:10.1145/2642937.2642982.

Ссылки

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