Lab Compilers

Session 5: Use of CFGs for Parsing
I. OBJECTIVE:
We can think of using CFGs to parse various language constructs in the token streams
freed from simple syntactic and semantic errors, as it is easier to describe the
constructs with CFGs. But CFGs are hard to apply practically. In this session, we
implement a simple recursive descent parser to parse a number of types of statements
after exercising with simpler CFGs. We note that a recursive descent parser can be
constructed from a CFG with reduced left recursion and ambiguity.
II. DEMONSTRATION OF USEFUL RESOURCES:

1. Observe the C code segments that implement the non-terminals of the following CFG.
S → b | AB
A →a | aA Language generated: {b, ab, aab, aaab, …..}
B →b
void S() { void A() { void B() {

if (str[i] == 'b'){ if (str[i] == 'a') { if (str[i] == 'b') {
i++; i++; i++;
f=1; f=1; f=1;
return; } return;
} else { }
else { f=0; else {
A(); return; f=0;
if (f) { } return;}
B(); if (i<l-1) }
return; } A();
}} }
** Find if there is any logical error in the sample code shown above.
2. A CFG to describe the syntax of simple arithmetic expressions may look like the one
that follows:
Non-terminal symbols:
<Exp>→<Term> + <Term> | <Term> - <Term> | <Term> <Exp>, <Term>, <Factor>
<Term>→<Factor> * <Factor> | <Factor> / <Factor> | <Factor> Terminal symbols:
<Factor>→( <Exp> ) | ID | NUM +, -, *, /, (,), a, b, c, d,e, 0, 1, 2, 3, ..., 9
ID → a|b|c|d|e Start symbol:

<Exp>
NUM→ 0|1|2|…|9
Page | 14
III. LAB EXERCISE:
1. Implement the following CFG in the way shown above.
A → aXd
X → bbX
X → bcX
X→
2. Implement the CFG shown above for generating simple arithmetic expressions.
IV. ASSIGNMENT #5:

Implement the following grammar in C.
<stat>→<asgn_stat><dscn_stat><loop_stat>
<asgn_stat>→id = <expn>
<expn>→<smpl_expn> <extn>
<extn>→<relop> <smpl_expn> | 
<dcsn_stat>→ if (<expn> ) <stat> <extn1>
<extn1>→ else <stat> | 
<loop_stat>→while (<expn>) <stat>for (<asgn_stat> ; <expn> ; <asgn_stat> ) <stat>
<relop>→ ==!=<=>=><
Note: <smpl_expn> can be implemented using the materials demonstrated in this

session.
Page | 15
Session 6: Predictive Parsing
I. OBJECTIVES:
Manual implementation of LL(1) and LR(1) parsing algorithms.
II. DEMONSTRATION OF USEFUL RESOURCES:

1. Computation of the FIRST and FOLLOW functions as described below.
❖ To Compute FIRST(X) for all grammar symbols X, apply the following rules until no
more terminals or  can be added to any FIRST set.
a. If X is a terminal, then FIRST(X) is {X}.
b. If X is a non-terminal and X → Y1Y2 … Yk is a production for some k  1, then place
b in FIRST(X) if for some i, b is in FIRST(Yi), and  is in all of FIRST(Y1), …, FIRST(Yi-
1);
that is, Y1, …, Yi-1 derives .
c. If  is in FIRST(Yj ) for all j = 1, 2, …, k then add  to FIRST(X).
Sample input and corresponding output:
E → TE' FIRST(E) = {(, id}

