LL(1) Grammars
- When we construct predictive parsing table for some grammars, the table may have some multiply defined entries. This happens when the given grammar is left recursive or ambiguous
- A grammar whose predictive parser has no multiply defined entries is known as LL(1) grammar
- LL(1) means left to right scan of the input to generate the left most derivation by using 1 symbol of look ahead (can be extended to k symbol look ahead)
Definition:
A grammar G is LL(1) if and only if whenever A → α | β are two distinct productions of G then the following three conditions hold.
For no terminal a do α and β derive strings beginning with a
At most one of α and β can derive ε
If β⇒* ε, then α does not derive any string beginning with a terminal in FOLLOW(A)
Note: No LL(1) grammar can be ambiguous.
