SYNTAX ANALYSIS
LECTURE 3 - 4
Top-Down Parsing
Recursive Descent Parsing
CONTENT Concepts of FIRST and FOLLOW
Examples
Can be viewed as a problem of constructing a parse
tree for the input string
TOP DOWN It starts from the root and create nodes of the parse
PARSING tree in pre order (Depth First)
Equivalently can be viewed as a leftmost derivation
Example:
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|id
Leftmost Derivation of string id + id * id
TOP DOWN E → TE'
→ FT'E'
PARSING → idT'E'
→ id e E'
→ id + TE'
→ id + FT'E'
→ id + id T'E'
→ id + id * F T' E'
→ id + id * id T' E'
→ id + id * id e E'
→ id + id * id e e
At each of the step the key problem is that Determining
the production to be applied for a nonterminal say A
TOP DOWN
Once an A production is chosen the rest of the parsing
PARSING process consists of matching the terminal symbols in
the production body with the input string
void A ( )
{
Choose an A pro duction A → X1 X2 … Xk
For ( i to k)
RECURSIVE {
if (Xi is a nonterminal)
DESCENT call procedure Xi ( );
PARSING else if (Xi equals the current input symbol a)
advance the input to the next symbol
else
an error has occurred
}
}
A recursive descent parsing program consists of a set of
procedures one for each nonterminal
Execution begins with the procedure for the start symbol
RECURSIVE The execution halts and announces success if its procedure
DESCENT body scans entire input string.
PARSING Note that this pseudo code is nondeterministic since it begins
by choosing the A production to apply in a manner that is not
specified
Backtracking is required
Consider the grammar
S→cAd
RECURSIVE A→ab|a
DESCENT
PARSING Derivation of string w = cad
If you go with S → cAd and then A → ab it leads to wrong string.
S → cabd
Backtracking is necessary
If X is a terminal then FIRST (X) = X
If X is a nonterminal and
X → Y1 Y2 … Yk is a production for some k >=1
Case 1:
a. if for some i, 'a' is in FIRST( Yi ) and
FIRST OF
GRAMMAR b. epsilon is in all of FIRST Yj where j = 1, 2, … i –1
Then add 'a' in the FIRST(X)
Case 2:
If epsilon is in FIRST(Yj) for all j = 1, 2, … , k
then add epsilon in FIRST (X)
If X → e is a production then add epsilon in FIRST(X)
Example 1:
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|id
FIRST OF Solution:
GRAMMAR
FIRST(E) = FIRST(T) = FIRST(F) = { (, id}
FIRST(E') = { +, ε }
FIRST(T) = FIRST (F) = { (, id }
FIRST (T') = { *, ε }
FIRST (F) = { (, id }
Example 2
A -> BC
B -> Ax | x
C -> yC | y
Solution
FIRST OF
In A-> BC
GRAMMAR FIRST(A)={FIRST(B) U FIRST (C)} if B -> Є is true
FIRST(A)={FIRST(B)} if B -> Є is false
FIRST(A) = {x}
FIRST(B) = {x}
FIRST(C) = {y}
Rule 1:
Place $ in FOLLOW (S) where S is the start symbol and $ is the
input right endmarker
Rule 2:
If there is a production A -> αBβ then everything in FIRST(β) except
FOLLOW OF
ε is in FOLLOW (B)
GRAMMAR
Rule 3:
If there is a production A -> αB or
a production A -> αBβ where FIRST(β) contains ε
then everything in FOLLOW (A) is in FOLLOW (B)
APPLY ABOVE RULES UNTIL THERE IS NO UPDATION IN
FOLLOW LIST
FOLLOW OF GRAMMAR
Example 1:
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|id
FIRST FOLLOW
Solution:
E ( , id $,)
1. FOLLOW (E) = { $, ) }
E' +,ε $,)
T ( , id Since E is start symbol and Production Rule F → (E)
T' *,ε 2. FOLLOW (E') = FOLLOW (E) = { $, ) }
F ( , id
By Rule 3 of FOLLOW
FOLLOW OF GRAMMAR Example 1:
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|id
FIRST FOLLOW Solution:
E ( , id $,) 3. FOLLOW (T) = { FIRST (E') - ε } U { FOLLOW (E') }
E' +,ε $,)
={+}U{$,)}
T ( , id +,$,)
={+,$,)}
T' *,ε +,$,)
4. FOLLOW (T') = FOLLOW (T)
F ( , id
={+,$,)}
FOLLOW OF GRAMMAR
Example 1:
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
FIRST FOLLOW F→(E)|id
E ( , id $,) Solution:
E' +,ε $,)
5. FOLLOW (F) = { FIRST (T') - ε } U { FOLLOW (T') }
T ( , id +,$,)
={*}U{+,$,)}
T' *,ε +,$,)
={*,+,$,)}
F ( , id *,+,$,)
FOLLOW OF GRAMMAR
Example 2:
A -> BC
B -> Ax | x
C -> yC | y
Solution:
FIRST FOLLOW 1. FOLLOW (A) = { $ } U FIRST (x) … As A is the start symbol
A x $,x = {$,x}
B x y 2. FOLLOW (B) = FIRST (C)
C y $,x ={y}
3. FOLLOW (C) = FOLLOW (A)
={$,x}
FOLLOW OF GRAMMAR Example 3:
S → ACB | Cbb | Ba
A → da | BC
B→g|ε
C→h|ε
Solution:
1. FIRST (S) = FIRST (A) U FIRST (C) U FIRST (B) U FIRST (b)
FIRST FOLLOW
U FIRST (a)
S d, g, h, b,
a, ε = { d, g, h } U { h , ε } U { g , ε } U { b , a }
A d,g,h,ε = { d , g , h , b, a, ε }
B g, ε 2. FIRST (A) = FIRST (d) U FIRST (B) U FIRST (C)
={d,g,h,ε}
C h,ε
3. FIRST (B) = { g , ε }
4. FIRST (C) = { h , ε }
FOLLOW OF GRAMMAR
Example 3:
S → ACB | Cbb | Ba
A → da | BC
B→g|ε
C→h|ε
Solution:
FIRST FOLLOW 1. FOLLOW (S) = { $ } … Since S is start symbol
S d, g, h, b, $ 2. FOLLOW (A) = { FIRST (C) - ε } U { FIRST (B) - ε } U FOLLOW (S)
a, ε ={h,g,$}
A d,g,h,ε h,g,$ 3. FOLLOW (B) = FIRST (a) U { FIRST (C) - ε } U FOLLOW (A) U FOLLOW (S)
B g, ε a,h,g,$ ={a,h,g,$}
C h,ε b,h,g,$ 3. FOLLOW (C) = FIRST (b) U { FIRST(B) - ε } U FOLLOW (A)
= { b , g , h, $ }
Example 4:
FOLLOW OF GRAMMAR
S → ABD
A → a | BSB
B→b|D
D→d|ε
Solution:
1. FIRST (S) = FIRST (A)
= { a } U FIRST (B)
FIRST FOLLOW
= { a } U { b } U FIRST (D)
S a,b,d,ε ={a,b,d,ε}
A a,b,d,ε 2. FIRST (A) = { a } U FIRST (B)
B b,d,ε = { a } U { b } U FIRST (D)
={a,b,d,ε}
D d,ε
3. FIRST (B) = { b } U FIRST (D)
={b,d,ε}
4. FIRST (D) = { d , ε }
Example 4:
FOLLOW OF GRAMMAR
S → ABD
A → a | BSB
B→b|D
D→d|ε
Solution:
1. FOLLOW (S) = { $ } U { FIRST (B) - ε } U FOLLOW (A)
= { $ , b , d } U { FIRST (B) - ε } U { FIRST (D) - ε }
FIRST FOLLOW
={b,d,$}
S a,b,d,ε b,d,$
2. FOLLOW (A) = { FIRST (B) - ε } U { FIRST (D) - ε } U FOLLOW (S)
A a,b,d,ε b,d,$ ={b,d,$}
B b,d,ε a,b,d,$ 3. FOLLOW (B) = {FIRST (D) - ε } U FOLLOW (S) U {FIRST (S) - ε } U FOLLOW (A)
D d,ε a,b,d,$ = { d, b, a, $ }
3. FOLLOW (D) = FOLLOW (B) U FOLLOW (S)
={a,b,d,$}