compiler-construction - que - arbol sintactico compiladores

¿Cuál es la diferencia entre los árboles de análisis sintáctico y los árboles sintácticos abstractos?

Question

Encontré los dos términos en un libro de diseño de compilador, y me gustaría saber qué significa cada uno, y cómo son diferentes.

Busqué en Internet y encontré que los árboles de análisis también se llaman árboles de sintaxis de concreto (CST).

Answer 1

Aquí hay una explicación de los árboles de análisis sintáctico ( árboles de sintaxis concretos, CST) y los árboles de sintaxis abstracta (AST), en el contexto de la construcción del compilador. Son estructuras de datos similares, pero están construidas de manera diferente y se utilizan para diferentes tareas.

Árboles de Parse

Los árboles de análisis se generan normalmente como el siguiente paso después del análisis léxico (que convierte el código fuente en una serie de símbolos que se pueden ver como unidades significativas, en lugar de solo una secuencia de caracteres).

Son estructuras de datos en forma de árbol que muestran cómo una cadena de terminales de entrada (tokens de código fuente) ha sido generada por la gramática del idioma en cuestión. La raíz del árbol de análisis sintáctico es el símbolo más general de la gramática: el símbolo de inicio (por ejemplo, enunciado ), y los nodos interiores representan símbolos no terminales a los que se extiende el símbolo de inicio (puede incluir el símbolo de inicio), como expresión , declaración , término , llamada de función . Las hojas son los terminales de la gramática, los símbolos reales que aparecen como identificadores, palabras clave y constantes en el lenguaje / cadena de entrada, por ejemplo, para , 9 , si , etc.

Al analizar el compilador también se realizan varias comprobaciones para garantizar la corrección de la sintaxis, y los informes de errores de sintaxis se pueden incrustar en el código del analizador.

Se pueden usar para la traducción dirigida por sintaxis a través de definiciones dirigidas por sintaxis o esquemas de traducción, para tareas simples como convertir una expresión de infijo a una de postfijo.

Aquí hay una representación gráfica de un árbol de análisis sintáctico para la expresión 9 - 5 + 2 (observe la ubicación de los terminales en el árbol y los símbolos reales de la cadena de expresiones):

Árboles sintaxis abstractos

Los AST representan la estructura sintáctica del código . Los árboles de las construcciones de programación, como expresiones, declaraciones de control de flujo, etc., se agrupan en operadores (nodos interiores) y operandos (hojas). Por ejemplo, el árbol de sintaxis para la expresión i + 9 tendría el operador + como raíz, la variable i como el hijo izquierdo del operador y el número 9 como el hijo correcto.

La diferencia aquí es que los no terminales y terminales no juegan un rol, ya que los AST no tratan con gramáticas y generación de cadenas, sino que construyen constructos, y por lo tanto representan relaciones entre tales constructos, y no las formas en que son generados por una gramática .

Tenga en cuenta que los operadores mismos son constructos de programación en un idioma dado, y no tienen que ser operadores computacionales reales (como + es): for bucles también se tratarían de esta manera. Por ejemplo, podría tener un árbol de sintaxis tal como for [ expr, expr, expr, stmnt ] (representado en línea), donde for es un operador , y los elementos dentro de los corchetes son sus secundarios (que representan C for sintaxis) - también compuesto por operadores, etc.

Los AST también suelen ser generados por compiladores en la fase de análisis de sintaxis (análisis sintáctico), y se utilizan más adelante para el análisis semántico, la representación intermedia, la generación de código, etc.

Aquí hay una representación gráfica de un AST:

Answer 2

Encontré esto en la web, quizás útil:

Un árbol de análisis sintáctico es un registro de las reglas (y tokens) utilizados para hacer coincidir un texto de entrada, mientras que un árbol de sintaxis registra la estructura de la entrada y es insensible a la gramática que lo produjo. Tenga en cuenta que hay un número infinito de gramáticas para un solo idioma y, por lo tanto, cada gramática dará como resultado una forma de árbol de análisis diferente para una oración de entrada dada debido a todas las diferentes reglas intermedias. Un árbol de sintaxis abstracta es una forma intermedia muy superior precisamente debido a esta insensibilidad y porque resalta la estructura del lenguaje y no la gramática.

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.

EDITAR

Para una explicación más detallada, ver Compiladores y generadores de compilación por PD Terry pág. 23. Consulte también la página de inicio de los autores para ver más elementos, como el código fuente.

Answer 4

Un AST describe conceptualmente el código fuente, no necesita contener todos los elementos sintácticos necesarios para analizar un código fuente (llaves, palabras clave, paréntesis, etc.).

Un árbol Parse representa el código fuente más de cerca.

En una AST, el nodo para una instrucción IF podría contener solo tres hijos:

• Condición
• Si el caso
• Otro caso

Para un lenguaje tipo C, el Árbol de Parse necesitaría contener nodos para la palabra clave ''si'', paréntesis, llaves también.

Answer 5

Wikipedia dice

Los árboles Parse reflejan concretamente la sintaxis del lenguaje de entrada, haciéndolos distintos de los árboles sintácticos abstractos utilizados en la programación de computadoras.

Una respuesta en Quora dice

Un árbol de análisis sintáctico es un registro de las reglas (y tokens) utilizados para hacer coincidir un texto de entrada, mientras que un árbol de sintaxis registra la estructura de la entrada y es insensible a la gramática que lo produjo.

Combinando las dos definiciones anteriores,

Un Abstract Syntax Tree describe el árbol de análisis sintáctico lógicamente. No es necesario que contenga todas las construcciones sintácticas necesarias para analizar un código fuente (espacios en blanco, llaves, palabras clave, paréntesis, etc.). Es por eso que Parse Tree también se llama Concrete Syntax Tree mientras que AST se llama Syntax Tree . El resultado del analizador de sintaxis es, por lo tanto, el árbol de sintaxis en realidad.