В чем разница между деревом синтаксического анализа и AST?

94

Они генерируются на разных этапах процесса компиляции? Или это просто разные названия одного и того же?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Томсон
источник
Дерево синтаксического разбора является результатом вашей грамматики с ее артефактами (вы можете написать бесконечное количество грамматик для одного и того же языка), AST сокращает дерево синтаксического анализа как можно ближе к языку. Несколько грамматик для одного и того же языка дадут разные деревья синтаксического анализа, но должны привести к одному и тому же AST. (вы также можете сократить разные скрипты (разные деревья синтаксического анализа из одной грамматики) до одного и того же AST)
Guillaume86
1
В этом SO-ответе подробно обсуждается разница: stackoverflow.com/a/1916687/120163
Ира Бакстер,
1
Возможный дубликат В чем разница между деревьями синтаксического анализа и абстрактными синтаксическими деревьями?
curiousdannii

Ответы:

98

Это основано на грамматике Expression Evaluator Терренса Парра.

Грамматика для этого примера:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

Ввод

x=1
y=2
3*(x+y)

Дерево разбора

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

Дерево разбора

AST

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

AST

Для более подробного объяснения см. Компиляторы и генераторы компиляторов стр. 23
или абстрактные синтаксические деревья на стр. 21 в синтаксисе и семантике языков программирования

Гай Кодер
источник
5
Как вы получаете AST из дерева синтаксического анализа? Каков метод упрощения дерева синтаксического анализа до AST?
CMCDragonkai
3
Не существует специального алгоритма для получения AST из дерева синтаксического анализа. То, что входит в AST, - это скорее личное предпочтение, но оно должно содержать достаточно информации для выполнения задачи. Я исключил пары из AST с помощью ANTLR ! оператор в грамматике , так как они не нужны, но по умолчанию ANTLR бы включили их. Я думаю, что дерево синтаксического анализа дает вам все, независимо от того, нужно оно вам или нет, а AST - как минимум. Помните, что вы будете много пересекать деревья, поэтому размер имеет значение.
Guy Coder
2
Вы имеете в виду, например, CST (конкретное дерево синтаксиса) или AST (абстрактное дерево синтаксиса)?
CMCDragonkai 07
Семантические действия / правила, встроенные в файлы синтаксиса синтаксического анализатора или генератора синтаксического анализатора, являются обычным способом семантического анализа и создания AST, в то время как дерево синтаксического анализа редко, если оно когда-либо создается или используется пользовательским кодом, за исключением, возможно, проверки правильности синтаксического анализатора.
Интересно: абстрактный семантический граф
Guy Coder
16

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

Я нашел эту страницу, которая пытается решить именно этот вопрос.

Кен Уэйн ВандерЛинде
источник
11

Книга DSL Мартина Фаулера прекрасно объясняет это. AST содержит только все `` полезные '' элементы, которые будут использоваться для дальнейшей обработки, в то время как дерево синтаксического анализа содержит все артефакты (пробелы, скобки, ...) из исходного документа, который вы анализируете.

Вим Деблаув
источник
4

Возьмите задание на паскаль Возраст: = 42;

Синтаксическое дерево будет выглядеть так же, как исходный код. Ниже я заключил узлы в скобки. [Возраст] [: =] [42] [;]

Абстрактное дерево будет выглядеть так [=] [Возраст] [42]

Назначение становится узлом с 2 элементами, возрастом и 42. Идея состоит в том, что вы можете выполнить задание.

Также обратите внимание, что синтаксис паскаль исчезает. Таким образом, один и тот же AST может генерироваться более чем одним языком. Это полезно для межъязыковых скриптовых машин.

Уильям Эгге
источник
1

В дереве разбора внутренние узлы нетерминальные, листья терминальные. В синтаксическом дереве внутренние узлы являются операторами, а листья - операндами.

Рошани Патель
источник