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.
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!