2/2/2024

Compiler Design (CD)

GTU # 2170701

Unit – 5
Top Down Parsing

 Topics to be covered
Looping

• Classification of parsing
• Backtracking
• LL(1) parsing
• Recursive Descent Paring

1
2/2/2024

Parsing
 Parsing is a technique that takes input string and produces output either a parse tree if string is
valid sentence of grammar, or an error message indicating that string is not a valid.
 Types of parsing are:
1. Top down parsing: In top down parsing parser build parse tree from top to bottom.
2. Bottom up parsing: Bottom up parser starts from leaves and work up to the root.

Classification of Parsing Methods

Parsing

Top down parsing Bottom up parsing (Shift reduce)

Back tracking Operator precedence

Parsing without
backtracking (predictive LR parsing
parsing)
LR (0)
LL(1) SLR

Recursive CLR
descent LALR

2
2/2/2024

Backtracking
 If one production of a non-terminal fails in deriving the input string. The parser has to go back
to the position where it has chosen the production. And start deriving the string again using
another production of the same nonterminal. This process may need repeated scans over the
input string and we refer to it as backtracking.

 Backtracking in top-down parsing provides flexibility to handle ambiguous grammars or

situations where the parser encounters uncertainty in choosing the correct production rule.
However, it can lead to inefficient parsing, especially when the grammar has many backtracking
points or when the input has long ambiguous sequences.

 Backtracking parsers are a type of top-down parser that can handle non-deterministic grammar.
When a parsing decision leads to a dead end, the parser can backtrack and try another
alternative. Backtracking parsers are not as efficient as other top-down parsers because they
can potentially explore many parsing paths.

Backtracking
 In backtracking, expansion of nonterminal symbol we choose one alternative and if any
mismatch occurs then we try another alternative.

 Grammar: S cAd Input string: cad

A ab | a

S S S

c A d c A d c A d
Make prediction Make prediction

a b Backtrack a Parsing done

3
2/2/2024

Backtracking
 Key Steps for Backtracking in a Top-Down Parser:

1. Choose a non-terminal: At each step, the parser chooses a non-terminal from the current production
rule to expand.
2. Apply a production: The parser selects a production rule for the chosen non-terminal that matches
the current input. If multiple choices are available, it may need to try each alternative.
3. Recursive expansion: The chosen production is recursively expanded by applying the rules to its
non-terminals. This process continues until a terminal symbol is reached or until further expansion is
not possible.
4. Backtrack on failure: If a selected production fails to match the input, the parser backtracks to the
previous decision point, undoing the previous expansion and selecting an alternative choice if
available.
5. Repeat until success or failure: The parser repeats the above steps, trying different alternatives
and backtracking as necessary until it either successfully matches the entire input or exhausts all
possible alternatives, resulting in a parsing error.

Backtracking
 Advantages of Backtracking:

1. Ambiguity Handling: Backtracking enables the parser to handle ambiguous grammars by

systematically exploring alternative choices and selecting the correct production rule.
2. Flexibility: By allowing alternative choices, backtracking provides flexibility in resolving parsing
ambiguities and making informed decisions during the parsing process.

 Disadvantages of Backtracking

1. Performance Impact: Backtracking can lead to inefficient parsing, particularly in cases where there
are numerous backtracking points or long ambiguous sequences in the input. In such scenarios,
alternative parsing techniques may be more efficient.
2. Complexity: Managing backtracking points and tracking alternative choices can introduce additional
complexity to the parsing algorithm, requiring careful implementation and optimization.

4
2/2/2024

Backtracking

First S --> rAd is chosen

then A-->y is chosen which is false So backtrack to A and verify other options (1st backtrack).

then A-->z is chosen which is false So backtrack to A and verify other options (2nd backtrack).

Since all options of A are verified now backtrack to S and choose S-->rB. (3rd backtrack )

then B-->zzd is chosen which is false So backtrack to B and verify other options (4th backtrack).

then B--ddz is chosen which we want.

So total 4 backtracks

Parsing Methods
Parsing

Top down parsing Bottom up parsing (Shift reduce)

