java - sintactico - Construyendo un árbol de sintaxis abstracta con una lista de Tokens

arbol sintactico java

Question

Quiero construir un AST a partir de una lista de tokens. Estoy creando un lenguaje de scripting y ya hice la parte del análisis léxico, pero no tengo idea de cómo crear un AST. Entonces la pregunta es, ¿cómo tomo algo como esto?

WORD, int
WORD, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

y convertirlo en un árbol de sintaxis abstracta? Preferiblemente, me gustaría hacerlo sin una biblioteca como ANTLR o lo que sea, prefiero intentar hacerlo desde cero. Sin embargo, si es una tarea realmente compleja, no me importa usar una biblioteca :) Gracias

Answer 1

El truco fundamental es reconocer que el análisis, sin embargo realizado, ocurre en pasos incrementales, incluida la lectura de las fichas una por una.

En cada paso incremental, hay una oportunidad de construir parte del AST combinando fragmentos de AST construidos por otros pasos incrementales. Esta es una idea recursiva, y se basa en la construcción de nodos de hojas AST para tokens a medida que se escanean. Esta idea básica ocurre en casi todos los analizadores de creación de AST.

Si uno construye un analizador de descenso recursivo, uno construye en efecto un sistema de cooperación de procedimientos recursivos, cada uno de los cuales reconoce un no terminal en cualquier gramática que se esté implementando. Para el análisis puro, cada procedimiento simplemente devuelve un valor booleano para "no terminal (no) reconocido".

Para crear un AST con un analizador de descenso recursivo, uno diseña estos procedimientos para devolver dos valores: el booleano "reconocido" y, si se reconoce, un AST construido (de alguna manera) para el no terminal. (Un truco común es devolver un puntero, que está vacío para "no reconocido", o apunta al AST construido si se "reconoce"). La forma en que se genera el AST resultante para un solo procedimiento, es mediante la combinación de los AST de los subprocedimientos que invoca. Esto es bastante trivial para los procedimientos de hoja, que leen un token de entrada y pueden construir un árbol inmediatamente.

La desventaja de todo esto es que uno debe codificar manualmente el descenso recursivo y aumentarlo con los pasos de construcción del árbol. En el gran esquema de las cosas, esto es en realidad bastante fácil de codificar para gramáticas pequeñas.

Para el ejemplo de OP, supongamos que tenemos esta gramática:

GOAL = ASSIGNMENT 
ASSIGNMENT = LHS ''='' RHS '';'' 
LHS = IDENTIFIER 
RHS = IDENTIFIER | NUMBER

OK, nuestro analizador de descenso recursivo:

boolean parse_Goal()
{  if parse_Assignement()
   then return true
   else return false
}

boolean parse_Assignment()
{  if not Parse_LHS()
   then return false
   if not Parse_equalsign()
   then throw SyntaxError // because there are no viable alternatives from here
   if not Parse_RHS()
   then throw SyntaxError
   if not Parse_semicolon()
   the throw SyntaxError
   return true
}

boolean parse_LHS()
{  if parse_IDENTIFIER()
   then return true
   else return false
}

boolean parse_RHS()
{  if parse_IDENTIFIER()
   then return true
   if parse_NUMBER()
   then return true
   else return false
}

boolean parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return true
   else return false
}

boolean parse_semicolon()
{  if TestInputAndAdvance(";")
   then return true
   else return false
}

boolean parse_IDENTIFIER()
{  if TestInputForIdentifier()
   then return true
   else return false
}

boolean parse_NUMBER()
{  if TestInputForNumber()
   then return true
   else return false
}

Ahora, revisémoslo construyendo un árbol de sintaxis abstracta:

AST* parse_Goal() // note: we choose to return a null pointer for "false"
{  node = parse_Assignment()
   if node != NULL
   then return node
   else return NULL
}

AST* parse_Assignment()
{  LHSnode = Parse_LHS()
   if LHSnode == NULL
   then return NULL
   EqualNode = Parse_equalsign()
   if EqualNode == NULL
   then throw SyntaxError // because there are no viable alternatives from here
   RHSnode = Parse_RHS()
   if RHSnode == NULL
   then throw SyntaxError
   SemicolonNode = Parse_semicolon()
   if SemicolonNode == NULL
   the throw SyntaxError
   return makeASTNode(ASSIGNMENT,LHSNode,RHSNode)
}

AST* parse_LHS()
{  IdentifierNode = parse_IDENTIFIER()
   if node != NULL
   then return IdentifierNode
   else return NULL
}

AST* parse_RHS()
{  RHSnode = parse_IDENTIFIER()
   if RHSnode != null
   then return RHSnode
   RHSnode = parse_NUMBER()
   if RHSnode != null
   then return RHSnode
   else return NULL
}

AST* parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return makeASTNode("=")
   else return NULL
}

AST* parse_semicolon()
{  if TestInputAndAdvance(";")
   then return makeASTNode(";")
   else return NULL
}

AST* parse_IDENTIFIER()
{  text = TestInputForIdentifier()
   if text != NULL
   then return makeASTNode("IDENTIFIER",text)
   else return NULL
}

