¿Es posible usar un analizador de descenso recursivo 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 un 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 a medida que asciende recursivamente?

Gracias, Boda Cydo.

Nota: Soy nuevo en analizar. (Hice varias preguntas así ya, y estoy mejorando con eso).

Answer 1

Si es posible. Cómo hacerlo dependerá de la implementación que desee. Aquí hay una muestra que podría funcionar para usted:

Primero, defina 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, deberá integrar eso en sus funciones de descenso recursivas:

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);
  }
}

A medida que desciende por su árbol de análisis, probablemente querrá enviar cualquier nuevo nodo "raíz", para que los niños puedan agregarse a él. 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 o un árbol abstracto simple utilizando el proceso anterior. Dado que la función de análisis devuelve el nodo raíz, que hará referencia a todos y cada uno de los nodos para niños, tendrá acceso completo al árbol de análisis después de la análisis.

Ya sea que use un árbol de análisis heterogéneo o homogéneo, necesitará una forma de almacenar información suficiente para que sea útil.