K.S.
RANGASAMY COLLEGE OF TECHNOLOGY, TIRUCHENGODE - 637 215 CSE
(An Autonomous Institution, Affiliated to Anna University, Chennai)
Tutorial – II Answer Key
Programme & Branch B.E. Computer Science and Engineering Semester VI
Course Code & Name 60 CS 602 – Principles of Compiler Design
Date 04.02.2026
Maximum Marks 50
Answer ALL Questions 5 x 10 = 50 Marks
Bloom CO Mark
level
1. Predict the role of parser with the error recovery strategies employed to Re CO2 01,02 10
recover from syntax error
A parser is a crucial component of the compiler that takes tokens
generated by the lexical analyzer and checks if they conform to the
syntax of the given programming language using a formal grammar. It
performs syntax analysis and constructs a parse tree or an abstract
syntax tree (AST).
The primary functions of a parser include:
1. Checking Syntax Validity: Ensures the input code follows the
grammar rules.
2. Constructing Parse Trees: Generates a hierarchical structure of
the program.
3.
4. Error Reporting and Recovery: Detects syntax errors and
attempts to recover from them.
5. Generating Intermediate Representation: Some parsers
contribute to generating intermediate code for further compilation
stages
Error Recovery Strategies in Parsers
Panic Mode Recovery
The parser skips tokens until it finds a known synchronization
point (e.g., semicolon, closing parenthesis).
Phrase-Level Recovery
The parser modifies or inserts missing tokens to fix the error at
the phrase level.
It uses heuristics to determine probable corrections.
Error Productions
The grammar is augmented with special rules to anticipate
common errors.
Global Correction
The parser searches for the minimum number of changes
needed to make the input correct.
Consider the given grammar, An CO2 01,02 08
,03,
2. E→E+T | T 04,05
T→ T*F | F
F→a | (E )
E'→ +TE' | ∈
E → TE'
T' → *FT' | ∈
T → F T'
F → a | (E)
(i) Solving the FIRST and FOLLOW for the given grammar.
FIRST(E) = FIRST(T) = FIRST(F) = { id, ( }
FIRST(E') = { +, ε }
FIRST(T') = { *, ε }
FIRST(F) = { id, ( }
FOLLOW(E) = FOLLow(E’)={ $ , ) }
FOLLOW(T) = FOLLOW(T') = {+, $,)}
FOLLOW(F) = {+, *, $,)}
(ii) Constructing the parsing table for the given grammar.
Non id + * ( ) $
Terminal
E E→ TE' E→ TE'
E' E’→ +TE' E’→ ε E’→ ε
T T→ F T' T → F T'
T' T’→ ε T'→*FT T’→ ε T’→ ε
'
F F → id F→ (E)
Parsing the input string a + a * a
Stack Input Action
E$ a+ a * a $ Apply E → T E'
T E' $ a+a*a$ Apply T → F T'
F T' E' $ a+a*a$ Apply F → a
id T' E' $ a+a*a$ Match id
T' E' $ +a*a$ Apply T' → ε
E' $ +a*a$ Apply E' → + T E'
+ T E' $ +a*a$ Match +
T E' $ a*a$ Apply T → F T'
F T' E' $ a*a$ Apply F → a
id T' E' $ a*a$ Match id
T' E' $ *a$ Apply T' → * F T'
* F T' E' $ *a$ Match *
F T' E' $ a$ Apply F → a
id T' E' $ a$ Match id
T' E' $ $ Apply T' → ε
E' $ $ Apply E' → ε
$ $ ACCEPT
3. Explain the ambiguous for the given grammar, Solve the leftmost and
rightmost derivation for the input string aaabbabbba and represent the
parser tree for the input string. 01,02
An CO2 10
S → aB / bA ,03
A → aS / bAA / a
B → bS / aBB / b
To check ambiguity, we need to determine whether a given string can be
derived in multiple ways.
1. Consider the input string "aaabbabbba".
2. If we find two distinct parse trees for the same string, the
grammar is ambiguous.
n leftmost derivation, we always replace the leftmost non-terminal at
each step.
1. S → aB (choosing aB since aaabbabbba starts with a)
2. aB → a aBB (choosing B → aBB)
3. aaBB → aa aBBB (B → aBB)
4. aaaBBB → aaa bSBB (B → bS)
5. aaabSBB → aaab aBBB (S → aB)
6. aaabaBBB → aaaba bSBB (B → bS)
7. aaababSBB → aaabab bSBB (S → bA)
8. aaababbSBB → aaababb aBBB (S → aB)
9. aaababbaBBB → aaababba bSBB (B → bS)
10. aaabbabbba (finally replacing S → a)
Thus, the leftmost derivation is:
S → aB
→ a aBB
→ aa aBBB
→ aaa bSBB
→ aaab aBBB
→ aaaba bSBB
→ aaabab bSBB
→ aaababb aBBB
→ aaababba bSBB
→ aaabbabbba
Rightmost Derivation (RM Derivation)
In rightmost derivation, we always replace the rightmost non-terminal.
1. S → aB
2. aB → a aBB
3. aaBB → aa aBBB
4. aaaBBB → aaa bSBB
5. aaabSBB → aaab aBBB
6. aaabaBBB → aaaba bSBB
7. aaababSBB → aaabab bSBB
8. aaababbSBB → aaababb aBBB
9. aaababbaBBB → aaababba bSBB
10. aaabbabbba (finally replacing S → a)
Since the rightmost derivation follows the same pattern as the leftmost
one in this case, it suggests there might not be multiple derivations
leading to ambiguity. However, we need to verify this by constructing
parse trees.
S
/ \
a B
/ \
a B
/ \
a B
/ \
b S
/ \
a B
/ \
b S
/ \
b A
/ \
a B
/ \
b S
|
a
Demonstrate and construct the predictive parser table for the given Ap CO2 01,02 10
4. grammar.
S→(L)|a
L→L,S|S
To construct the predictive parser table for the given grammar:
Step 1: Compute FIRST and FOLLOW Sets
We first compute the FIRST and FOLLOW sets for each non-terminal.
Rules Given:
1. S → ( L ) | a
2. L → L , S | S
Step 2: Compute FIRST Sets
FIRST(S)
S → ( L ) → FIRST(( L )) = { ( }
S→a→{a}
So, FIRST(S) = { ( , a }
FIRST(L)
L→L,S
o L is recursive, so we check FIRST(L), which depends
on itself.
L→S
o FIRST(S) = { ( , a }
So, FIRST(L) = { ( , a }
Step 3: Compute FOLLOW Sets
FOLLOW(S)
Follow Functions-
Follow(S) = { $ , , , ) }
Follow(L) = { ) }
Follow(L’) = Follow(L) = { ) }
o From L → L , S, FOLLOW(S) ⊇ FOLLOW(L)
o Since S is the start symbol, $ (EOF) is in FOLLOW(S)
o From S → ( L ), ) ∈ FOLLOW(L)
o So, FOLLOW(S) = { ) , $ }
FOLLOW(L)
o From L → L , S, FOLLOW(L) ⊇ { , } (because after L we
o From S → ( L ), FOLLOW(L) = { ) }
have ,)
o Also, since L → L , S and S’s FOLLOW is { ) , $ }, we
include those in FOLLOW(L).
o So, FOLLOW(L) = { , , ) }
Step 4: Construct the Predictive Parsing Table
We construct a parsing table using the FIRST and FOLLOW sets.
Non-Terminal ( ), a $
S S→(L) - - S→a -
L L→S - L→L,S L→S -
Step 5: Verify LL(1) Property
To check if the grammar is LL(1):
There should be no conflicts (i.e., no multiple entries in a single
cell).
There are no conflicting rules in the table, so the grammar is
LL(1).
The Predictive Parsing Table is:
Non- ( ) , a $
Terminal
S S→(L) - - S→a -
L L→S - L→L,S L→S -
5. Perform the left factoring for the given grammar and also construct
parsing table. Un CO1 (10)
S → iEtS | iEtSeS | a
E→b
Given Grammar
S → iEtS | iEtSeS | a
E→b
1. S→iEtSS′ ∣ a
Left Factored Grammar:
2. S′→eS ∣ε
3. E→b
FIRST Sets
FIRST(S) = { i, a }
FIRST(S') = { e, ε }
FIRST(E) = { b }
FOLLOW Sets
FOLLOW(S)={$,e}
FOLLOW(S')={$,e}
FOLLOW(E)={t}
Non i a e b t $
Terminal
S S→ iEtS S→a E→ TE'
S'
S’ S' → S' → ε S' → ε
eS
E E→b
Bloom Level Mark
Remember (Re) 10
Understand (Un) 10
Apply (Ap) 10
Analyze (An) 20
Create (Cr) -
Q. No Course Outcomes Marks
1-5 CO2: Interpret the role od syntax analysis and parsing techniques 50
Course Instructor Course Coordinator Module Coordinator HOD/CSE