Back tracking Operator precedence

Parsing without
backtracking (predictive LR parsing
parsing)
SLR
LL(1)
CLR
Recursive
descent LALR

5
2/2/2024

LL(1) parser (predictive parser)

 LL(1) is non recursive top down parser.
1. First L indicates input is scanned from left to right.
2. The second L means it uses leftmost derivation for input string
3. 1 means it uses only input symbol to predict the parsing process.

a + b $ INPUT

X
Predictive
Y
Stack parsing OUTPUT
Z program
$

Parsing table M

LL(1) parsing (predictive parsing)

Steps to construct LL(1) parser
1. Remove left recursion / Perform left factoring (if any).
2. Compute FIRST and FOLLOW of non terminals.
3. Construct predictive parsing table.
4. Parse the input string using parsing table.

6
2/2/2024

Rules to compute first of non terminal

1. If 𝐴 → 𝛼 and 𝛼 is terminal, add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴).
2. If 𝐴 → ∈, add ∈ to 𝐹𝐼𝑅𝑆𝑇(𝐴).
3. If 𝑋 is nonterminal and 𝑋𝑌1 𝑌2 … . 𝑌𝑘 is a production, then place 𝑎 in 𝐹𝐼𝑅𝑆𝑇(𝑋) if for some
𝑖, a is in 𝐹𝐼𝑅𝑆𝑇(𝑌𝑖), and 𝜖 is in all of 𝐹𝐼𝑅𝑆𝑇(𝑌1), … … … , 𝐹𝐼𝑅𝑆𝑇(𝑌𝑖−1 ); that is 𝑌1 … 𝑌𝑖−1 ⇒
𝜖. If 𝜖 is in 𝐹𝐼𝑅𝑆𝑇(𝑌𝑗) for all 𝑗 = 1,2, … . . , 𝑘 then add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝑋).
Everything in 𝐹𝐼𝑅𝑆𝑇(𝑌1) is surely in 𝐹𝐼𝑅𝑆𝑇(𝑋) If 𝑌1 does not derive 𝜖, then we do nothing
more to 𝐹𝐼𝑅𝑆𝑇(𝑋), but if 𝑌1 ⇒ 𝜖, then we add 𝐹𝐼𝑅𝑆𝑇(𝑌2) and so on.

Rules to compute first of non terminal

Simplification of Rule 3
If 𝐴 → 𝑌1 𝑌2 … … . . 𝑌𝐾 ,
• If 𝑌1 does not derives ∈ 𝑡ℎ𝑒𝑛, 𝐹𝐼𝑅𝑆𝑇(𝐴) = 𝐹𝐼𝑅𝑆𝑇(𝑌1 )
• If 𝑌1 derives ∈ 𝑡ℎ𝑒𝑛,
𝐹𝐼𝑅𝑆𝑇 𝐴 = 𝐹𝐼𝑅𝑆𝑇 𝑌1 − 𝜖 U 𝐹𝐼𝑅𝑆𝑇(𝑌2 )
• If 𝑌1 & Y2 derives ∈ 𝑡ℎ𝑒𝑛,
𝐹𝐼𝑅𝑆𝑇 𝐴 = 𝐹𝐼𝑅𝑆𝑇 𝑌1 − 𝜖 U 𝐹𝐼𝑅𝑆𝑇(𝑌2 ) − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌3 )
• If 𝑌1 , Y2 & Y3 derives ∈ 𝑡ℎ𝑒𝑛,
𝐹𝐼𝑅𝑆𝑇 𝐴 = 𝐹𝐼𝑅𝑆𝑇 𝑌1 − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌2 ) − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌3 ) − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌4 )
• If 𝑌1 , Y2 , Y3 …..YK all derives ∈ 𝑡ℎ𝑒𝑛,
𝐹𝐼𝑅𝑆𝑇 𝐴 = 𝐹𝐼𝑅𝑆𝑇 𝑌1 − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌2 ) − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌3 ) − 𝜖 𝑈 𝐹𝐼𝑅𝑆𝑇(𝑌4 ) −
𝜖 𝑈 … … … … 𝐹𝐼𝑅𝑆𝑇(𝑌𝑘 ) (note: if all non terminals derives ∈ then add ∈ to FIRST(A))

