c++ - 再帰下降パーサーの質問

Question

再帰下降パーサーの書き方について2つの質問があります。

1つ目は、いくつかの異なる非終端記号の1つと一致する非終端記号がある場合はどうなりますか？どちらが正しいかをどのように確認しますか？

次に、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

または、1 つの簡単なレッスンでストロークを行う方法のレッスン。

1 つ目は、いくつかの異なる非終端記号の 1 つに一致する非終端記号がある場合はどうなるでしょうか。どの方法が正しいかをどのように確認しますか?

流れを先取りして決断を下す必要があります。RDC でバックトラッキングを行うのは難しいです。

より簡単な解決策は、文法を先読みする必要がないように設計することです (難しい)。

次に、AST をどのように構築しますか?

関数呼び出しからの戻り値は、呼び出しによって解析されたすべてのツリーです。すべてのサブ呼び出しを別の動的に割り当てられたオブジェクトにラップし、それを返します。