В чем разница между parse tree и AST?

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

5 76
terminology compiler-construction abstract-syntax-tree compiler-theory parse-tree

5 ответов:

это основано на Выражение Оценщика грамматика Терренса Парра.

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

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)

Дерева

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

Parse Tree

АСТ

АСТ является абстрактным представление входных данных. Обратите внимание, что parens не присутствуют в AST, потому что ассоциации выводятся из древовидной структуры.

AST

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

82

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

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

16

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

9

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

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

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

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

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

3

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

1