Какая разница между деревом разбора и АСТ?

Ответ 1

Это основано на грамматике 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 - это абстрактное представление ввода. Обратите внимание, что в АСТ нет парен, потому что ассоциации выводятся из древовидной структуры.

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

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

Также обратите внимание, что синтаксис pascal исчезает. Таким образом, возможно, что более одного языка генерирует один и тот же АСТ. Это полезно для двигателей с несколькими языками script.

Ответ 5

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