É possível usar o analisador de descida recursiva para verificar a gramática e construir a árvore de análise ao mesmo tempo?

Question

É possível gerar uma árvore de análise ao mesmo tempo em que uso o analisador de descida recursiva para verificar se os dados correspondem à gramática?

Nesse caso, que abordagem eu usaria para construir uma árvore, pois descida recursivamente?

Obrigado, Boda Cydo.

Nota: Eu sou novo em analisar. (Fiz várias perguntas sobre assim, e estou melhorando com isso.)

Answer 1

Sim é possivel. Como fazer isso dependerá da implementação que você deseja. Aqui está uma amostra que pode funcionar para você:

Primeiro, defina seu nó:

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

Em seguida, você precisará integrar isso às suas funções de descida recursiva:

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

Ao descer pela sua árvore de análise, você provavelmente desejará enviar o novo nó "raiz", para que as crianças possam ser adicionadas a ele. Alternativamente, parseSubtree poderia criar e retornar um nó, que seria então adicionado ao nó raiz.

Você pode construir a árvore de análise ou uma árvore abstrata simples usando o processo acima. Como a função Parse retorna o nó raiz, que fará referência a todos e quaisquer nós filhos, você terá acesso total à árvore de análise após a análise.

Se você usa uma árvore de broca heterogênea ou homogênea, precisará de uma maneira de armazenar informações suficientes para torná -las úteis.