6

LR(1) - アイテムの先読みの原則を理解するのに苦労しています。先読みセットを計算するにはどうすればよいですか?

例として、次の文法があるとします。

S -> AB
A -> aAb | b
B -> d

次に、最初の状態は次のようになります。

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b,   {look ahead}

先読みとは何かは知っていますが、それらを計算する方法がわかりません。グーグルで答えを探しましたが、これを簡単に説明しているウェブページが見つかりませんでした。

前もって感謝します

4

1 に答える 1

14

あなたの例の最初の 2 つの状態を書き留めておきます。

S -> AB
A -> aAb | b
B -> d

状態 0:

(1) S -> .AB, {$}   # Once we have done this rule it's EOF ($) 
(2) A -> .aAb, {d}  # from (1), after A there has to be a B whose first symbol has to be d
(3) A -> .b, {d}    # as above

状態 1:

(4) A -> a.Ab, {d}   # from (2)
(5) A -> .aAb, {b}   # from (4), the symbol after the A has to be b
(6) A -> .b, {b}     # from (4), as above
(7) A -> b., {d}     # from (3)
(8) S -> A.B, {$}    # from (1) and (7)
(9) B -> .B, {$}     # from (8)

など、LR(0) パーサーの場合と同じシフト/リデュース/クロージャに従いますが、次のシンボルを追跡 ( の先読み
) します... (状態 2+ は長いため、お勧めしませんそれらを手で処理してください！）

Udacity のプログラミング言語コースを調べて、字句解析と構文解析について詳しく学ぶことをお勧めします。wikipediaと関連する SO questionにも例があります。

于 2012-11-19T22:20:46.667 に答える