7
2/2/2024

Rules to compute FOLLOW of non terminal

1. Place $ 𝑖𝑛 𝑓𝑜𝑙𝑙𝑜𝑤 𝑆 . (S is start symbol)
2. If A → 𝛼𝐵𝛽 , then everything in 𝐹𝐼𝑅𝑆𝑇(𝛽) except for 𝜖 is placed in 𝐹𝑂𝐿𝐿𝑂𝑊(𝐵)
3. If there is a production A → 𝛼𝐵 or a production A → 𝛼𝐵𝛽 where 𝐹𝐼𝑅𝑆𝑇(𝛽) contains 𝜖 then
everything in F𝑂𝐿𝐿𝑂𝑊 𝐴 = 𝐹𝑂𝐿𝐿𝑂𝑊 𝐵

How to apply rules to find FOLLOW of non terminal?

A → 𝛼𝐵𝛽

𝛽 𝑖𝑠 𝑎𝑏𝑠𝑒𝑛𝑡 𝛽 𝑖𝑠 𝑝𝑟𝑒𝑠𝑒𝑛𝑡

𝑅𝑢𝑙𝑒 3 𝛽 is terminal 𝛽 𝑖𝑠 𝑁𝑜𝑛𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙

𝑅𝑢𝑙𝑒 2 𝛽 does not derives 𝜖 𝛽 derives 𝜖

𝑅𝑢𝑙𝑒 2 𝑅𝑢𝑙𝑒 2 + 𝑅𝑢𝑙𝑒 3

8
2/2/2024

Rules to construct predictive parsing table

1. For each production 𝐴 → 𝛼 of the grammar, do steps 2 and 3.
2. For each terminal 𝑎 in 𝑓𝑖𝑟𝑠𝑡(𝛼), Add 𝐴 → 𝛼 to 𝑀[𝐴, 𝑎].
3. If 𝜖 is in 𝑓𝑖𝑟𝑠𝑡(𝛼), Add 𝐴 → 𝛼 to 𝑀[𝐴, 𝑏] for each terminal 𝑏 in 𝐹𝑂𝐿𝐿𝑂𝑊(𝐵). If 𝜖 is in
𝑓𝑖𝑟𝑠𝑡(𝛼), and $ is in 𝐹𝑂𝐿𝐿𝑂𝑊(𝐴), add 𝐴 → 𝛼 to 𝑀[𝐴, $].
4. Make each undefined entry of M be error.

Example-1: LL(1) parsing

SaBa
BbB | ϵ
NT First
Step 1: Not required S {a}

Step 2: Compute FIRST B {b,𝜖}

First(S) S  a B a Rule 1
SaBa A  𝛼 add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴)
FIRST(S)={ a }

First(B)
BbB B𝜖

B  b B B  𝜖
Rule 1
A  𝛼 A  𝜖
add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) Rule 2
add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)
FIRST(B)={ b , 𝜖 }

9
2/2/2024

Example-1: LL(1) parsing

SaBa
BbB | ϵ NT First Follow
S {a} {$}
Step 2: Compute FOLLOW B {b,𝜖} {a}
Follow(S)
Rule 1: Place $ in FOLLOW(S)
Follow(S)={ $ }

Follow(B)
SaBa BbB

S  a B a Rule 2 B  b B Rule 3
A  𝛂 B 𝛃 First(β) − 𝜖 A  𝛂 B Follow(A)=follow(B)

Follow(B)={ a }

Example-1: LL(1) parsing

SaBa
BbB | ϵ NT First Follow
S {a} {$}
Step 3: Prepare predictive parsing table B {b,𝜖} {a}

NT Input Symbol
a b $
S SaBa
B

SaBa
Rule: 2
a=FIRST(aBa)={ a } A 𝛼
a = first(𝛼)
M[S,a]=SaBa M[A,a] = A 𝛼

10
2/2/2024

Example-1: LL(1) parsing

