¿Es posible usar Recursive Descent Parser para verificar la gramática Y construir el árbol de análisis al mismo tiempo?

Question

¿Es posible generar un árbol de análisis al mismo tiempo que uso el analizador de descenso recursivo para verificar si los datos coinciden con la gramática?

Si es así, ¿qué enfoque usaría para construir un árbol mientras descendía recursivamente?

Gracias, Boda Cydo.

Nota: Soy nuevo en el análisis sintáctico. (Hice varias preguntas sobre SO ya, y estoy mejorando con eso.)

Answer 1

Sí, es posible. Cómo hacerlo dependerá de la implementación que desee. He aquí una muestra que podría funcionar para usted:

En primer lugar, definir su nodo:

class ParseTreeNode { 
    private final String name; 
    private final List<ParseTreeNode> children = /* new */; 
    public ParseTreeNode(String name) { 
    this.name = name; 
    } 
    public void addChild(ParseTreeNode child) { 
    children.add(child); 
} 

A continuación, tendrá que integrar esto en sus funciones descendente recursivo:

class RDParser { 
    ParseTreeNode parse(Input input) { 
    ParseTreeNode root = createParseTreeNodeNamed("Root") 
    switch (input.nextToken()) { 
     case OPT1: 
     root.addChild(createParseTreeNodeNamed("Opt1")); 
     break; 
     case OPT2: 
     while (/*someCondition*/) { 
      root.addChild(createParseTreeNodeNamed("Opt2-sibling" + /* i */)); 
     } 
     case SUBTREE: 
     ParseTreeNode subtree = createParseTreeNodeNamed("Subtree"); 
     root.addChild(subtree); 
     parseSubtree(subtree, input); 
     break; 
     default: 
     error("Input %s was not in the expected first/follow sets", input.nextToken()); 
    } 
    } 
    void parseSubtree(ParseTreeNode node, Input input) { 
    node.addChild(createParseTreeNodeNamed("subtree-child")); 
    /* ... */ 
    } 

    /* and other functions do similarly */ 
    ParseTreeNode createParseTreeNodeNamed(String name) { 
    return new ParseTreeNode(name); 
    } 
} 

Como desciende por su árbol de análisis sintáctico, probablemente quiera enviar lo que sea que sea el nuevo nodo "raíz", para que se puedan agregar los elementos secundarios. Alternativamente, parseSubtree podría crear y devolver un nodo, que luego se agregaría al nodo raíz.

Puede construir el árbol de análisis sintáctico o un árbol abstracto simple utilizando el proceso anterior. Como la función de análisis devuelve el nodo raíz, que hará referencia a todos los nodos secundarios, tendrá acceso completo al árbol de análisis sintáctico después del análisis.

Si utiliza un árbol de análisis heterogéneo u homogéneo, necesitará una forma de almacenar información suficiente para hacerlo útil.