Определение

Начнём сразу с примера.

Возьмём арифметическое выражение 1 + (2 * 3).

Абстрактным синтаксическим деревом (abstract syntax tree, AST) для него будет следующее:

Абстрактное синтаксическое дерево выражения 1 + (2 * 3).

Объясним словосочетание «абстрактное синтаксическое дерево» по частям.

«Дерево» — см. рисунок.

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

«Абстрактное» — дерево «очищено» от вспомогательных символов, использующихся в исходной строке (для данного примера  — отсутствуют скобки).

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

AST и естественный язык

Несколько упрощая, абстрактным синтаксическим деревом предложения

Мама мыла раму

является

«Абстрактное синтаксическое дерево» предложения на русском языке

Предикат (то есть глагол) стоит в узле. Его референты (в математике мы их называли «операнды», а в лингвистике «актанты»: объект и субъект) отходят от предиката листьями.

AST vs parse tree

Важно не путать «абстрактное синтаксическое дерево» и «дерево парсинга» (parse tree).

Собственно, у них одно отличие: дерево парсинга «конкретно», то есть содержит все вспомогательные языковые средства.

А абстрактное (= очищенное) синтаксическое дерево содержит то и только то, что существенно для понимания предложения (в языках программирования под «пониманием» имеется в виду вычисление/выполнение).

Например, в языке Ruby можно получить «parse tree» с помощью следующей команды:

require 'ripper'

code = "1 + (2 * 3)"
pp Ripper.sexp(code)

На выходе мы получим вот такой массив, являющийся префиксным выражением (S-expression):

[:program,
 [[:binary,
   [:@int, "1", [1, 0]],
   :+,
   [:paren, [[:binary, [:@int, "2", [1, 5]], :*, [:@int, "3", [1, 9]]]]]]]]

В виде дерева вот как выглядит:

Ruby-специфичный parse tree выражения 1 + (2 * 3).

Нас здесь интересует следующее: в parse tree нашёл отражение тот факт, что (2 * 3) была взята в скобки (получился узел :paren).

Нужна ли эта информация для вычисления выражения? Нет, не нужна, так как в дереве и так видно, что первым выполняется умножение (оно стоит на более низком уровне дерева), а следом сложение (которое использует в правой ветке результат умножения).

Логика такая: детали языковых средств записи попали в дерево. Значит, это не «абстрактное» дерево. Значит, это не AST, а parse tree.

На AST смотри выше.

Как изобразить AST

Предложение «мама мыла раму» можно написать мелом на доске, можно печатным текстом в книге, можно ручкой в тетради. Это будет всё то же предложение.

Точно также и AST можно изобразить в виде рисунка (как здесь), можно записать на бумаге (или в тексте) линейно как префиксное выражение, а можно сохранить на жёсткий диск в виде последовательности байтов.

А можно в виде структуры на каком-нибудь языке программирования, например:

["мыла", ["мама", "раму"]]

Концептуальной разницы это не создаёт. Без ограничения общности мы все такие варианты будем назвывать «абстрактными синтаксическими деревьями», хотя это может быть не буквальный рисунок дерева, а массив (структура данных внутри языка разработки парсера), линейный текст, либо последовательность зарядов электронов на SSD-диске.

AST и парсинг

На этапе парсинга наша задача — получить из выражения (из программы) именно AST (для дальнейшей обработки и/или вычисления).

При этом алгоритмы парсинга и средства автогенерации парсеров создают, изначально, parse tree. Получается, возникает дополнительная задача специально отметить те узлы parse tree, которые должны попасть в AST.

Рассмотрим на примере. Пусть дана следующая грамматика:

<function_call> ::=
  <variable> '(' <arguments_or_nothing> ')'

<arguments_or_nothing> ::= <arguments> | ε

<arguments> ::=
  number ',' <arguments>
  | number

<variable> ::= string

Где string это строка, соответствующая регулярному выражению [a-z].

Данная грамматика соответствует строкам типа f(1), multiply(2,5), now() и т. п.

Рассмотрим строку multiply(2,5). Parse tree, соответствующее этой строке, следующее:

Дерево парсинга для строки “multiply(2,5)” в заданной грамматике

Итак, дерево парсинга (parse tree) однозначно отображает, какие правила вывода и в каком порядки были применены и каким терминалам исходной строки сопоставлены.

В методе рекурсивного нисходящего парсинга синие узлы соответствуют вызову функции, обрабатывающей указанный нетерминал, а белые узлы — «снятию» (shift) символа с входной ленты. Обход дерева сверху вниз и слева направо соответствует порядку операций при данном методе парсинге.

Возникает вопрос: нафига козе боян а зачем нам такое избыточное количество информации, все «потроха» синтаксического разбора, если мы хотим просто «понять», что видим перед собой «вызов функции со списком таких-то аргументов»?

Мы хотим получить AST. Например, что-то вроде такого:

Абстрактное синтаксическое дерево для строки “multiply(2,5)” выбранной структуры

Отметим, что структуру AST разработчик языка выбирает исходя из соображений облегчения дальнейшего выполнения кода, «зафиксированного» в виде AST.

Трансформация parse tree в AST

Для преобразования parse tree в некий заранее спроектированный вариант AST требуется сделать ряд типовых операций:

• переименовать некоторые узлы;
• удалить «служебные» узлы;
• свернуть порождённое рекурсией поддерево <arguments> в линейный список/массив.

Рассмотрим, для примера, следующую грамматику (упрощённый оператор присвоения):

<assignment> ::= letter "=" number

Где letter — буква латинского алфавита, number — число.

Данная грамматика будет соответствовать строкам типа x=5, y=21 и т. д.

Предположим, что в нашем варианте AST мы для каждого присвоения хотим сохранять массив вида ["x", 5], ["y", 21] и т. д. (В данном случае мы, говоря AST, имеем в виду в первую очередь внутреннюю структуру данных языка разработки, а не её графическое изображение.)

Тогда мы можем добавить код (в фигурных скобках) к данному правилу в следующей манере:

<assigment> ::= letter "=" number ; { [$1, $3] }

В системах автоматической генерации парсеров подобный код даёт следующее указанию парсеру: «когда обработаешь данное правило вывода (построишь соответствующее ему parse tree), возьми первый символ (letter) и третий (number) и выполни с ними указанный код (объедини в массив из двух элементов) — это и будет AST».