SaBa
BbB | ϵ NT First Follow
S {a} {$}
Step 3: Prepare predictive parsing table B {b,𝜖} {a}

NT Input Symbol
a b $
S SaBa
B BbB

BbB
Rule: 2
a=FIRST(bB)={ b } A 𝛼
a = first(𝛼)
M[B,b]=BbB M[A,a] = A 𝛼

Example-1: LL(1) parsing

SaBa
BbB | ϵ NT First Follow
S {a} {$}
Step 3: Prepare predictive parsing table B {b,𝜖} {a}

NT Input Symbol
a b $
S SaBa Error Error
B Bϵ BbB Error

Bϵ
Rule: 3
b=FOLLOW(B)={ a } A 𝛼
b = follow(A)
M[B,a]=B𝜖 M[A,b] = A 𝛼

11
2/2/2024

Example-2: LL(1) parsing

SaB | ϵ
BbC | ϵ
CcS | ϵ
Step 1: Not required
NT First
Step 2: Compute FIRST S { a, 𝜖 }
First(S) B {b,𝜖}
SaB S𝜖 C {c,𝜖}

S  a B S  𝜖
Rule 1 Rule 2
A  𝛼 add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) A  𝜖 add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)

FIRST(S)={ a , 𝜖 }

Example-2: LL(1) parsing

SaB | ϵ
BbC | ϵ
CcS | ϵ
Step 1: Not required
NT First
Step 2: Compute FIRST S { a,𝜖}
First(B) B {b,𝜖}
BbC B𝜖 C {c,𝜖}

B  b C B  𝜖
Rule 1 Rule 2
A  𝛼 add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) A  𝜖 add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)

FIRST(B)={ b , 𝜖 }

12
2/2/2024

Example-2: LL(1) parsing

SaB | ϵ
BbC | ϵ
CcS | ϵ
Step 1: Not required
NT First
Step 2: Compute FIRST S { a,𝜖}
First(C) B {b,𝜖}
CcS C𝜖 C {c,𝜖}

C  c S C  𝜖
Rule 1 Rule 2
A  𝛼 add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) A  𝜖 add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)

FIRST(B)={ c , 𝜖 }

Example-2: LL(1) parsing

Step 2: Compute FOLLOW
Follow(S) Rule 1: Place $ in FOLLOW(S)
Follow(S)={ $ }
CcS SaB | ϵ
BbC | ϵ
C  c S Rule 3 CcS | ϵ
A  𝛂 B Follow(A)=follow(B)
Follow(S)=Follow(C) ={$}
NT First Follow
S {a,𝜖} {$}
BbC SaB B {b,𝜖} {$}
C {c,𝜖} {$}
B  b C Rule 3 S  a B Rule 3
A  𝛂 B Follow(A)=follow(B) A  𝛂 B Follow(A)=follow(B)
Follow(C)=Follow(B) ={$} Follow(B)=Follow(S) ={$}

13
2/2/2024

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB
B
C

SaB Rule: 2
A 𝛼
a=FIRST(aB)={ a } a = first(𝛼)
M[S,a]=SaB M[A,a] = A 𝛼

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB S 𝜖
B
C

S𝜖 Rule: 3
A 𝛼
b=FOLLOW(S)={ $ } b = follow(A)
M[S,$]=S𝜖 M[A,b] = A 𝛼

14
2/2/2024

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB S 𝜖
B BbC
C

BbC Rule: 2
A 𝛼
a=FIRST(bC)={ b } a = first(𝛼)
M[B,b]=BbC M[A,a] = A 𝛼

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB S 𝜖
B BbC B𝜖
C

B𝜖 Rule: 3
A 𝛼
b=FOLLOW(B)={ $ } b = follow(A)
M[B,$]=B𝜖 M[A,b] = A 𝛼

15
2/2/2024

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB S 𝜖
B BbC B𝜖
C CcS

CcS Rule: 2
A 𝛼
a=FIRST(cS)={ c } a = first(𝛼)
M[C,c]=CcS M[A,a] = A 𝛼

Example-2: LL(1) parsing

