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

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

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

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

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

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