Left recursion in LR(1) parsers

context-free-grammar, lr-grammar, parsing

Solution

LR(1) parsers can handle some types of left recursion, though not all left-recursive grammars are LR(1).

Let's see if your particular grammar is LR(1). Augmenting the grammar gives

S' → S

S → SA | A

A → aSb | ab

Our configurating sets are therefore

 (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)

There are no shift/reduce or reduce/reduce conflicts in this grammar, and so it should be LR(1) (unless I made a mistake somewhere!)

Hope this helps!

Problem

Can a LR(1) parser parse a grammar of this type? ``` S -> SA | A A -> aSb | ab ``` I'm trying to write a Java program that implements this type of parser, but I only get the right results on a grammars without left recursion.

Original source