SaB | ϵ
NT First Follow
BbC | ϵ
S {a,𝜖} {$}
CcS | ϵ
B {b,𝜖} {$}
Step 3: Prepare predictive parsing table C {c,𝜖} {$}

N Input Symbol
T a b c $
S SaB Error Error S 𝜖
B Error BbB Error B𝜖
C Error Error CcS C𝜖

C𝜖 Rule: 3
A 𝛼
b=FOLLOW(C)={ $ } b = follow(A)
M[C,$]=C𝜖 M[A,b] = A 𝛼

16
2/2/2024

Example-3: LL(1) parsing

EE+T | T
TT*F | F
F(E) | id
Step 1: Remove left recursion
ETE’
E’+TE’ | ϵ
TFT’
T’*FT’ | ϵ
F(E) | id

Example-3: LL(1) parsing

Step 2: Compute FIRST ETE’
First(E) E’+TE’ | ϵ
E  T E’ Rule 3 TFT’
ETE’ A  Y1 Y2 First(A)=First(Y1) T’*FT’ | ϵ
F(E) | id
FIRST(E)=FIRST(T) = {(, id }

NT First
First(T) E { (,id }
T  F T’ Rule 3
TFT’ E’
A  Y1 Y2 First(A)=First(Y1)
T { (,id }
FIRST(T)=FIRST(F)= {(, id } T’
First(F) F { (,id }
F(E) Fid
F  ( E ) F  id
A  𝛼 Rule 1 A  𝛼 Rule 1
add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴)
FIRST(F)={ ( , id }

17
2/2/2024

Example-3: LL(1) parsing

Step 2: Compute FIRST ETE’
First(E’) E’+TE’ | ϵ
TFT’
E’+TE’ T’*FT’ | ϵ
F(E) | id
E’  + T E’ Rule 1
add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) NT First
A  𝛼
E { (,id }

E’𝜖 E’ { +, 𝜖 }
T { (,id }
T’
E’  𝜖 Rule 2
F { (,id }
A  𝜖 add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)

FIRST(E’)={ + , 𝜖 }

Example-3: LL(1) parsing

Step 2: Compute FIRST ETE’
First(T’) E’+TE’ | ϵ
TFT’
T’*FT’ T’*FT’ | ϵ
F(E) | id
T’  * F T’ Rule 1
add 𝛼 to 𝐹𝐼𝑅𝑆𝑇(𝐴) NT First
A  𝛼
E { (,id }

T’𝜖 E’ { +, 𝜖 }
T { (,id }
T’ { *, 𝜖 }
T’  𝜖 Rule 2
F { (,id }
A  𝜖 add 𝜖 to 𝐹𝐼𝑅𝑆𝑇(𝐴)

FIRST(T’)={ * , 𝜖 }

18
2/2/2024

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(E) E’+TE’ | ϵ
TFT’
Rule 1: Place $ in FOLLOW(E) T’*FT’ | ϵ
F(E) | id
F(E)
NT First Follow
E { (,id } { $,) }
E’ { +, 𝜖 }
F  ( E ) Rule 2 T { (,id }
A  𝛂 B 𝛃
T’ { *, 𝜖 }
F { (,id }

FOLLOW(E)={ $, ) }

Example-3: LL(1) parsing

ETE’
Step 2: Compute FOLLOW E’+TE’ | ϵ
FOLLOW(E’) TFT’
T’*FT’ | ϵ
ETE’ F(E) | id
NT First Follow
E  T E’ Rule 3 E { (,id } { $,) }
A  𝛂 B
E’ { +, 𝜖 } { $,) }
T { (,id }
E’+TE’ T’ { *, 𝜖 }
F { (,id }
E’  +T E’ Rule 3
A  𝛂 B

FOLLOW(E’)={ $,) }

19
2/2/2024

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(T) E’+TE’ | ϵ
TFT’
ETE’ T’*FT’ | ϵ
F(E) | id
NT First Follow
E  T E’ Rule 2 E { (,id } { $,) }
A  𝛼 B 𝛃
E’ { +, 𝜖 } { $,) }
T { (,id }
T’ { *, 𝜖 }
F { (,id }
E  T E’ Rule 3
A  𝛼 B 𝛃

FOLLOW(T)={ +, $, )

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(T) E’+TE’ | ϵ
TFT’
E’+TE’ T’*FT’ | ϵ
F(E) | id
NT First Follow
E’  + T E’ Rule 2 E { (,id } { $,) }
A  𝛂 B 𝛃
E’ { +, 𝜖 } { $,) }
T { (,id } { +,$,) }
T’ { *, 𝜖 }
F { (,id }
E’  + T E’ Rule 3
A  𝛂 B 𝛃

FOLLOW(T)={ +, $, ) }

20
2/2/2024

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(T’) E’+TE’ | ϵ
TFT’
TFT’ T’*FT’ | ϵ
F(E) | id
NT First Follow
T  F T’ Rule 3 E { (,id } { $,) }
A  𝛂 B
E’ { +, 𝜖 } { $,) }
T’*FT’ T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
F { (,id }
T’  *F T’ Rule 3
A  𝛂 B

FOLLOW(T’)={+ $,) }

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(F) E’+TE’ | ϵ
TFT’
TFT’ T’*FT’ | ϵ
F(E) | id
NT First Follow
T  F T’ Rule 2 E { (,id } { $,) }
A  𝛂 B 𝛃
E’ { +, 𝜖 } { $,) }
T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
F { (,id }
T  F T’ Rule 3
A  𝛂 B 𝛃

FOLLOW(F)={ *, + ,$ , )

21
2/2/2024

Example-3: LL(1) parsing

Step 2: Compute FOLLOW ETE’
FOLLOW(F) E’+TE’ | ϵ
TFT’
T’*FT’ T’*FT’ | ϵ
F(E) | id
NT First Follow
T’  * F T’ Rule 2 E { (,id } { $,) }
A  𝛂 B 𝛃
E’ { +, 𝜖 } { $,) }
T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
F { (,id } {*,+,$,)}
T’  * F T’ Rule 3
A  𝛂 B 𝛃

FOLLOW(F)={ *,+, $, ) }

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ NT First Follow
T E { (,id } { $,) }
T’ E’ { +, 𝜖 } { $,) }
F T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
ETE’ F { (,id } {*,+,$,)}
Rule: 2
a=FIRST(TE’)={ (,id } A 𝛼
a = first(𝛼)
M[E,(]=ETE’ M[A,a] = A 𝛼
M[E,id]=ETE’

22
2/2/2024

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ NT First Follow
T E { (,id } { $,) }
T’ E’ { +, 𝜖 } { $,) }
F T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
E’+TE’ F { (,id } {*,+,$,)}
Rule: 2
a=FIRST(+TE’)={ + } A 𝛼
a = first(𝛼)
M[E’,+]=E’+TE’ M[A,a] = A 𝛼

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ E’𝜖 E’𝜖 NT First Follow
T E { (,id } { $,) }
T’ E’ { +, 𝜖 } { $,) }
F T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
E’𝜖 F { (,id } {*,+,$,)}
Rule: 3
b=FOLLOW(E’)={ $,) } A 𝛼
b = follow(A)
M[E’,$]=E’𝜖 M[A,b] = A 𝛼
M[E’,)]=E’𝜖

23
2/2/2024

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ E’𝜖 E’𝜖 NT First Follow
T TFT’ TFT’ E { (,id } { $,) }
T’ E’ { +, 𝜖 } { $,) }
F T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
TFT’ F { (,id } {*,+,$,)}
Rule: 2
a=FIRST(FT’)={ (,id } A 𝛼
a = first(𝛼)
M[T,(]=TFT’ M[A,a] = A 𝛼
M[T,id]=TFT’

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ E’𝜖 E’𝜖 NT First Follow
T TFT’ TFT’ E { (,id } { $,) }
T’ T’*FT’ E’ { +, 𝜖 } { $,) }
F T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
T’*FT’ F { (,id } {*,+,$,)}
Rule: 2
a=FIRST(*FT’)={ * } A 𝛼
a = first(𝛼)
M[T’,*]=T’*FT’ M[A,a] = A 𝛼

24
2/2/2024

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
NT Input Symbol TFT’
id + * ( ) $ T’*FT’ | ϵ
E ETE’ ETE’ F(E) | id

E’ E’+TE’ E’𝜖 E’𝜖

NT First Follow
T TFT’ TFT’
E { (,id } { $,) }
T’ T’𝜖 T’*FT’ T’𝜖 T’𝜖
E’ { +, 𝜖 } { $,) }
F
T { (,id } { +,$,) }
T’𝜖 T’ { *, 𝜖 } { +,$,) }
b=FOLLOW(T’)={ +,$,) } F { (,id } {*,+,$,)}
Rule: 3
M[T’,+]=T’𝜖 A 𝛼
b = follow(A)
M[T’,$]=T’𝜖 M[A,b] = A 𝛼
M[T’,)]=T’𝜖

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ E’𝜖 E’𝜖 NT First Follow
T TFT’ TFT’ E { (,id } { $,) }
T’ T’𝜖 T’*FT’ T’𝜖 T’𝜖 E’ { +, 𝜖 } { $,) }
F F(E) T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
F { (,id } {*,+,$,)}
Rule: 2
F(E) A 𝛼
a = first(𝛼)
a=FIRST((E))={ ( } M[A,a] = A 𝛼
M[F,(]=F(E)

25
2/2/2024

Example-3: LL(1) parsing

Step 3: Construct predictive parsing table ETE’
E’+TE’ | ϵ
TFT’
NT Input Symbol
T’*FT’ | ϵ
id + * ( ) $ F(E) | id
E ETE’ ETE’
E’ E’+TE’ E’𝜖 E’𝜖 NT First Follow
T TFT’ TFT’ E { (,id } { $,) }
T’ T’𝜖 T’*FT’ T’𝜖 T’𝜖 E’ { +, 𝜖 } { $,) }
F Fid F(E) T { (,id } { +,$,) }
T’ { *, 𝜖 } { +,$,) }
F { (,id } {*,+,$,)}
Rule: 2
Fid A 𝛼
a = first(𝛼)
a=FIRST(id)={ id } M[A,a] = A 𝛼
M[F,id]=Fid

