В чем разница между деревом разбора и AST?

Question

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

Answer 1

Это основано на грамматике выражений Терренса Парр.

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

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(); } ;

Input

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

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

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

АСТ

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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