私はウィキペディアで両方を読んでいて、LR(0) パーサーは存在しますが、LL(0) パーサーのようなものは存在しないことに気付きました。
私が読んだことから、LL(k)/LR(k) の k は、パーサーが現在作業中の現在の文字を超えて認識できる文字数を意味することを理解しています。
私の質問は、LR(0) が存在するにもかかわらず、LL(0) パーサーなどがないのはなぜですか?
17801 次
1 に答える
38
違いは、LR(k) と LL(k) の k の意味に関係しています。
LL(k) では、パーサーは左端の派生をトレースするトップダウン、左から右の解析に関する情報を保持します。パーサーは、現在の非終端記号を繰り返し調べてから、入力ストリームの次の k 個のトークンを調べて、どのプロダクションを使用する必要があるかを判断します。その結果、LL(0) パーサーを使用している場合、パーサーは、現在の非ターミナルのみに基づいて、使用するプロダクションを予測する必要があります。これは、各非終端記号に関連付けられたプロダクションが 1 つしかない場合にのみ可能です。つまり、文法が 1 つの文字列を正確に生成するか、文字列をまったく生成しない (ループに入る) ことを意味します。したがって、数学的には明確に定義されていますが、LL(0) 解析は実際には使用されません。
LR(k) では、パーサーはボトムアップで動作します。現在の「状態」とともにシンボルのスタックを維持し、シフト(スタックの一番上に別のシンボルをプッシュする) を実行するか、削減(スタックからいくつかのシンボルをポップしてプロダクションを適用する) を実行するかを継続的に決定します。逆に）。LL(k) パーサーと LR(k) パーサーの主な違いの 1 つは、LR(k) パーサーが実行するアクションを決定する方法です。LR(k) パーサーでは、次に何をするかの決定は、先読みの次の k トークンとパーサーの現在の状態の両方に基づいて行われます。その結果、LR(0) パーサーは、たとえ先読みトークンが見えなくても、どのアクションを実行するかについてある程度インテリジェントな決定を下すことができます。これは、パーサーの現在の状態が、プロダクション内のどこにあるのかに関する膨大な量の情報をエンコードできるためです。パーサーは、入力の次のトークンとして実際に期待できるものです (パーサーがそれらのトークンを直接見ることができない場合でも)。
要するに、LL(0) は非常に弱いものです。パーサーは現在の非終端記号のみに基づいて決定を行う必要があるためです。LR(0) パーサーは、パーサーが内部状態に基づいて選択を行うため、かなり強力です。これは通常、パーサーが次に何をすべきかについて情報に基づいた決定を行うのに十分なほど詳細です。
LL(0) が弱いのに対し、LR(0) はかなり強力な理由がもう 1 つあります。LL(0) パーサーでは、パーサーはどのプロダクションを実行する必要があるかを即座に決定する必要があります。つまり、パーサーは完全にやみくもにプロダクションを推測する必要があります。LR(0) パーサーでは、パーサーは、縮小する時期であると判断する前に、複数のシンボルをシフトできます。したがって、パーサーは、先読みなしで、文字列の構造を理解するのに十分な入力トークンを確認するまで、使用するリダクションの決定を延期できます。これは、LL(k) 文法は自動的に LR(k) になるというより一般的な事実の特殊なケースです。
お役に立てれば！
于 2013-02-03T18:49:27.407 に答える