Example-3: LL(1) parsing

 Step 4: Make each undefined entry of table be Error
NT Input Symbol
id + * ( ) $
E ETE’ Error Error ETE’ Error Error
E’ Error E’+TE’ Error Error E’𝜖 E’𝜖
T TFT’ Error Error TFT’ Error Error
T’ Error T’𝜖 T’*FT’ Error T’𝜖 T’𝜖
F Fid Error Error F(E) Error Error

26
2/2/2024

Recursive Descent Parsing

 A top down parsing that executes a set of recursive procedure to process the input without
backtracking is called recursive descent parser.
 There is a procedure for each non terminal in the grammar.
 Consider RHS of any production rule as definition of the procedure.
 As it reads expected input symbol, it advances input pointer to next position.

27
2/2/2024

Example: Recursive descent parsing

Procedure E Procedure T Proceduce Match(token t)
{ { {
If lookahead=num If lookahead=’*’ If lookahead=t
{ { lookahead=next_token;
Match(num); Match(‘*’); Else
T(); If lookahead=num Error();
} { }
Else Match(num);
Error(); T(); Procedure Error
If lookahead=$ } {
{ Else Print(“Error”);
Declare success; Error(); }
}
Else }
Error(); Else
} NULL E num T
} T * num T | 𝜖
3 * 4 $ Success

Example: Recursive descent parsing

Procedure E Procedure T Proceduce Match(token t)
{ { {
If lookahead=num If lookahead=’*’ If lookahead=t
{ { lookahead=next_token;
Match(num); Match(‘*’); Else
T(); If lookahead=num Error();
} { }
Else Match(num);
Error(); T(); Procedure Error
If lookahead=$ } {
{ Else Print(“Error”);
Declare success; Error(); }
}
Else }
Error(); Else
} NULL E num T
} T * num T | 𝜖
3 * 4 $ Success 3 4 * $ Error

28
1
2
3
4
5
6
7