1
PARSING
Introduction
2
A grammar describes the strings of tokens
that are syntactically legal in a PL
A parser construct a derivation or parse
tree for a sentence (if possible)
Types of Parsing
3
Top Down Parsing:
starts constructing the parse tree at the to
p (root) of the parse tree and move down tow
ards the leaves. Easy to implement by hand,
but work with restricted grammars.
examples:
Predictive parsers
Bottom Up Parsing:
Bottom-up parsing reduces a string to the st
art symbol by inverting productions
shift-reduce parser
4
TOP-DOWN PARSIN
G
Creating a top-down parser
5
Top-down parsing can be viewed as the pro
blem of constructing a parse tree for the
input string, starting form the root and
creating the nodes of the parse tree in p
reorder.
An example follows.
Creating a top-down parser
(Cont.)
6
Given the grammar :
E → TE’
E’ → +TE’ | λ
T → FT’
T’ → *FT’ | λ
F → (E) | id
The input: id + id * id
Creating a top-down parser
(Cont.)
7
Top-down parsing
8
A top-down parsing program consists of a s
et of procedures, one for each non-termina
l.
Execution begins with the procedure for th
e start symbol, which halts and announces
success if its procedure body scans the en
tire input string.
LL(1) Parsers
9
The first “L” stands for scanning input
from left to right. The second “L” for p
roducing a leftmost derivation. The “1”
for using one input symbol of look-ahead a
t each step to make parsing decisions.
Model of a table-driven predictive parser
10
The parsing table
11
FIRST and FOLLOW
FIRST FOLLOW
S -> ABCDE {a,b,c} {$}
A -> a|€ {a, €} {b,c}
B -> b| € {b, €} {c}
C->c {c} {d,e,$}
D -> d | € {d, €} {e,$}
E -> e| € {e, €} {$}
FIRST and FOLLOW Example 1
12
FIRST FOLLOW
S -> Bb | Cd {a,b,c,d} {$}
B -> aB| € {a, € } {b}
C -> cC | € {c, €} {d}
FIRST and FOLLOW Example 2
13
FIRST FOLLOW
E -> TE’ {id,(} {$,)}
E’ -> +TE’|€ {+, €} {$,)}
T -> FT’ {id,(} {+,$,)}
T’ -> * FT’|€ {*, €} {+,$,)}
F -> id|(E) {id,(} {*,+,$,)}
FIRST and FOLLOW Example 3
14
FIRST FOLLOW
S->ACB|CbB|Ba {d,g,h,€,b,a} {$}
A -> da|BC {d,g,h, €} {h,g,$}
B-> g| € {g, €} {$,a,h,g}
C->h| € {h, €} {g,$,b,h}
15
How to construct parsing tab
le?
FIRST FOLLOW
E -> TE’ {id,(} {$,)}
E’ -> +TE’|€ {+, €} {$,)}
T -> FT’ {id,(} {+,$,)}
T’ -> * FT’|€ {*, €} {+,$,)}
F -> id|(E) {id,(} {*,+,$,)}
Non- Input symbol
terminal
ID + * ( ) $
E E->TE’ E->TE’
E’ E’->+TE’ E’->€ E’->€
T T->FT’ T->FT’
T’ T’->€ T’->*FT’ T’->€ T’->€
F16 F->id F->(E)
How does parsing table help
17
in parsing process?
S->(S) | € $ S
NT Input symbol
$ ) S (
( ) $
S S->(S) S->€ S->€ $ ) S
$ ) ) S (
( ( ) ) $ $ ) ) S
$ ) )
$ )
Stack Input Symbol Moves
Exercise
Construct the LL(1) table for the following
grammar:
S->aABb
A->c/€
B-d/€
Also parse the following input string:
acdb$
Exercise
Construct the LL(1) table for the following
grammar:
1 Expr → - Expr
2 Expr → (Expr)
3 Expr → Var ExprTail
4 ExprTail → - Expr
5 ExprTail → λ
6 Var → id VarTail
7 VarTail → (Expr)
8 VarTail → λ
Solution
First(Expr) = {-, (, id}
First(ExprTail) = {-, λ}
First (Var) = { id}
First (VarTail) = { (, λ}
Follow (Expr) = Follow (ExprTail) = {$,
) }
Follow (Var)
= {$, ), -}
Follow (VarTail)
= {$, ), -}
Exercise 1 Solution (Cont.)
Non- Input Symbol
Terminal
- ( id ) $
Expr 1 2 3
ExprTail 4 5 5
Var 6
VarTail 8 7 8 8
Exercise 2
Given the grammar:
S → i E t S S’ | a
S’ → e S | λ
E → b
1. Find the first set and follow set.
2. Build the parsing table.
22
Exercise 2 Solution
23
First(S) = {i, a}
First(S’) = {e, λ}
First (E) = {b}
Follow (S) = Follow (S’) = {$, e}
Follow (E) = {t}
Exercise 2 Solution (Cont.)
24
Non- Input Symbol
Terminal
a b e i t $
S 2 1
S’ 3/4 4
E 5
As First(S’) contains λ and Follow (S’) = {$, e} So rule 4 is added to e, $.
3/4 (rule 3 or 4) means an error. This is not LL(1) grammar.
