¿Qué es un analizador de árbol en antlr y estoy obligado a escribir uno?

StackOverflow https://stackoverflow.com/questions/697755

Pregunta

Estoy escribiendo un analizador léxico / analizador para un pequeño subconjunto de C en antlr que se ejecuta en un entorno Java. Soy nuevo en el mundo de las gramáticas de las lenguas y en muchos de los tutoriales ANTLR, crean un AST - Árbol de sintaxis abstracta, ¿estoy obligado a crear uno y por qué

?
¿Fue útil?

Solución 2

esta respuesta a la pregunta sobre jGuru escrito por Terence Parr, que creó antlr. Copié esta explicación de la página enlazada aquí :

Sólo sencilla, llamados traducciones de sintaxis dirigida se puede hacer con las acciones dentro del analizador. Este tipo de traducciones sólo pueden escupir construcciones que son funciones de la información ya vistos en ese punto en el análisis. analizadores de árboles le permiten caminar una forma intermedia y manipular ese árbol, transformándose gradualmente durante varias fases de traducción a una forma final que puede ser fácilmente impreso de vuelta como la nueva traducción.

Imagine un problema de traducción simple en el que desea imprimir una página html cuyo título es "hay n elementos" donde n es el número de identificadores que se encuentran en el flujo de entrada. Los identificadores deben imprimirse después del título como este: 

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

desde la entrada 

Dog
Cat
Velociraptor

Así que con acciones simples en su gramática cómo se puede calcular el título? No se puede sin leer toda la entrada. Ok, por lo que ahora sabemos que necesitamos una forma intermedia. Lo mejor es por lo general un AST que he encontrado ya que registra la estructura de entrada. En este caso, es sólo una lista pero demuestra mi punto.

Ok, ahora se sabe que un árbol es una buena cosa para nada más que simples traducciones. Dado un AST, ¿cómo se obtiene la salida de ella? Imagínese árboles de expresión simples. Una forma es hacer que los nodos en las clases específicas de árboles como PlusNode, IntegerNode y así sucesivamente. Luego le preguntas a cada nodo para imprimir por sí mismo. Para la entrada, 3 + 4 que tendría árbol:

+ | 3 - 4

y clases 

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

Dado un árbol de expresión, se puede traducir volver al texto con t.toString (). Entonces, ¿qué hay de malo en esto? Parece que funciona muy bien, ¿verdad? Parece que funciona bien en este caso porque es simple, pero argumentan que, incluso para este sencillo ejemplo, las gramáticas de árboles son más legibles y son descripciones de exactamente lo que codificado en el PlusNode.toString formalizadas (). 

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

Tenga en cuenta que la clase específica ( "AST heterogéneo") enfoque codifica realmente un analizador sintáctico descendente recursivo completo para # (+ INT INT) a mano en toString (). A medida que la gente generador de análisis, esto debería hacer que usted está nervioso. ;)

La principal debilidad del enfoque AST heterogénea es que no se puede acceder cómodamente a la información de contexto. En un analizador sintáctico descendente recursivo, el contexto es de fácil acceso, ya que se puede pasar como parámetro. También sabe exactamente cuál es la norma, que puede invocar otra norma (por ejemplo, esta expresión es una condición WHILE o una condición SI?) Mirando a la gramática. La clase PlusNode anteriormente existe en un mundo distante, aislado donde no tiene idea de quién va a invocar el método toString () es. Peor aún, el programador no puede decir en qué contexto, se invocará mediante la lectura de la misma.

En resumen, la adición de acciones para su analizador de entrada funciona para textos muy sencillos donde:

  1. el orden de los constructos de salida es el mismo que el orden de entrada
  2. todas las construcciones se pueden generar a partir de la información analizada hasta el punto cuando se necesita para escupir a cabo

Más allá de esto, tendrá una forma intermedia - la AST es la mejor forma general. El uso de una gramática para describir la estructura de la AST es análogo al uso de una gramática para analizar el texto de entrada. descripciones formalizado en un lenguaje de alto nivel de dominio específico como antlr son mejores que entregar analizadores codificados. Acciones dentro de una gramática de árbol tienen contexto muy claras y pueden acceder convenientemente información pasó de rlues que invocan. Las traducciones que manipulan el árbol de paso múltiple traducciones son también mucho más fácil el uso de una gramática árbol.

Otros consejos

Creación de un AST con antlr se incorpora en la gramática. Usted no tiene que hacer esto, pero es una herramienta muy buena para los requisitos más complicados. Se trata de un tutorial sobre la construcción del árbol se puede utilizar.

Básicamente, con antlr cuando se está analizado la fuente, usted tiene algunas opciones. Puede generar código o un AST usando reglas de reescritura en su gramática. Un AST es básicamente una representación en memoria de su origen. A partir de ahí, hay mucho que puede hacer.

Hay mucho que Antlr. Si no lo ha hecho, le recomiendo conseguir el libro .

Creo que la creación de la AST es opcional. El de sintaxis abstracta árbol es útil para el tratamiento posterior como análisis semántico del programa analizado.

Sólo usted puede decidir si necesita crear una. Si su único objetivo es la validación sintáctica, entonces no es necesario generar una. En javacc (similar a antlr) hay un utilidad llamada JJTree que permite la generación de la AST. Así que me imagino que esto es opcional en antlr también.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top