# 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) 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.

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.

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

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

## No comments