Next: LL(1) Grammars
Up: Parsing
Previous: Predictive parsing
THE IDEA.
Predictive parsing can be performed using a pushdown stack,
avoiding recursive calls.
 Initially the stack holds just the start symbol of the grammar.
 At each step a symbol X is popped from the stack:
 if X is a terminal symbol then it is matched with
lookahead and lookahead is advanced,
 if X is a nonterminal, then using lookahead and a parsing table
(implementing the FIRST sets)
a production is chosen and its right hand side is pushed onto the stack.
 This process goes on until the stack and the input string become empty.
It is useful to have an end_of_stack and an end_of_input
symbols. We denote them both by $.
Figure 8
shows the structure of nonrecursive predictive parsers.
For each nonterminal A and each token a
the entry M[A, a] of the parsing table contains either
an Aproduction generating sentences starting with a
or an errorentry.
Figure 8:
The structure of nonrecursive predictive parsers.

Example 17
Consider the grammar G given by:
S 

aAa  BAa  
A 

cA  bA  
B 

b 
The parsing table is:

a 
b 
c 
$ 
S 
S aAa 
S BAa 

S 
A 
A

A bA 
A cA


B 

B b 


where the empty slots correspond to errorentries.
Consider the parsing of the word
w = bcba.
Stack 
Remaining input 
action 
$S 
bcba$ 
choose
S BAa 
$aAB 
bcba$ 
choose
B b 
$aAb 
bcba$ 
match b 
$aA 
cba$ 
choose
A cA 
$aAc 
cba$ 
match c 
$aA 
ba$ 
choose
A bA 
$aAb 
ba$ 
match b 
$aA 
a$ 
choose
A 
$a 
a$ 
match a 
THE ALGORITHM.
Algorithm 5
COMPUTING THE FIRST SETS.
Recall that for any string of symbols the set FIRST()
satisfies the following conditions for every terminal a and every string of symbols
 FIRST()
V_{T} {}

a
iff a FIRST()

iff
FIRST().
For a symbol
X V_{T} V_{N} the set FIRST(X) can be computed as follows
Algorithm 6
Comments about the computation of FIRST(X) with Algorithm 6.
 The case where X is a terminal symbol is trivial.
 Assume from now on that X is a nonterminal.
The case where
X follows
immediately from the specifications of FIRST(X).
 Assume that there is a production of the form
X X_{1}X_{2}^{ ... }X_{k}
where
X_{1}, X_{2},...X_{k} are grammar symbols.
If
FIRST(X_{1}) then
the first letter of a word generated from
X_{1}X_{2}^{ ... }X_{k}
is the first letter of a word generated from X_{1} and thus
FIRST(X) = FIRST(X_{1}).
If
FIRST(X_{1}) but
FIRST(X_{2}) then
the first letter of a word generated from
X_{1}X_{2}^{ ... }X_{k}
is either the first letter of a word generated from X_{1}
or the first letter of a word generated from X_{2}.
Etc ...
This explains the nested for loop.
 The last if statement tells that if
belongs to all
FIRST(X_{i}) then
must be in FIRST(X).
This statement is necessary since the nested for loop cannot
add
to FIRST(X) even if
belongs to all
FIRST(X_{i}).
Algorithm 7
The principle of Algorithm 7
is similar to that of Algorithm 6.
 If
FIRST(X_{1}) then
the first letter of a word generated from
X_{1}X_{2}^{ ... }X_{k}
must be the first letter of a word generated from X_{1}.
 If
FIRST(X_{1}) but
FIRST(X_{2}) then
the first letter of a word generated from
X_{1}X_{2}^{ ... }X_{k}
is either the first letter of a word generated from X_{1}
or the first letter of a word generated from X_{2}.
 Etc ...

belongs to FIRST(
X_{1}X_{2}^{ ... }X_{k})
iff it belongs to each FIRST(X_{i}).
THE FOLLOW SETS. In order to give an algorithm
for building the parsing table we define for every A V_{N}
FOLLOW(A) = a V_{T} {$}  S$Aar  
(42) 
In other words FOLLOW(A) is the set of the terminals that can appear
immediately to the right of the nonterminal A in some sentential form.
Moreover $ belongs to FOLLOW(A) if A is the rightmost
symbol in some sentential form.
COMPUTING THE FOLLOW SETS.
Algorithm 8
The FOLLOW sets of all nonterminal symbols are computed together
by the following process:
 Initially all these sets are empty, except FOLLOW(S).
 There exist three rules that can increase FOLLOW(B)
for a given nonterminal B.
These rules are:
 if
(A B) then FOLLOW(B) :=
FIRST() {} FOLLOW(B)
 if
(A B) then FOLLOW(B) := FOLLOW(B) FOLLOW(A)
 if
(A B) and
then FOLLOW(B) := FOLLOW(B) FOLLOW(A)
 Let us call a pass the fact of trying to apply each rule to each nonterminal.
 Then the algorithm scheme can be stated as follows:
repeat perform a pass until this pass does not change
any of the FOLLOW sets.
 To implement this process in Algorithm 8 we use two boolean
auxiliary variables:
 done which becomes true when a pass could not increase any of the FOLLOW sets.
 building which becomes true during a pass if at least one FOLLOW set could
be increased.
 In the pseudocode of Algorithm 8 the value
 FOLLOW(B)  denotes the number
