递归下降解析器问题

Question

我有两个关于如何编写递归下降解析器的问题：

第一个问题是，当您有一个非终结符可以匹配几个不同的非终结符时，如何检查哪种方式是正确的？

第二个问题是，如何构建AST？使用YACC，我只需编写一段代码来执行每个非终结符的实例，并且它有特殊变量引用规则的“值”。在递归下降解析器中如何进行类似的操作？

- mtk358

---

请参见https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769。 - Ira Baxter

Answer 1

1. 你按顺序尝试它们，如果失败则回溯。或者你可以证明你的语言在LL(k)中，并查看最多k个符号。
2. 对于每个成功解析的规则，你从子规则的结果构造一个对象。

E.g.,

class ASTNode {
  public:
    virtual int eval() = 0;
    virtual ~ASTNode() = 0;
};

// construct this when parsing an integer literal
class Value : ASTNode {
    int v;
  public:
    Value(int v_) : v(v_) {}
    virtual int eval() { return v; }
    virtual ~Value() {}
};

// construct this when parsing "x+y"
class Addition : ASTNode {
    ASTNode *left, *right;
  public:
    Addition(ASTNode *l, ASTNode *r) : left(l), right(r) {}
    virtual int eval() { return l->eval() + r->eval(); }
    virtual ~Addition() { delete left; delete right; }
};

- Fred Foo

---

@Jörgen：有些混乱，但是可以实现。更新了关于LL和前瞻的说明。（我的背景是自然语言处理，在那里每个语法都是模棱两可的，所以回溯是我学习解析的第一件事 :)） - Fred Foo

AST节点不应该只包含解析信息，而不积极地对其进行操作吗？至少对我来说，将实际逻辑（示例中的实际加法）嵌入节点本身似乎会导致以后出现很多问题，并且似乎违反了SRP。 - stijn

@stijn：我承认这并不是特别优雅，但我想展示一个简单的例子，几乎可以做一些有用的事情，并且仍然比OP提到的Yacc示例更清晰地分离逻辑。 - Fred Foo

@stijn：你还能把逻辑放在哪里呢？节点拥有一个 eval 方法似乎是最完美的方式。 - mtk358

@mtk：在一个真正的解释器中，你需要分离解析和执行阶段，这样你就可以在两者之间进行优化。 - Fred Foo

@mtk：一种可能性是实现访问者模式遍历节点树，并为每个节点创建一个将执行逻辑的对象。这些“逻辑节点”大致具有与 AstNodes 相同的结构，但正如 larsman 所说，现在有一个中间阶段，将解析与逻辑分开，并可以进行优化等操作。使用访问者还有一个好处，就是如果要打印 AST，则不必更改节点，只需实现一个仅进行打印的访问者即可。 - stijn

Answer 2

或者是如何在一堂简单的课程中让自己中风的教训。

第一个问题是，当您有一个非终端可以匹配几个不同的非终端时，该怎么办？您如何检查哪种方式是正确的？

您需要向前查看流并做出决策。在 RDC 上进行回溯很困难。

更简单的解决方案是设计语法，使其不需要向前查看（难度较大）。

第二个问题是，如何构建 AST？

函数调用的返回值是由调用解析的所有内容组成的树。您将所有子调用包装到另一个动态分配的对象中并返回它。

- Martin York

---

也许使用不同类型的解析器会是个好主意？ - mtk358