Как построить абстрактное синтаксическое дерево

У меня есть общее представление о том, что такое AST, но я хочу знать, как его построить.

Если вам дана грамматика и дерево разбора, как вы строите AST?

Как вы это делаете, если вам дают грамматику и выражение?

Ответы

Ответ 1

Ну, во-первых, грамматика используется для построения дерева разбора из выражения. Поэтому, если у вас уже есть дерево разбора, вам не нужна грамматика.

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

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

Таким образом, выражение 1 + 2*(3+4) может быть разделено на список токенов следующим образом:

1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen

Первый столбец - это фактическое текстовое значение. Второй представляет тип токена. Эти жетоны передаются в парсер, который построен из вашей грамматики и распознает маркеры и строит дерево разбора.

Итак, как написать лексический токенизатор и фактический синтаксический анализатор? Вы можете бросить свои руки вручную. Или, чаще, используйте генератор синтаксического анализатора, такой как coco или antlr или lex/yacc. Эти инструменты используют описание вашей грамматики и генерируют код для токензира и парсера. (Генераторы кода существуют для большинства популярных языков и некоторых непопулярных.)

Как вы строите свой парсер сильно зависит от того, какой язык вы используете. Как вы могли бы написать парсер в Haskell, полностью отличается от того, как вы, скажем, C.

Вот учебник, в котором показано, как создать собственную рекурсивную синтаксический анализатор.
Coco - генератор парсера для разных языков, что также поставляется с документацией о том, как начать работу.
Если Python ваша вещь, то pyparsing, возможно, для вас.

Ответ 2

Я отвечу на это с общей точки зрения, не пытаясь говорить о лексерах и парсерах.

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

АСТ не содержит никаких нетерминальных символов. Он содержит только символы.

Пример:

E | E + T | | T M * M | | | M a b | b

Это очень быстрая версия показа a+a*b. Обратите внимание, как интерпретируется дерево абстрактного синтаксиса, зависит от приоритета дерева, какого типа обхода вы делаете (в порядке, предзаказ, пост-порядок). Это будет общая функция, которую вы кодируете в свое дерево поиска. Однако, в общем, AST для этого дерева разбора может выглядеть так:

+ | | a * | | a b