c++ - 递归下降解析器问题

Question

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

第一个是当你有一个非终结符可以匹配几个不同的非终结符之一时怎么办？你如何检查哪种方式是正确的？

其次，如何构建 AST？使用 YACC，我可以只编写一段代码来为非终结符的每个实例执行，它具有引用规则“值”的特殊变量。你如何在递归下降解析器中做类似的事情？

Answer 1

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

例如，

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

Answer 2

或者如何在一个简单的课程中给自己一个中风的课程。

第一个是当你有一个非终结符可以匹配几个不同的非终结符之一时怎么办？你如何检查哪种方式是正确的？

您需要在流程中向前看并做出决定。很难在 RDC 上进行回溯。

一个更简单的解决方案是设计您的语法，以便它不需要向前看（硬）。

其次，如何构建 AST？

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