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

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

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

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

2 54
abstract-syntax-tree

2 ответа:

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

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

42

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

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

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

пример:

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

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

   +
 |   |
 a   * 
    | |
    a b
3