compiler construction - sintactico - ¿Cuál es la diferencia entre el árbol de análisis sintáctico y AST?

arbol sintactico compiladores

Question

¿Se generan por diferentes fases de un proceso de compilación? ¿O son solo nombres diferentes para la misma cosa?

Answer 1

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

Answer 2

En el árbol sintáctico, los nodos interiores no son terminales, las hojas son terminales. En la sintaxis, los nodos interiores del árbol son operator, las leaves son operandos.

Answer 3

Esto se basa en la gramática Evaluador de expresiones de Terrence Parr.

La gramática para 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)

Árbol Parse

El árbol de análisis sintáctico es una representación concreta de la entrada. El árbol de análisis conserva toda la información de la entrada. Los cuadros vacíos representan espacios en blanco, es decir, el final de la línea.

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 del árbol.

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

Answer 4

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

Encontré esta page que intenta resolver esta pregunta exacta.

Answer 5

Tome la asignación pascal Edad: = 42;

El árbol de sintaxis se vería exactamente como el código fuente. A continuación, coloco 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 puede ejecutar la tarea.

También tenga en cuenta que la sintaxis pascal desaparece. Por lo tanto, es posible tener más de un lenguaje generando el mismo AST. Esto es útil para motores de script de lenguaje cruzado.