Search code examples
parsingcompiler-constructiongrammarcontext-free-grammarlr-grammar

Is this grammar LR(1)?

A bit confused about whether this grammar is ambiguous or not

C' -> C
C -> d C u C
C -> d C
C -> ε

I tried building the DFA for this but I get this in one of the states:

C -> d C DOT u C, $
C -> d C DOT, $

Isn't this a shift-reduce conflict, so surely it means the grammar is not LR(1)? Or does it reduce regardless since $ and u are both in the follow set of C?

Solution

  • It does have a shift-reduce conflict. Here's the state machine produced by selecting shift. The conflict is in state 4. state machine

    I should point out that your question is a bit off. A grammar can be unambiguous and still not LR(1).

    But this one happens to be provably ambiguous. Consider the string ddudu. Two leftmost derivations are

    C'->C->dCuC->ddCuCuC->dduCuC->ddudCuC->dduduC->ddudu
C'->C->dCuC->ddCuC->dduC->ddudCuC->dduduC->ddudu

    The existence of these says the grammar is ambiguous.

    Proving a general grammar ambiguous is an undecidable problem: there can be no algorithm for it. Happily this one is not so hard to sort out.