E' → +TE' |  FIRST(T) = {(, id}
T → FT' FIRST(E') = {+, }
T' → *FT' |  FIRST(T') = {*, }
F → (E) | id FIRST(F) = {(, id}
❖ To compute FOLLOW(A) for all non-terminals A, apply the following rules until
nothing can be added to any FOLLOW set.
i. Place $ in FOLLOW(S), where S is the start symbol and $ is the right end-marker
of an input.
ii. If there is a production A →B, then everything in FIRST() except  is in
FOLLOW(B).
iii. If there is a production A →B, then everything in FOLLOW(A) is in FOLLOW(B).
iv. If there is a production A →B where FIRST() contains , then everything in
FOLLOW(A) is in FOLLOW(B).
Page | 16
Sample input and corresponding output:
E → TE' FOLLOW(E) = {$, )}

E' → +TE' |  FOLLOW(T) = {+, $, )}
T → FT' FOLLOW(E') = {), $}
T' → *FT' |  FOLLOW(T') = {+, ),$}
F → (E) | id FOLLOW(F) = {*, +, $, )}
Table for LL(1) non-recursive predictive parsing with the given grammar:
Non- Input symbols

terminal id + * ( ) $
E E → TE' E → TE'
E' E'→+TE' E'→ E'→
T T → FT' T → FT'
T' T'→ T'→ *F T' T'→ T'→
F F →id F → (E)
III. An example of construction of tools for LR(1) parsing

$
S 1 accept
1. S →AbA S' → S
2. A →aA 0 A A
S →AbA b 4
3. A → a 2 6
A→aA
a a
A→a
3 5
A
a
ACTION GOTO
State FOLLOW(S) = {$}
a b $ S A
0 s3 1 2 FOLLOW(A) = {b, $}
1 acc
2 s4
3 s3 r3 r3 5
4 s3 6 FIRST(S) = FIRST(A) ={a}
5 r2 r2
6 r1
If A →• is in Ii, then set ACTION(i, a) to “Reduce by A →” for all a in FOLLOW(A).
I3 contains A→a•; I5contains A →aA•; I6contains S →AbA•.
Page | 17
IV. LAB EXERCISE:
Perform the tasks1, 2, and 3 of the Assignment #6 which is described below.
V. ASSIGNMENT #6:
Suppose, you are given the following grammar and the input string abcd.
S →aXd
X → YZ
Y→b
Y →
Z →cX
Z →
❑ You are required to perform the following tasks manually:

1. Find the FIRST and FOLLOW sets of each of the non-terminals.
2. Construct the predictive parsing table for LL(1) method.
3. Demonstrate the moves of the LL(1) parser on the given input.
4. Construct the LR(0) automaton for the grammar.
5. Construct the parsing table for LR(1) parsing with the grammar.
6. Demonstrate the moves of the LR(1) parser on the given input.
Page | 18

Lab Compilers

Uploaded by

Copyright:

Available Formats

Lab Compilers

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab Compilers

Uploaded by

Copyright:

Available Formats

Session 5: Use of CFGs for Parsing

II. DEMONSTRATION OF USEFUL RESOURCES:

void S() { void A() { void B() {

<Term>→<Factor> * <Factor> | <Factor> / <Factor> | <Factor> Terminal symbols:

<Factor>→( <Exp> ) | ID | NUM +, -, *, /, (,), a, b, c, d,e, 0, 1, 2, 3, ..., 9

ID → a|b|c|d|e Start symbol:

1. Implement the following CFG in the way shown above.

IV. ASSIGNMENT #5:

<dcsn_stat>→ if (<expn> ) <stat> <extn1>

<extn1>→ else <stat> | 

<loop_stat>→while (<expn>) <stat>for (<asgn_stat> ; <expn> ; <asgn_stat> ) <stat>

Note: <smpl_expn> can be implemented using the materials demonstrated in this

II. DEMONSTRATION OF USEFUL RESOURCES:

Sample input and corresponding output:

E → TE' FIRST(E) = {(, id}

E → TE' FOLLOW(E) = {$, )}

Non- Input symbols

III. An example of construction of tools for LR(1) parsing

I3 contains A→a•; I5contains A →aA•; I6contains S →AbA•.

❑ You are required to perform the following tasks manually:

You might also like