1
Syntax Analysis
Part I
Chapter 4
2
Left Factoring
• When a nonterminal has two or more productions
whose right-hand sides start with the same
grammar symbols, the grammar is not LL(1) and
cannot be used for predictive parsing
• Replace productions
A 1 | 2 | … | n |
with
A AR |
AR 1 | 2 | … | n
3
Predictive Parsing
• Eliminate left recursion from grammar
• Left factor the grammar
• Compute FIRST and FOLLOW
• Two variants:
– Recursive (recursive calls)
– Non-recursive (table-driven)
• Wait for definition of LL(1)
4
Computing First(X) : All Grammar Symbols
Informally, suppose we want to compute
First(X1 X2 … Xn ) = First (X1) “+”
First(X2) if is in First(X1) “+”
First(X3) if is in First(X2) “+”
…
First(Xn) if is in First(Xn-1)
Note 1: Only add to First(X1 X2 … Xn) if
is in First(Xi) for all i
Note 2: For First(X1), if X1 Z1 Z2 … Zm ,
then we need to compute First(Z1 Z2 … Zm) !
5
Computing First(X) : All Grammar Symbols
1. If X is a terminal, First(X) = {X}
2. If X is a production rule, add to First(X)
3. If X is a non-terminal, and X Y1Y2…Yk is a production rule
Place First(Y1) in First(X)
*
if Y1 , Place First(Y2) in First(X)
if Y2
* , Place First(Y3) in First(X)
…
* ,
if Yk-1 Place First(Yk) in First(X)
NOTE: As soon as Yi
* , Stop.
Repeat above steps until no more elements are added to any First(
) set.
Checking “Yj * ?” essentially amounts to checking whether
belongs to First(Yj)
6
Computing FIRST (Revisited)
• FIRST() = the set of terminals that begin all strings
derived from
FIRST(a) = {a} if a T
FIRST() = {}
FIRST(A) = A FIRST() for A P
FIRST(X1X2…Xk) =
if for all j = 1, …, i-1 : FIRST(Xj) then
add non- in FIRST(Xi) to FIRST(X1X2…Xk)
if for all j = 1, …, k : FIRST(Xj) then
add to FIRST(X1X2…Xk)
7
Example 3: Computing First
Given the production rules:
i E t SS’ = If E then S S’ = If E then S Else S
S’ = Else S
S i E t SS’ | a
S’ eS |
E b
Verify that
First(S) = { i, a }
First(S’) = { e, }
First(E) = { b }
8
Example 4
Computing First for: E TE’
E’ + TE’ |
T FT’
T’ * FT’ |
F ( E ) | id
9
Example 4 Computing First
Computing First for: E TE’
E’ + TE’ |
T FT’
T’ * FT’ |
F ( E ) | id
First(TE’)
First(T) “+” First(E’)
First(E) *
Not First(E’) since T
First(T)
First(F) “+” First(T’) First(F) Not First(T’) since F
*
First((E)) “+” First(id) “(“ and “id”
Overall: First(E) = { ( , id } = First(F)
First(E’) = { + , } First(T’) = { * , }
First(T) First(F) = { ( , id }
10
Computing Follow(A) : All Non-Terminals
1. Place $ in Follow(S), where S is the start symbol and $ signals end
of input
2. If there is a production A B, then everything in First() is in
Follow(B) except for .
3. If A B is a production, or A B and * (First()
contains ), then everything in Follow(A) is in Follow(B)
Whatever followed A must follow B, since nothing follows B
from the production rule.
We’ll calculate Follow for two grammars.
11
More Formal Way of Computing
FOLLOW
• FOLLOW(A) = the set of terminals that can
immediately follow nonterminal A
FOLLOW(A) =
for all (B A ) P do
add FIRST()\{} to FOLLOW(A)
for all (B A ) P and FIRST() do
add FOLLOW(B) to FOLLOW(A)
for all (B A) P do
add FOLLOW(B) to FOLLOW(A)
if A is the start symbol S then
add $ to FOLLOW(A)
12
Computing Follow : Example 5
Recall: S i E t SS’ | a First(S) = { i, a }
S’ eS | First(S’) = { e, }
E b First(E) = { b }
Follow(S) – Contains $, since S is start symbol
Since S i E t SS’ , put in First(S’) – not
Since S’
* , Put in Follow(S)
Since S’ eS, put in Follow(S’) So…. Follow(S) = { e, $ }
Follow(S’) = Follow(S) HOW?
Follow(E) = { t }
13
Example 6
Compute Follow for: E TE’
E’ + TE’ |
T FT’
T’ * FT’ |
F ( E ) | id
14
Example 6: First and Follows
Already Computed
Compute Follow for: E TE’
E’ + TE’ |
T FT’
T’ * FT’ |
F ( E ) | id
First Follow
E ( id E $)
E’ + E’ $)
T ( id T +$)
T’ * T’ +$)
F ( id F +*$)
15
Constructing Parsing Table
Algorithm:
1. Repeat Steps 2 & 3 for each rule A
2. Terminal a in First(): Add A to M[A, a ]
3. a) in First(): Add A to M[A, b ] for all
terminals b in Follow(A).
b) in First() and $ in Follow(A): Add A to M[A, $ ]
4. All undefined entries are errors.
16
Constructing a Predictive Parsing
Table: More Formal Way
for each production A do
for each a FIRST() do
add A to M[A,a]
enddo
if FIRST() then
for each b FOLLOW(A) do
add A to M[A,b]
enddo
endif
enddo
Mark each undefined entry in M error
17
Constructing Parsing Table – Example 7
S i E t SS’ | a First(S) = { i, a } Follow(S) = { e, $ }
S’ eS | First(S’) = { e, } Follow(S’) = { e, $ }
E b First(E) = { b } Follow(E) = { t }
18
Constructing Parsing Table – Example 7
S i E t SS’ | a First(S) = { i, a } Follow(S) = { e, $ }
S’ eS | First(S’) = { e, } Follow(S’) = { e, $ }
E b First(E) = { b } Follow(E) = { t }
S i E t SS’ Sa Eb
First(i E t SS’)={i} First(a) = {a} First(b) = {b}
S’ eS S
First(eS) = {e} First() = {} Follow(S’) = { e, $ }
Non- INPUT SYMBOL
terminal a b e i t $
S S a S iEtSS’
S’ S’
S’ eS S’
E E b
19
Constructing Parsing Table – Example 8
E TE’ First(E,F,T) = { (, id } Follow(E,E’) = { ), $}
E’ + TE’ |
T FT’ First(E’) = { +, } Follow(F) = { *, +, ), $ }
T’ * FT’ | First(T’) = { *, } Follow(T,T’) = { +, ) , $}
F ( E ) | id
Expression Example: E TE’ : First(TE’) = First(T) = { (, id }
M[E, ( ] : E TE’
by rule 2
M[E, id ] : E TE’
(by rule 2) E’ +TE’ : First(+TE’) = + : M[E’, +] : E’ +TE’
(by rule 3) E’ : in First( ) T’ : in First( )
M[E’, )] : E’ (3.1) M[T’, +] : T’ (3.1)
M[E’, $] : E’ (3.2) M[T’, )] : T’ (3.1)
(Due to Follow(E’) M[T’, $] : T’ (3.2)
20
Example 8
E TE’
E’ + TE’ |
T FT’ Our well-worn example !
T’ * FT’ |
F ( E ) | id
First(E,F,T) = { (, id } Follow(E,E’) = { ), $}
First(E’) = { +, } Follow(F) = { *, +, ), $ }
Table M First(T’) = { *, } Follow(T,T’) = { +, ) , $}
Non- INPUT SYMBOL
terminal
id + * ( ) $
E ETE’ ETE’
E’ E’+TE’ E’ E’
T TFT’ TFT’
T’ T’ T’*FT’ T’ T’
F Fid F(E)
