のような単純な文法が与えられます
rule1
:= token1 token2 token3 token4
|| token1 token2 token3 token3;
最初の3つのトークンをシフトしてから、4番目のトークンを調べてどのルールを減らすかを確認することと、3つのトークンの先読みを実行してどのルールを減らすかを確認することの違いは何ですか？
1 に答える
9
shift/reduce パーサーでは、先読みはどのプロダクションが考慮されているかを判断するために使用されるのではなく、パーサーが次のトークンをシフトする必要があるか、または何らかの削減アクションを実行する必要があるかを決定するために使用されます。上記の文法のシフト/リデュース パーサーがある場合、パーサーはリデュースするかどうかを決定する前に常に 4 つのトークンをシフトします。LR パーサーでは、適切な一連のシンボルが解析スタックの一番上にある場合にのみリダクションが実行されることに注意してください。ここで先読みが必要になるのは、パーサーが持っていた 4 つのトークンを減らすべきか、それともさらに多くのシンボルをシフトし続けて後で減らすべきかを判断できない場合だけです。
具体的には、パーサーはおそらく次のようにします。
Stack Input Action
-------------------------------------------------------------------------------
token1 token2 token3 token4 Shift
token1 token2 token3 token4 Shift
token1 token2 token3 token4 Shift
token1 token2 token3 token4 Shift
token1 token2 token3 token4 Reduce, Option 1
rule1 Accept
または
Stack Input Action
-------------------------------------------------------------------------------
token1 token2 token3 token3 Shift
token1 token2 token3 token3 Shift
token1 token2 token3 token3 Shift
token1 token2 token3 token3 Shift
token1 token2 token3 token3 Reduce, Option 2
rule1 Accept
これは、使用するプロダクションを予測しようとすることによって機能する LL(k) パーサーのようなトップダウン パーサーとは対照的であることに注意してください。その場合、パーサーはプロダクションを推測し、その推測をチェックする (予測/一致解析) ため、4 つの先読みトークンが必要になります。たとえば、トップダウン パーサー (ここでは LL(4) である必要があります) では、次のようになります。
Stack Input Action
----------------------------------------------------------------------------------
rule1 token1 token2 token3 token4 $$$$ Predict, Option 1
token1 token2 token3 token4 token1 token2 token3 token4 $$$$ Match
token2 token3 token4 token2 token3 token4 $$$$ Match
token3 token4 token3 token4 $$$$ Match
token4 token4 $$$$ Match
$$$$ Accept
または
Stack Input Action
----------------------------------------------------------------------------------
rule1 token1 token2 token3 token3 $$$$ Predict, Option 2
token1 token2 token3 token3 token1 token2 token3 token3 $$$$ Match
token2 token3 token3 token2 token3 token3 $$$$ Match
token3 token3 token3 token3 $$$$ Match
token3 token3 $$$$ Match
$$$$ Accept
使用するプロダクションを予測するために先読みがどのように必要であるかに注意してください。したがって、パーサーは先読みの 4 つのトークンを持っている必要があります。LR パーサーでは、パーサーは、探しているものが見られることに満足するまで、より多くのトークンを検査することによって機能し、次に削減 (シフト/削減解析) します。この場合、先読みはまったく必要ありません。先読みは、パーサーがハンドル(削減する文字列) の末尾を認識したかどうか、またはハンドルの途中にあり、シフトを続ける必要があるかどうかを判断するために、LR パーサーでのみ必要です。これが、たとえば、いくつかの興味深い文法が LR(0) であると示される理由ですが、LL(0) である唯一の文法は、各非終端記号がそれに関連付けられた正確に 1 つの生成を持つ文法です。先読みは、トップダウン解析とボトムアップ解析で根本的に異なる用途を持っています。
一般的に言えば、トップダウン パーサーはボトムアップ パーサーよりも少ない文法を処理できます。実際、LL(k) 文法は LR(k) であることが保証されていますが、その逆は保証されていません。
お役に立てれば！
于 2011-12-13T00:00:10.613 に答える