8

再帰降下パーサーを使用してデータが文法に一致するかどうかを確認すると同時に、解析ツリーを生成することはできますか?

もしそうなら、再帰的に降下するときにツリーを構築するためにどのようなアプローチを使用しますか?

ありがとう、ボダ・シド。

注：私は解析が初めてです。（すでにSOについていくつかの質問をしましたが、私はそれで良くなっています。）

4

1 に答える 1

7

はい、可能です。その方法は、必要な実装によって異なります。これはあなたのために働くかもしれないサンプルです：

まず、ノードを定義します。

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

次に、それを再帰降下関数に統合する必要があります。

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

解析ツリーを下っていくとき、子を追加できるように、新しい「ルート」ノードが何であれ送信する必要があるでしょう。または、parseSubtreeノードを作成して返すこともできます。このノードは、ルート ノードに追加されます。

上記のプロセスを使用して、解析ツリーまたは単純な抽象ツリーのいずれかを構築できます。parse 関数は、すべての子ノードを参照するルート ノードを返すため、解析後に解析ツリーに完全にアクセスできます。

異種解析ツリーを使用するか同種解析ツリーを使用するかに関係なく、それを有効にするために十分な情報を格納する方法が必要になります。

于 2010-03-10T20:01:54.517 に答える