of elements of the set FOLLOW(B).
 One could wonder whether Algorithm 8 could run forever.
But it is easy to see that the process has to stop.
Indeed, each FOLLOW set contains at most t + 1 symbols
where t is the number of terminals.
So the number of passes is at most n(t + 1) where n is the
number of nonterminals (since each successful pass increases at least
by one the number of elements of at least one FOLLOW set).
COMPUTING THE PARSING TABLE.
Algorithm 9
Algorithm 9 consists of three main steps.
 The first for loop which initializes each entry of
the parsing table M to the empty set.
 The second for loop which fills the parsing table M
by using the following rules.
 If
A with
is a production and if a is a terminal such that
a FIRST()
then the production
A
is added to M[A, a].
 If
FIRST()
(which means
)
then the production
A
is added to M[A, b] for every
b FOLLOW(A).
In particular if
FIRST()
and
$ FOLLOW(A)
then the production
A
is added to M[A,$].
 The third for loop which sets to error every empty entry
of the parsing table M.
Example 19
Consider the following grammar (with terminals
+ ,*,(,), and nonterminals
T, E, E', F)
E 

TE' 
E' 

+ TE'  
T 

FT' 
T' 

*FT'  
F 

(E)  
The FIRST sets of the right side (and some of their prefixes)
of the productions are given by
FIRST(F) 
= 
{(,} 
FIRST(T) 
= 
{(,} 
FIRST(T') 
= 
{*,} 
FIRST(E) 
= 
{(,} 
FIRST(E') 
= 
{ + ,} 
FIRST(TE') 
= 
{(,} 
FIRST(FT') 
= 
{(,} 
FIRST((E)) 
= 
{(} 
FIRST(+ TE') 
= 
{ + } 
FIRST(*FT') 
= 
{*} 
The FOLLOW sets of the left side of the productions are given by
FOLLOW(E) 
= 
{),$} 
FOLLOW(E') 
= 
{),$} 
FOLLOW(T) 
= 
{ + ,),$} 
FOLLOW(T') 
= 
{ + ,),$} 
FOLLOW(F) 
= 
{ + ,*,),$} 


+ 
* 
( 
) 
$ 
E 
E TE' 


E TE' 


E' 

E' + TE' 


E' 
E' 
T 
T FT' 


T FT' 


T' 

T' 
T' *FT' 

T' 
T' 
F 
F 


F (E) 


Example 20
Consider the following grammar (with terminals
a, b, e, i, t and nonterminals S, S', E)
S 

i E t S S'  a 
S' 

e S  
E 

b 
The FIRST sets of the right side
of the productions are given by
FIRST(
i E t S S') 
= 
{i} 
FIRST(a) 
= 
{a} 
FIRST(e S) 
= 
{e} 
FIRST(
) 
= 
{} 
FIRST(b) 
= 
{b} 
Le's sketch the computation of the FOLLOW sets.
Recall that the rules are:
if 
A B 
then 
: = {} 
if 
A B 
then 
: = 
if 

then 
: = 

(43) 

Initialization 
S iEtSS' 
S iEtSS' 
FOLLOW(S) 
{$} 
{e,$} 
{e,$} 
FOLLOW(S') 


{e,$} 
FOLLOW(E) 

{t} 
{t} 
This leads to the following parsing table.

a 
b 
e 
i 
$ 
t 
S 
S a 


S iEtSS' 


S' 


S' 

S' 




S' eS 



E 

E b 




The entry M[S', e] contains both

S' eS (since
e FIRST(e S))

S' (since
FIRST(
)
and since
e FOLLOW(S'))
We know that this grammar is ambiguous and this ambiguity is shown by this choice
of productions when an e (else) is seen.
ERROR RECOVERY IN PREDICTIVE PARSING. A predictive parser attempts to match the nonterminals and the terminals
in the stack with the remaining input.
Therefore two types of conflicts can occur.
 Tconflict.
 A terminal appearing on top of the stack does not match the following
input token.
 Nconflict.
 For a nonterminal B on top of the stack and the lookahead token b
the entry M[B, b] of the parsing table is empty.
Panicmode recovery is based on the idea of skipping symbols
on the input string until a token in a selected set of synchronizing tokens appears.
These synchronizing sets should be chosen such that the parser recovers quickly
from errors that are likely to occur in practice.
Here are some strategies for the above conflict cases.
 Tconflict.
 Skip (= ignore and advance) the token in the input string.
Hence the synchronizing set conists here of all other tokens.
 Nconflict.
 Possible solutions.
 Skip (= ignore and advance) the token b in the input string.
 If M[B, b] is a blank entry labeled synch then skip (= pop and ignore)
the nonterminal B. (Strictly speaking and according to the above definition,
this is not a panicmode recovery, but quite close in the spirit.)
 Skip tokens from the input string until an element of FIRST(B)
is reached, then continue parsing normally.
So the synchronizing set here is FIRST(B).
 Skip tokens from the input string until an element of FOLLOW(B)
is reached, then skip B and continue parsing normally.
(Again this is a variation of panicmode recovery.)
 Delimiters such as ; in C can be added to the two previous synchronizing sets.
Next: LL(1) Grammars
Up: Parsing
Previous: Predictive parsing
Marc Moreno Maza
20041202