Non Recursive Predictive

Parsing

Lecture 10
Topics Covered in Lecture 9
 A general form of top-down parsing where
backtracking may be involved.
 Why does Recursive Descent Parser fail at
particular conditions ?
 Predictive Parsing is a special case of recursive
descent parsing that needs no back tracking
 Transition Diagrams as a plan for predictive
parsing
 Optimizing Transition Diagrams
3
 Non Recursive Predictive Parser/ LL(k) Parser

 It is possible to build a non recursive

predictive parser by maintaining a stack
explicitly
 Key problem with predictive parsing –
determining the production to be applied
for a non terminal

4
Table-driven parsing vs. recursive
descent parsing

 Recursive descent: every production is a

procedure. Implicit stack holds active procedures
corresponding to pending non-terminals.

 Table-driven parser: recursion simulated with

explicit stack.

5
 Predictive Parsing using a Parsing Table
Model

a + b $ Input buffer
stack

Output stream
Y Predictive Parser
Z

Parsing table M

6
 Non Recursive Predictive Parser/ LL(k) Parser

 Non recursive parser looks up the production to be

applied by looking up a parsing table
 Input buffer contains the string to be parsed; $ - end of
input marker
 Stack contains a sequence of grammar symbols with $
on the bottom, indicating the bottom of stack
 Initially, stack contains the start symbol of the grammar
on the top of $
 Parsing table is a two-dimentional array M[A,a] where:
 A  Non terminal
 a  Terminal or the symbol $

7
 Non Recursive Predictive Parser/ LL(k) Parser

 For a grammar to be suitable for predictive parsing, it

has to be an LL(k) grammar
 The two LL stands for Left-to-Right scan of input, Left
most derivation
 K: stands for number of lookahead tokens of input
 LL(1) property allows the parser to make a correct
choice of picking alternative (production rule) with a
lookahead of exactly ONE symbol
 To determine whether a particular grammar is LL(1), a
Parsing Table has to be constructed
 This is error prone and tedious process for large
grammar but can be automated

8
9
 How to construct Table?

 To determine the FIRST and FOLLOW sets of each of the

symbols defined or used in the grammar
 These sets allow us to fill in the entries of a predictive
parsing table for G
 FIRST sets:
 FIRST (α) is defined to be the set of terminal symbols that can
appear on the left hand side of the strings derived from α
 FOLLOW sets:
 FOLLOW (α) is defined to be the set of terminal symbols that
can appear immediately to the right of α in a sentential form

10
 Computing FIRST Sets

 For terminal symbol α , FIRST (α) = {α}

 If α  ε, add ε to FIRST(α)
 For all productions, α  k1k2…kn
 Add FIRST(K1) – {ε} to FIRST(α), stop if ε not a member
of FIRST(k1)
 Add FIRST(K2) – {ε} to FIRST(α), stop if ε not a member
of FIRST(k2)
 and so on.

11
Computing FOLLOW Sets

12
Learn by Example
Production First Follow
S -> A B C D E
A -> a / ε
B -> b / ε
C -> c
D -> d / ε
E -> e / ε

14
Production First Follow
S -> A B C D E {a, b, c} {$}
A -> a / ε {a, ε} {b, c}
B -> b / ε {b, ε} {c}
C -> c {c} {d, e, $}
D -> d / ε {d, ε} {e, $}
E -> e / ε {e, ε} {$}

15
 Example 2

Production First Follow

S -> Bb / Cd {a, b, c, d} {$}
B -> aB / ε {a, ε} {b}
C -> cC / ε {c, ε} {c}

16
 Example 3

Production First Follow

E -> TE’ {id, c} {$,)}
E’ -> +TE’ / ε {+, ε} {$,)}
T -> FT’ {id, c} {+ , $ , ) }
T’ -> *FT’ / ε {*, ε} {+ , $ , ) }
F -> id / (E) {id, c} {* , + , $ }

17
18
19
20
 Example

NT/T + * ( ) ID $ Production Predict

