LL(1) or Table Driver or Predictive Parser

1. In LL1, the first L stands for Left to Right, and the second L stands for Left-most Derivation. 1 stands for the number of Looks Ahead tokens used by the parser while parsing a sentence.
2. LL(1) parsing is constructed from the grammar which is free from left recursion, common prefix, and ambiguity.
3. LL(1) parser depends on 1 look ahead symbol to predict the production to expand the parse tree.
4. This parser is Non-Recursive

Construction of LL(1)predictive parsing table 

For each production A -> α repeat the following steps: 

• Add A -> α under M[A, b] for all b in FIRST(α) 
• If FIRST(α) contains ε then add A -> α under M[A,c] for all c in FOLLOW(A). 
• Size of parsing table = (No. of terminals + 1) * #variables 

Example:  

Consider the grammar 
S → (L) | a 
L → SL’ 
L’ → ε | SL’ 

For any grammar, if M has multiple entries then it is not LL(1) grammar.

Example:
S → iEtSS’/a 
S’ →eS/ε 
E → b 

Important Notes

If a grammar contains left factoring then it can not be LL(1). 

Eg - S -> aS | a      
---- both productions go in a

If a grammar contains left recursion it can not be LL(1)

 Eg - S -> Sa | b 
      S -> Sa goes to FIRST(S) = b
      S -> b goes to b, thus b has 2 entries hence not LL(1)

 If the grammar is ambiguous then it can not be LL(1).

 Every regular grammar need not be LL(1) because regular grammar may contain left factoring, left recursion or ambiguity. 

Parsing is classified into two categories, i.e. Top-Down Parsing, and Bottom-Up Parsing. Top-Down Parsing is based on Left Most Derivation whereas Bottom-Up Parsing is dependent on Reverse Right Most Derivation. 

The process of constructing the parse tree which starts from the root and goes down to the leaf is Top-Down Parsing. 

1. Top-Down Parsers constructs from the Grammar which is free from ambiguity and left recursion.
2. Top-Down Parsers use leftmost derivation to construct a parse tree.
3. It does not allow Grammar With Common Prefixes.