5

私はいくつかの再帰的上昇パーサーを書いてきましたが、苦労してきたことの 1 つは左再帰です。次のように、正しい再帰を再帰的に表現できることは明らかです。

addExpr
    : primaryExpr '+' addExpr
    | primaryExpr;

の線に沿った何かによって

parseAddExpr() {
    auto x = parsePrimaryExpr();
    if (next_token == '+') {
        auto result = make_unique<PlusExpr>();
        result->lhs = x;
        result->rhs = parseAddExpr();
        return std::move(result);
    }
    return std::move(x);
}

しかし、左再帰については、while ループしか思いつきませんでした。

mulExpr
    : mulExpr '*' addExpr
    | addExpr;

parseMulExpr() {
    auto expr = parseAddExpr();
    while(next_token == '*') {
        auto mul_expr = make_unique<MulExpr>();
        mul_expr->lhs = std::move(expr);
        mul_expr->rhs = parseAddExpr();
        expr = std::move(mul_expr);
    }
    return std::move(expr);
}

つまり、これは正常に機能しますが、再帰バージョンが必要だと常に感じていました。左結合演算子を反復ではなく再帰的に実装することは可能ですか?

4

1 に答える 1

8

あなたの関数は再帰下降であり、再帰下降ではありません。あなたが遭遇した再帰下降パーサーが左再帰で抱えている問題は、非常によく知られており、研究されています。構文解析をカバーするコンパイラコースまたは教科書は、問題とそれを解決する方法について説明します。

反復を使用することは、それを処理するための完全に正常で有効な方法です。 たとえば、これらのコースノートを参照してください。これらのメモでは、ルールT -> T '*' S | T '/' S | S（mulExpr除算が追加されたルール）がルールに変換されます。T -> S { ('*' | '/') S }中括弧{...}は「0回以上の繰り返し」を意味します。

アップデート

あなたのコメントに基づいて、あなたは「再帰下降」が何を意味するのか、そして「再帰下降」が何を意味するのかについて少し混乱していると思います。

再帰下降

再帰下降の基本的な考え方は、文法の非終端記号ごとに1つの関数を作成することです。一部の非終端記号Aに対応する関数の役割は、可能であればAの1つのインスタンスを完全に解析し、必要に応じて、文法のAの生成の右側に表示される非終端記号の関数を呼び出すことです。

したがって、たとえば、文法にはaddExpr次の2つの生成を持つ非終端記号があります。

addExpr -> primaryExpr '+' addExpr
addExpr -> primaryExpr

したがって、再帰下降パーサーには、プロダクションaddExprの1つの右側を一致させようとする関数があり、これらの非終端記号はのプロダクションに表示されるため、必要に応じて関数と（それ自体！）addExprを呼び出します。primaryExpraddExpraddExpr

そして確かに、これはまさにあなたがあなたのparseAddExpr機能に持っているものです。必要に応じて、addExprプロダクションの1つに一致する方法を探します。parsePrimaryExprparseAddExpr

再帰的な上昇

再帰的上昇は、LR解析を実装するための（非常にまれな）方法です。LRパーサーには、状態テーブルがあり、各状態の行と各端末の列があります。再帰的アセントパーサーでは、テーブルをデータとして表しません。代わりに、状態ごとに1つの関数を作成します。その状態の行は、関数内のswitchステートメントとして具体化されます。

LRパーサーでは、通常、状態と非終端記号の間、または状態とプロダクションの間で1対1の対応はありません。一般的に、プロダクションよりも多くの州があります。各状態は、プロダクション内の一連の位置を表します。

あなたのパーサー

あなたの投稿の関数を見ると、状態テーブルを作成または具体化したという証拠はありません。私が見ているのは、文法の非終端記号に直接対応する一連の関数です。その対応は、再帰下降の特徴です。

また、左再帰的なプロダクションで問題が発生しているという事実は、再帰下降を使用しているという死んだプレゼントです。LRパーサーには左再帰の問題はなく、再帰下降パーサーには問題があります。

于 2012-09-08T19:04:54.590 に答える