Можно ли использовать анализатор рекурсивного спуска, чтобы одновременно проверять грамматику и строить дерево разбора? - PullRequest
Новая
       14

Можно ли использовать анализатор рекурсивного спуска, чтобы одновременно проверять грамматику и строить дерево разбора?

7 голосов
/ 10 марта 2010

Можно ли создать дерево разбора одновременно с использованием анализатора рекурсивного спуска для проверки соответствия данных грамматике?

Если да, то какой подход я бы использовал для построения дерева при рекурсивном спуске?

Спасибо, Бода Цидо.

Примечание: я новичок в разборе. (Уже задавал несколько вопросов по SO, и мне становится лучше.)

1 Ответ

6 голосов
/ 10 марта 2010

Да, это возможно. Как это сделать, будет зависеть от реализации, которую вы хотите. Вот пример, который может работать для вас:

Сначала определите ваш узел: 

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 может создать и вернуть узел, который затем будет добавлен к корневому узлу.

Вы можете построить либо дерево разбора, либо простое абстрактное дерево, используя описанный выше процесс. Поскольку функция синтаксического анализа возвращает корневой узел, который будет ссылаться на все дочерние узлы, после синтаксического анализа у вас будет полный доступ к дереву синтаксического анализа.

Независимо от того, используете ли вы разнородное или однородное дерево разбора, вам понадобится способ хранить достаточно информации, чтобы сделать ее полезной.

...