Why is this grammar not LL(1)

Question

I have the next grammar:

C := (PZ)
P := X | C
X := iQ | eQ | rQ
Q := AX | ε
A := +
L :=  >
Z := LP | AP | ε

and i am using JFLAP to build an LL(1) parsing table, but at the moment that i type those rules, JFLAP throws me an error that says: the grammar is not LL(1).I have found where the mistake is, in the rule 'Q'.

The first set of Q is Q = {+,ε}, and the follow set of Q is Q = { ), + , >} and in the parsing table i am going to have two rules in table[Q,+] and that´s the mistake, but i dont know how to fix it because i need to have the rule Q -> ε

Chris Dodd Chris Dodd · Accepted Answer · 2014-11-05T03:36:18

The basic problem is that your grammar is ambiguous -- you have two nested repeating patterns from your rules for X and Z and both of them can match an i+i fragment. So you need to decide how you want to resolve that ambiguity -- which way should a fragment like i+i match:

         PZ                          PZ
        /  \                        /  \
       X    ε                      X    AP
      / \                         / \  /  \
     i   Q                       i  Q  +   X
        / \                        /      / \
       A   X                      ε      i   Q
      /   / \                                |
     +   i   Q                               ε
             |
             ε

The easiest fix is to make it always match the right example, which you can do by just getting rid of the X/Q repeating pattern:

C := (PZ)
P := X | C
X := i | e | r
A := +
L :=  >
Z := LP | AP | ε

If you want to always match the left example, you need to disallow + in the Z pattern:

C := (PZ)
P := X | C
X := iQ | eQ | rQ
Q := AX | ε
A := +
L :=  >
Z := LP | ε

Why is this grammar not LL(1)

1 Answers