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

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

Источник

5 ответов

Решение

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

АСТ

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

Источник

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

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

Источник

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

Источник

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

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

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

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

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

Источник

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

Источник
Другие вопросы по тегам