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

Question

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

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

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

Answer 1

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

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

Чтобы построить дерево разбора из грамматики и выражения, сначала нужно преобразовать грамматику в рабочий код. Как правило, вы должны разделить работу на токенизатор, который разбивает входной поток, представляющий выражение, в список токенов, и парсер, который принимает список токенов и создает из него дерево синтаксиса \ 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 полностью отличается от того, как вы бы, скажем, С.

• Вот учебник, который показывает вам, как build your own recursive descent parser.

• Coco является генератором синтаксиса для различных языков, который также содержит с документацией о том, как начать работу.

• Если ваша вещь Python, то pyparsing может быть для вас.

Answer 2

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

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

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

Пример:

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

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

+ 
| | 
a * 
    | | 
    a b