Qual é a diferença entre a árvore de análise e AST?

90

Eles são gerados por diferentes fases de um processo de compilação? Ou são apenas nomes diferentes para a mesma coisa?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Thomson
fonte
O Parse Tree é o resultado da sua gramática com seus artefatos (você pode escrever uma infinidade de gramáticas para o mesmo idioma), um AST reduz o Parse Tree o mais próximo possível do idioma. Várias gramáticas para o mesmo idioma fornecerão diferentes árvores de análise, mas devem resultar no mesmo AST. (você também pode reduzir scripts diferentes (árvores de análise diferentes da mesma gramática) para o mesmo AST)
Guillaume86
1
Esta resposta do SO discute a diferença em detalhes: stackoverflow.com/a/1916687/120163
Ira Baxter
1
Possível duplicata de Qual é a diferença entre árvores de análise e árvores de sintaxe abstrata?
curiousdannii

Respostas:

95

Isso se baseia na gramática do Expression Evaluator, de Terrence Parr.

A gramática para este exemplo:

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

Entrada

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

Analisar árvore

A árvore de análise é uma representação concreta da entrada. A árvore de análise retém todas as informações da entrada. As caixas vazias representam espaços em branco, ou seja, fim de linha.

Analisar árvore

AST

O AST é uma representação abstrata da entrada. Observe que os parênteses não estão presentes no AST porque as associações são deriváveis ​​da estrutura em árvore.

AST

Para uma explicação mais detalhada, consulte Compiladores e geradores de compiladores na pág. 23
ou Árvores de sintaxe abstrata na pág. 21 em Sintaxe e Semântica de Linguagens de Programação

Guy Coder
fonte
5
Como você obtém o AST da árvore de análise? Qual é o método de simplificar uma árvore de análise em um AST?
CMCDragonkai
3
Não há algoritmo específico para derivar o AST da árvore de análise. O que entra no AST é mais uma preferência pessoal, mas deve conter informações suficientes para realizar a tarefa. Excluí os parênteses do AST usando o ANTLR ! operador na gramática, uma vez que não são necessários, mas por padrão o ANTLR os teria incluído. Acho que a árvore de análise fornece tudo, quer você precise ou não, e a AST, fornecendo o mínimo necessário. Lembre-se de que você vai atravessar muito as árvores, então o tamanho é importante.
Guy Coder
2
Você quer dizer como CST (árvore de sintaxe concreta) vs AST (árvore de sintaxe abstrata)?
CMCDragonkai
Ações / regras semânticas embutidas em arquivos de sintaxe de um analisador ou gerador de analisador são a forma usual de análise semântica e criação de um AST, enquanto a árvore de análise é raramente, ou nunca, construída ou usada pelo código do usuário, exceto talvez para verificação de exatidão do analisador.
De interesse: Gráfico semântico abstrato
Guy Coder
16

Pelo que entendi, o AST se concentra mais nas relações abstratas entre os componentes do código-fonte, enquanto a árvore de análise se concentra na implementação real da gramática utilizada pela linguagem, incluindo os detalhes minuciosos. Eles definitivamente não são os mesmos, já que outro termo para "árvore de análise" é "árvore de sintaxe concreta".

Encontrei esta página que tenta resolver esta questão exata.

Ken Wayne VanderLinde
fonte
11

O livro DSL de Martin Fowler explica isso muito bem. O AST contém apenas todos os elementos 'úteis' que serão usados ​​para processamento posterior, enquanto a árvore de análise contém todos os artefatos (espaços, colchetes, ...) do documento original que você analisa

Wim Deblauwe
fonte
4

Faça a atribuição pascal Idade: = 42;

A árvore de sintaxe seria semelhante ao código-fonte. Abaixo estou colocando colchetes ao redor dos nós. [Idade] [: =] [42] [;]

Uma árvore abstrata ficaria assim [=] [Idade] [42]

A atribuição se torna um nó com 2 elementos, Idade e 42. A ideia é que você possa executar a atribuição.

Observe também que a sintaxe pascal desaparece. Assim, é possível que mais de um idioma gere o mesmo AST. Isso é útil para motores de script entre idiomas.

William Egge
fonte
1

Na árvore de análise, os nós internos são não terminais, as folhas são terminais. Na árvore de sintaxe, os nós internos são operadores e as folhas são operandos.

Roshani Patel
fonte