¿Cuál es la diferencia entre el árbol de análisis y el AST?

90

¿Son generados por diferentes fases de un proceso de compilación? ¿O son simplemente diferentes nombres para lo mismo?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Thomson
fuente
Parse Tree es el resultado de su gramática con sus artefactos (puede escribir una infinidad de gramáticas para el mismo idioma), un AST reduce el Parse Tree lo más cerca posible del idioma. Varias gramáticas para el mismo idioma darán diferentes árboles de análisis, pero deberían dar como resultado el mismo AST. (también puede reducir diferentes scripts (diferentes árboles de análisis de la misma gramática) al mismo AST)
Guillaume86
1
Esta respuesta SO discute la diferencia en detalle: stackoverflow.com/a/1916687/120163
Ira Baxter
1
Posible duplicado de ¿Cuál es la diferencia entre árboles de análisis y árboles de sintaxis abstracta?
Curiousdannii

Respuestas:

95

Esto se basa en la gramática Expression Evaluator de Terrence Parr.

La gramática de este ejemplo:

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)

Parse árbol

El árbol de análisis es una representación concreta de la entrada. El árbol de análisis conserva toda la información de la entrada. Las casillas vacías representan espacios en blanco, es decir, final de línea.

Parse árbol

AST

El AST es una representación abstracta de la entrada. Observe que los parens no están presentes en el AST porque las asociaciones son derivables de la estructura de árbol.

AST

Para obtener una explicación más detallada, consulte Compiladores y generadores de compiladores, pág. 23
o Árboles de sintaxis abstracta en la pág. 21 en sintaxis y semántica de lenguajes de programación

Guy Coder
fuente
5
¿Cómo se deriva el AST del árbol de análisis? ¿Cuál es el método para simplificar un árbol de análisis sintáctico en un AST?
CMCDragonkai
3
No existe un algoritmo específico para derivar el AST del árbol de análisis. Lo que entra en el AST es más una preferencia personal, pero debe contener suficiente información para realizar la tarea. ¡Excluí los parens del AST usando el ANTLR ! operador en la gramática ya que no son necesarios, pero por defecto ANTLR los habría incluido. Creo que el árbol de análisis te da todo lo que necesites o no, y el AST te da lo mínimo. Recuerda que atravesarás mucho los árboles, por lo que el tamaño importa.
Guy Coder
2
¿Te refieres a CST (árbol de sintaxis concreta) vs AST (árbol de sintaxis abstracta)?
CMCDragonkai
Las acciones / reglas semánticas incrustadas en los archivos de sintaxis de un analizador o generador de analizador son la forma habitual de análisis semántico y de creación de un AST, mientras que el árbol de análisis sintáctico rara vez, si es que alguna vez lo construye o utiliza el código de usuario, excepto quizás para la verificación de la corrección del analizador.
De interés: Gráfico semántico abstracto
Guy Coder
16

Por lo que entiendo, el AST se enfoca más en las relaciones abstractas entre los componentes del código fuente, mientras que el árbol de análisis se enfoca en la implementación real de la gramática utilizada por el lenguaje, incluidos los detalles delicados. Definitivamente no son lo mismo, ya que otro término para "árbol de análisis sintáctico" es "árbol de sintaxis concreto".

Encontré esta página que intenta resolver esta pregunta exacta.

Ken Wayne Vander como Linde
fuente
11

El libro DSL de Martin Fowler lo explica muy bien. El AST solo contiene todos los elementos 'útiles' que se utilizarán para el procesamiento posterior, mientras que el árbol de análisis contiene todos los artefactos (espacios, corchetes, ...) del documento original que analiza.

Wim Deblauwe
fuente
4

Tome la asignación de pascal Edad: = 42;

El árbol de sintaxis se parecería al código fuente. A continuación, pongo corchetes alrededor de los nodos. [Edad] [: =] [42] [;]

Un árbol abstracto se vería así [=] [Edad] [42]

La asignación se convierte en un nodo con 2 elementos, Edad y 42. La idea es que puedas ejecutar la asignación.

También tenga en cuenta que la sintaxis de pascal desaparece. Por tanto, es posible que más de un idioma genere el mismo AST. Esto es útil para motores de secuencia de comandos en varios idiomas.

William Egge
fuente
1

En el interior del árbol de análisis, los nodos no son terminales, las hojas son terminales. En el árbol de sintaxis, los nodos interiores son operadores, las hojas son operandos.

Roshani Patel
fuente