LL(1) Grammars in Compiler Design

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)

Rather than constructing a table to check for LL(1) Grammar, we can check for it using the following definition of LL(1) Grammar.

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.

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.