Construir un Árbol de Sintaxis Abstracta con una lista de Tokens

El truco fundamental es reconocer que el análisis, sin embargo logrado, ocurre en pasos incrementales, incluida la lectura de los tokens uno por uno.

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 toca fondo en la construcción de nodos de hoja AST para los tokens a medida que se escanean. Esta idea básica ocurre en casi todos los analizadores de AST.

Si uno construye un analizador de descenso recursivo, uno en efecto construye 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 booleano para "no terminal (no) reconocido".

Para construir 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. (Común hack es devolver un puntero, que es nulo para "no reconocido", o apunta al AST construido si"reconocido"). La forma en que se construye el AST resultante para un solo procedimiento, es combinando los ASTs de los sub-procedimientos que invoca. Esto es bastante trivial para los procedimientos de hoja, que leen un token de entrada y pueden construir inmediatamente un árbol.

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, vamos a revisarlo construir 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 Parser como JavaCC y ANTLR básicamente generan parsers de descenso recursivo, y tienen facilidades por construir árboles que funcionan muy bien así.

Herramientas de generador de analizadores que construyen analizadores de abajo hacia arriba (YACC, Bison, GLR,...) también construye nodos AST en el mismo estilo. Sin embargo, no hay un conjunto de funciones recursivas; en su lugar, 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 no terminal Nodo AST para reemplazarlos. Esto sucede con segmentos de pila de" tamaño cero " para reglas gramaticales que también están vacíos, lo que hace que los nodos AST (típicamente para 'lista vacía' o 'opción faltante') parezcan aparecer de la nada.

Con lenguajes bitty, escribir analizadores de descenso recursivo que construyan árboles es bastante práctico.

Un problema con los idiomas reales (ya sean viejos y canosos como COBOL o calientes y brillantes como Scala) es que el número de reglas gramaticales es bastante grande, complicado por el sofisticación del lenguaje y la insistencia en cualquier comité de lenguaje que esté a cargo de él para agregar perpetuamente nuevas golosinas ofrecidas por otros lenguajes ("envidia del lenguaje", ver la raza 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 un buen sintaxis "abstracta" vs. lo primero que viene a la mente). Mantener las reglas gramaticales y construir AST se vuelve progresivamente más difícil con la escala y la evolución continua. (Si tu idioma tiene éxito, dentro de un año querrás cambiarlo). Así que incluso escribir las reglas de construcción de AST se vuelve incómodo.

Idealmente, a uno le gustaría escribir una gramática, y obtener un analizador y un árbol. Usted puede hacer esto con algunos generadores de analizadores recientes: Nuestro Kit de herramientas de Reingeniería de software DMS acepta gramáticas libres de contexto, y construye automáticamente un AST , sin trabajo por parte del ingeniero gramatical; ha estado haciendo esto desde 1995. Los chicos de ANTLR finalmente descubrieron esto en 2014, y ANTLR4 ahora ofrece una opción como esta.

Último punto: tener un analizador sintáctico (incluso con un AST) no es una solución al problema real que se propuso resolver, sea lo que sea. Es solo una pieza fundamental, y para sorpresa de la mayoría de los principiantes, es la parte más pequeña de una herramienta que manipula el código. Busque en Google mi ensayo sobre la vida Después de Analizar (o consulte mi biografía) para obtener más detalles.