0

lr(0) パーサーについて疑問があります。たとえば、次の文法があります。

S -> S N
   | 

N -> terminalsymbol

lr0 オートマトンの最初の状態を構築しようとすると、次の最初の状態が得られます。

S ' -> . S $ 

S -> . S N
S -> .

ですから、ここで私にはばかげた疑問が浮かびます。「S -> 」があるので。最初の状態では、これは lr0 パーサーのシフト/リデュースの状況ですか? パーサーは、非終端記号 S によってアクションをシフトしたり、空のトランジションによってアクションを減らしたりすることができます (私はそう思います)。

空のトランジションの例を探して Web を検索しましたが、見つかりませんでした。

4

1 に答える 1

1

拡張文法から始めれば、それは衝突ではありません。

初期状態では、可能なシフト アクションはなく、リデュース アクションは 1 つだけです。したがって、reduce アクションは無条件に実行する必要があります。

S を減らすと、次の状態になります。

S' -> S . $
S  -> S . N
N  -> . nonterminal

これは、入力終了マーク、または次の非終端記号のいずれかをシフトします。それが非終端であると仮定すると、次のようになります。

N  -> nonterminal .

これは別の強制的な削減であり、次のようになります

S  -> S N .

そして、次のように戻ります。

S' -> . S $
S  -> . S N
S  -> .

ただし、元の拡張されていない文法は LR(0) ではありません。(空の文字列と他の文字列の両方を含む言語は、LR(0) にはなりません。)

于 2013-07-08T19:20:43.410 に答える