parsing - LR(1) パーサーでの左再帰

Question

LR(1) パーサーはこのタイプの文法を解析できますか?

S -> SA  | A
A -> aSb | ab

このタイプのパーサーを実装する Java プログラムを作成しようとしていますが、左再帰を使用しない文法では正しい結果しか得られません。

Answer 1

LR(1) パーサーは、一部のタイプの左再帰を処理できますが、すべての左再帰文法が LR(1) であるとは限りません。

特定の文法が LR(1) かどうか見てみましょう。文法を拡張すると、

S'→S

南→南 | あ

A→aSb | ab

したがって、構成セットは

 (1)
 S' -> .S    [$]     (Go to 2)
 S  -> .SA   [$a]    (Go to 2)
 S  -> .A    [$a]    (Go to 3)
 A  -> .aSb  [$a]    (Shift on a and go to 4)
 A  -> .ab   [$a]    (Shift on a and go to 4)

 (2)
 S' -> S.    [$]     (Accept on $)
 S  -> S.A   [$a]    (Go to 3)
 A  -> .aSb  [$a]    (Shift on a and go to 4)
 A  -> .ab   [$a]    (Shift on a and go to 4)

 (3)
 S  -> A.    [$a]    (reduce on $ or a)

 (4)
 A  -> a.Sb  [$a]    (Go to 6)
 A  -> a.b   [$a]    (Shift on b and go to 10)
 S  -> .SA   [ab]    (Go to 11)
 S  -> .A    [ab]    (Go to 12)
 A  -> .aSb  [ab]    (Shift on a and go to 8)
 A  -> .ab   [ab]    (Shift on a and go to 8)

 (5)
 A  -> ab.   [$a]    (Reduce on a or $)

 (6)
 A  -> aS.b  [$a]    (Shift on b and go to 7)
 S  -> S.A   [ab]    (Go to 13)
 A  -> .aSb  [ab]    (Shift on a and go to 8)
 A  -> .ab   [ab]    (Shift on a and go to 8)

 (7)
 A  -> aSb.  [$a]    (Reduce on a or $)

 (8)
 A  -> a.Sb  [ab]    (Go to 14)
 A  -> a.b   [ab]    (Shift on b and go to 16)
 S  -> .SA   [ab]    (Go to 11)
 S  -> .A    [ab]    (Go to 12)
 A  -> .aSb  [ab]    (Shift on a and go to 8)
 A  -> .ab   [ab]    (Shift on a and go to 8)

 (9)
 S  -> SA.   [$a]    (Reduce on a or $)

 (10)
 A  -> ab.   [$a]    (Reduce on a or b)

 (11)
 S  -> S.A   [ab]    (Go to 13)
 A  -> .aSb  [ab]    (Shift on a and go to 8)
 A  -> .ab   [ab]    (Shift on a and go to 8)

 (12)
 S  -> A.    [ab]    (Reduce on a or b)

 (13)
 S  -> SA.   [ab]    (Reduce on a or b)

 (14)
 A  -> aS.b  [ab]    (Shift on b and go to 15)
 S  -> S.A   [ab]    (Go to 13)
 A  -> .aSb  [ab]    (Shift on a and go to 8)
 A  -> .ab   [ab]    (Shift on a and go to 8)   

 (15)
 A  -> aSb.  [ab]    (Reduce on a or b)

 (16)
 A  -> ab.   [ab]    (Reduce on a or b)

この文法にはシフト/リデュースまたはリデュース/リデュースの競合がないため、LR(1) である必要があります (どこかで間違いを犯していない限り!)

お役に立てれば！

Answer 2

SLR文法でもあることが判明したため、LRはやり過ぎです。LR では 16 ステートが必要ですが、SLR では 10 ステートしか必要ありません。

(1)
 S' -> .S    S => (Go to 2)
 S  -> .SA   A => (Go to 3)
 S  -> .A    a => (Shift and go to 4)
 A  -> .aSb     
 A  -> .ab   

 (2)
 S' -> S.    $ => (Accept on $)
 S  -> S.A   A => (Go to 5)
 A  -> .aSb  a => (Shift and go to 6)
 A  -> .ab   

 (3)
 S  -> A.    [$b] => (reduce on $ or b)

 (4)
 A  -> a.Sb  S => (Go to 7)
 A  -> a.b   A => (Go to 9)
 S  -> .SA   a => (Shift and go to 6)
 S  -> .A    b => (Shift and go to 8)
 A  -> .aSb  
 A  -> .ab   

 (5)
 S  -> SA.   [$b] => (reduce on $ or b)

 (6)
 A  -> a.Sb  S => (Go to 7)
 A  -> a.b   A => (Go to 3)
 S  -> .SA   a => (Shift and go to 4)
 S  -> .A    b => (Shift and go to 8)
 A  -> .aSb  
 A  -> .ab   

 (7)
 A  -> aS.b  A => (Go to 5)
 S  -> S.A   a => (Shift and go to 6)
 A  -> .aSb  b => (Shift and go to 10)
 A  -> .ab   

 (8)
 A  -> ab.   [$b] => (reduce on $ or b)

 (9)
 S  -> A.    [$b] => (reduce on $ or b)

 (10)
 A  -> aSb.  [$b] => (reduce on $ or b)