コンパイラ:LL(0)パーサーとLR(0)パーサーの違いは何ですか。 LL(0)パーサーなどはありますか?


答え 1:

この質問はLL(0)パーサーに焦点を当てているようですので、それらを定義しましょう。 LL(0)パーサーは、プロダクションの開始時に0トークンを使用して左から右に解析し、適用するプロダクションを決定します。 0トークンとはどういう意味ですか?つまり、パーサーは解析対象のテキストを使用して、適用するプロダクションを決定できないことを意味します。 つまり、パーサーは選択を行えません。 解析するトークンのシーケンスを正確に解析し始める前に知る必要があります。 トークンのシーケンスは固定する必要があります。つまり、パーサーが解析するシーケンスは1つだけです。 したがって、「Hello world!」を受け入れるパーサーを使用できます。 このような文法で:

目標: "こんにちは"空白 "世界"感嘆符;

許可されるバリエーションは、レクサーがトークンをどのように照合するかだけであることに注意してください。

(表記法が明白であることを願っています-これは基本的にYacc ++で使用する表記法です。引用符で囲まれた文字列は、定義されていない識別子と同様にトークンです。)

パーサーは常にトークンのまったく同じシーケンスを予期します。 最初の例のように、ルールを1つだけ持つ必要はありません。 このように見えるかもしれません。

目標:hello-partの空白のend-part;

hello-part:hello1;

hello1: "Hello";

エンドパート:ワールドパートラストパート。

ワールドパート:「ワールド」;

最後の部分: "!";

ただし、どのルールにも「or」(|)演算子がなく、非終端記号ごとに1つのルールしかないことに注意してください。 これにより、パーサーは、識別トークン(パーサーの進行方向を選択するトークン)を使用せずに各ルールに一致する方法を知ることができます。これにより、文法LL(0)が作成されます。

さて、再帰生成を使用しても、LL(0)文法を保持することは可能ですか? 答えはいいえだ"。 再帰的なルールがある場合に何が起こるか見てみましょう。

ゴール:「x」ゴール「y」;

覚えておいてください、非終端記号ごとに1つのルールのみが許可され、「or」演算子は許可されません。 したがって、ゴールの再帰呼び出しに到達すると、その再帰呼び出しである無限ループに再び到達するパスに到達する必要があります。 自分自身に証明してください。その呼び出しをどのようにネストするか、再帰が間接的であるかどうかは関係ありません。 常に無限ループになります。

したがって、LL(0)文法は、トークンの有限リスト、厳密に1つの有限リスト(毎回同じリスト)を解析する必要があります。

LR(0)の意味との違いに注意してください。 LR(k)パーサーは、プロダクション内の任意の(好きなだけの)トークンを使用して識別し、さらに、プロダクションが縮小するときにコンテキストから最大k個のトークンを使用して、縮小する必要があるかどうかを判断できます。 LR(0)の場合、追加のトークンを使用して、減らす必要があるかどうかを判断することはできません。 削減されるルールのトークンに基づいて簡単に決定する必要があります。 簡単なLR(0)文法は次のとおりです。

目標: "x" | "("目標 ")";

この文法は、いくつかの括弧で囲まれた「x」を解析します。 「x」トークンと「(」トークンを使用して、適用するルールを決定できることに注意してください。LR(0)の0は、LL(0)の0のようにルール内のトークンの使用を制限しません。制限するのは、縮小することを決定するときのトークンの使用(コンテキストの、非終端の一部の使用における規則の後)です。この文法は、縮小することを決定するためのコンテキストを必要としません。 2番目の「x」は、「)」が表示された後に減少します。 ルール内のトークンは、ルールが縮小されるタイミングを正確に決定します。


答え 2:

LL(0)パーサーは、トークンストリームを左から右へ処理し、先読みなしで左端の派生を使用することを意味します。 理論的には、LL(0)パーサーは可能ですが、たとえ存在してもパーサーはあまり使用されません。 LL(0)パーサーは、先読みがゼロの現在の非端末に基づいて、適用するプロダクションを予測する必要があります。 このような文法では、すべての非端末に関連付けられているプロダクションは1つだけであり、再帰はありません。

LR(0)パーサーは、先読みがゼロのRightmost派生を使用して、トークンストリームを左から右に処理することを意味します。 これは、LL(0)パーサーが解析ツリーを上から下に構築するのに対し、解析ツリーを下から上に構築することを意味します。