递归下降解析器问题

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？

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