## Recent Post

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