Search code examples
javaparsingcontext-free-grammarlr1

This parser generator says that this grammar isn't LR(1) but I have my doubts

I've written a parser generator in Java, after a few bumps (an early version didn't particularly like left recursion for example), I managed to make it work with some simple grammars (so i can verify by hand the productions are correct) I tried feeding it a more complex grammar and the output is that it isn't a LR(1) grammar (derived from the fact that the parsed tried to write twice on the same cell in the parsing table)

the grammar in question is

S->aAb|SA
A->aA|e|S

I'm pretty sure this grammar is LR(1), anyhow, here is the output of my program http://pastebin.com/hJNC9uuN

Any advice will be most precious Thanks (even better if someone has a parser generator that output the automaton and parse table so i can confront them)

Solution

  • This grammar can't be LR(1) because it's ambiguous. Here are two ways of deriving the string ab:

    S → aAb → ab

    S → SA → aAbA → abA → ab

    Your LR(1) sets actually contain a shift/reduce conflict. Check out State 5, which includes these items:

    [A->S. { $a }]
[A->.aA { $a }]

    This is a shift/reduce conflict: do you shift on a, or do you reduce on a? Therefore, the tool looks right on this input: the grammar isn't LR(1), and it's finding that it isn't LR(1).

    Hope this helps!