AST* parse_NUMBER()
{  text = TestInputForNumber()
   if text != NULL
   then return makeASTNode("NUMBER",text)
   else return NULL
}

Obviamente he pasado por alto algunos detalles, pero asumo que el lector no tendrá problemas para completarlos.

Las herramientas generadoras de analizadores como JavaCC y ANTLR básicamente generan analizadores de descendencia recursivos, y tienen instalaciones para construir árboles que funcionan de esta manera.

Las herramientas de generador de analizador que crean analizadores de abajo a arriba (YACC, Bison, GLR, ...) también crean nodos AST en el mismo estilo. Sin embargo, no hay un conjunto de funciones recursivas; en cambio, estas herramientas administran una pila de tokens vistos y reducidos a no-terminales. Los nodos AST se construyen en una pila paralela; cuando se produce una reducción, los nodos AST en la parte de la pila cubierta por la reducción se combinan para producir un nodo AST no terminal para reemplazarlos. Esto sucede con los segmentos de la pila de "tamaño cero" para las reglas gramaticales que también están vacías, lo que hace que los nodos AST (generalmente para "lista vacía" o "opción perdida") aparezcan aparentemente de la nada.

Con lenguajes pequeños, escribir analizadores de descendencia recursiva que construyen árboles es bastante práctico.

Un problema con los lenguajes reales (ya sea antiguo y canoso como COBOL o caliente y brillante como Scala) es que la cantidad de reglas gramaticales es bastante grande, complicada por la sofisticación del lenguaje y la insistencia en cualquier comité de idiomas que se encargue de ello para agregue constantemente nuevas golosinas ofrecidas por otros idiomas ("envidia del idioma", vea la carrera evolutiva entre Java, C # y C ++). Ahora escribir un analizador de descenso recursivo se sale de las manos y uno tiende a usar generadores de analizador. Pero incluso con un generador de analizador, escribir todo el código personalizado para construir nodos AST también es una gran batalla (y no hemos discutido lo que se necesita para diseñar una buena sintaxis "abstracta" frente a lo primero que se me ocurre). Mantener las reglas gramaticales y la creación de reglas de AST se hace cada vez más difícil con la escala y la evolución continua. (Si su idioma es exitoso, dentro de un año querrá cambiarlo). Así que incluso escribir las reglas de construcción de AST se vuelve incómodo.

Lo ideal sería escribir una gramática y obtener un analizador y un árbol. Puede hacer esto con algunos generadores de analizadores recientes: nuestro kit de herramientas de reingeniería de software de DMS acepta gramáticas libres de contexto y construye automáticamente un AST , sin trabajo por parte del ingeniero de gramática; ha estado haciendo esto desde 1995. Los chicos de ANTLR finalmente lo resolvieron en 2014, y ANTLR4 ahora ofrece una opción como esta.

Último punto: tener un analizador (incluso con un AST) no es una solución al problema real que se propuso resolver, sea lo que sea. Es solo una pieza de base, y para gran sorpresa de la mayoría de los analizadores-novatos, es la parte más pequeña de una herramienta que manipula el código. Google mi ensayo sobre la vida después de analizar (o ver mi biografía) para más detalles.

Answer 2

No es difícil en absoluto; de hecho, es una de las cosas más fáciles que he hecho. La idea general es que cada estructura (también conocida como reglas de analizador) es solo una lista de otras estructuras, y cuando se llama a una función parse (), simplemente recorren sus hijos y les dicen que analicen. Esto no es un bucle infinito; los tokens son estructuras, y cuando se llama a su parse (), escanean la salida del lexer. También deben tener un nombre para la identificación, pero esto no es obligatorio. Parse () normalmente devolvería un árbol Parse. Los árboles de Parse son como estructuras, listas de niños. También es bueno tener un campo de "texto", y su estructura principal, para la identificación. Aquí hay un ejemplo (querría organizarlo mejor y manejar el nulo para proyectos reales):

public void push(ParseTree tree) { // ParseTree
    children.add(tree);
    text += tree.text;
}

public ParseTree parse() { // Structure
    ParseTree tree = new ParseTree(this);
    for(Structure st: children) {
        tree.push(st.parse());
    }
    return tree;
}

public ParseTree parse() { // Token
    if(!lexer.nextToken() || !matches(lexer.token))
        return null;
    ParseTree tree = new ParseTree(this);
    tree.text = lexer.token;
    return tree;
}

Ahí. Llama al parse de la estructura principal (), y obtuviste un AST. Por supuesto, este es un ejemplo muy simple, y no funcionará de la caja. También es útil tener "modificadores"; por ejemplo, emparejar niño 3 una o más veces, niño 2 es opcional. Eso también es fácil de hacer; guárdelos en una matriz del mismo tamaño que su hijo, y cuando analice, verifique:

public void setModifier(int id, int mod) {
    mods[id] = mod;
}

public ParseTree parse() {
    ...
    ParseTree t;
    switch(mods[i]) {
        case 1: // Optional
            if((t = st.parse()) != null) tree.push(t);
        case 2: // Zero or more times
            while((t = st.parse()) != null) tree.push(t);
        ...
        default:
            tree.push(st.parse());
    }
    ...
}