Top Down Parsing ( TDP )

TOP DOWN PARSING

1. Recursive-descent parsing :
   (i) Follows Brute Force mechanism ( Suffers from Backtracking ).
   (ii) Not efficient , general purpose , not widely used.
2. Predictive parsing :
   It can uniquely choose a production rule by just looking the current symbol.
   (i) Recursive predictive parsing : each non terminal corresponds to a procedure.
   (ii) Non-recursive predictive parsing : Table driven also called as LL(1).

LL(1) Parser/Predictive Parser

- LL(1) grammar is unambiguous , left factored and non left recursive.
- Top down parser follows left most derivation.

      L                                                          L                                  (1)
        ↓                                                           ↓                                    ↓
 Number of Look Ahead Symbol=1    Left Most Derivation    Left to Right Scanning



FIRST (A) is a set of the terminal symbols which occur as first symbols in string derived from A.
Follow (A) is the set of terminals which occur immediately after the non-terminal A in the strings derived from the starting symbol.

Configuration of LL(1) Parser

LL(1) Parsing Table Construction

 First ( ) and Follow ( ) sets are used to construct LL(1) parsing table.
For each rule A →α in grammar G:
  (i) For each terminal 'a' contained in FIRST (A)
       add A →α to [ A , a] entry in parsing table if α derives 'a' as the first symbol.
  (ii) If FIRST(A) contain 'ε' for each terminal 'b' in FOLLOW ( A) , add A→ε to [A,b] entry in parsing table.

  LL(1) Grammar
    A grammar where its LL(1) parsing table has free from multiple entries is said to be LL(1) grammar.
A left recursive grammar cannot be a LL(1) grammar.
If a grammar is not left factored,it cannot be a LL(1)
An ambiguous grammar can not be a LL(1) grammar