E 1: E  T E’ {(,id}
E’ 2: E’  + T E’ {+}
T 3: E’  e {$,)}
T’ 4: T  F T’ {(,id}
F 5: T’  * F T’ {*}
6: T’  e {+,$,)}
7: F  id {id}
8: F  ( E ) {(}
21
 Production Predict
NT/T + * ( ) ID $ 1: E  T E’ {(,id}

E 1 1 2: E’  + T E’ {+}

E’ 2 3 3 3: E’  e {$,)}

T 4 4 4: T  F T’ {(,id}

T’ 6 5 6 6 5: T’  * F T’ {*}

F 8 7 6: T’  e {+,$,)}
7: F  id {id}
8: F  ( E ) {(}
Reference:
http://hackingoff.com/compilers/predict-first-follow-set

22
 Parsing Algorithm

 Parsing table can be used to construct an

efficient Top-Down parser
 Parser maintains a stack of symbols, initialized
with $ at the bottom and S at the top
 Parser reads symbols from the input buffer one
at a time
 Parser picks a production by looking at the
current input symbol a and the symbol X at the
top of stack
23
 Parsing Algorithm

 Parser behaves as follows:

1. If (X = a = $), parser halts and announces successful
completion
2. If (X = a # $), the parser pops X off the stack and
advances the input pointer to the next input pointer
3. If X is non-terminal, the program consults entry M[X,a]
of parsing table M
1. If the entry is a production M[X,a]= {X  UVW},
then parser replaces X on top of stack by WVU (with U on top)
2. If the entry in the table (M) is empty, parser calls an error
recovery routine
24
 Stack Input Action
NT/T + * ( ) ID $ $E a+b*c$ ET
E 1 1 E’

E’ 2 3 3
T 4 4
T’ 6 5 6 6
F 8 7

Assume E is the start symbol

25
 Stack Input Action
NT/T + * ( ) ID $
$E a+b*c$ E  T E’
E 1 1
$E’T a+b*c$ T  F T’
E’ 2 3 3
T 4 4
T’ 6 5 6 6
F 8 7

26
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
E 1 1
E’ 2 3 3
T 4 4
T’ 6 5 6 6
F 8 7

27
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
E’ 2 3 3
T 4 4
T’ 6 5 6 6
F 8 7

28
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3
T 4 4
T’ 6 5 6 6
F 8 7

29
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3 $E’ +b*c$ E’  + T E’
T 4 4
T’ 6 5 6 6
F 8 7

30
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3 $E’ +b*c$ E’  + T E’
T 4 4 $E’ T + +b*c$ match
T’ 6 5 6 6
F 8 7

31
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3 $E’ +b*c$ E’  + T E’
T 4 4 $E’ T + +b*c$ match
T’ 6 5 6 6 $E’ T b*c$ T  F T’
F 8 7

32
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3 $E’ +b*c$ E’  + T E’
T 4 4 $E’ T + +b*c$ match
T’ 6 5 6 6 $E’ T b*c$ T  F T’
F 8 7 $E’T’F b*c$ F  id

33
 Stack Input Action
$E a+b*c$ E  T E’
$E’T a+b*c$ T  F T’
$E’T’F a+b*c$ F  id
NT/T + * ( ) ID $
$E’T’id a+b*c$ match
E 1 1
$E’T’ +b*c$ T’  e
E’ 2 3 3 $E’ +b*c$ E’  + T E’
T 4 4 $E’ T + +b*c$ match
T’ 6 5 6 6 $E’ T b*c$ T  F T’
F 8 7 $E’T’F b*c$ F  id
$E’T id b*c$ match

34
 Parsing a + b * c
Stack Input Action Stack Input Action
$E’T’F F  id
$E a+b*c$ E  T E’
$E’T’id match
$E’T T  F T’
$E’T’ *c$ T’  * F T’
$E’T’F F  id
$E’T’F* match
$E’T’id match
$E’T’F c$ F  id
$E’T’ +b*c$ T’  e
$E’T’id match
$E’ E’  + T E’
$E’T+ match $E’T’ $ T’  e

$E’T b*c$ T  F T’ $E’ E’  e

$ accept

35
Learn by Doing

Parse Trace of (z + q) * x + w * y
 Parse Trace of (z + q) * x + w * y

Stack Input Output

$E ( id + id ) * id + id * id $
$E’T ( id + id ) * id + id * id $ ET E’
$E’T’F ( id + id ) * id + id * id $ TF T’
$E’T’)E( ( id + id ) * id + id * id $ F( E )
$E’T’)E id + id ) * id + id * id $
$E’T’)E’T id + id ) * id + id * id $ ET E’
$E’T’)E’T’F id + id ) * id + id * id $ TF T’
$E’T’)E’T’id id + id ) * id + id * id $ Fid
$E’T’)E’T’ + id ) * id + id * id $
$E’T’)E’ + id ) * id + id * id $ T’ε

37
 Learn by Doing

Construct a parsing table for the following

grammar
 S  iEtSS’ | a

 S’  eS |Є

E  b
39
40
 Learn by Doing

Construct a parsing table for the following

grammar:
S  (A)
A  CB
B  ;A | ε
Cx|S