Sample Question Format

KIIT Deemed to be University

Online Mid Semester Examination(Spring Semester-2021)

Subject Name & Code: Compiler Design ( CS 3008)

Applicable to Courses: 6th semester

Full Marks=20 Time:1 Hour

SECTION-A(Answer All Questions. All questions carry 2 Marks)

Time:20 Minutes (5×2=10 Marks)

Questi Question Question Answer CO

on No Type(MCQ/ Key(if Mapping
SAT) MCQ)
Q.No:1 MCQ Consider the following C-prog. Find A CO1
(a) the number of tokens in the output of
the following program if that is
passed as a string to a lexical
analyzer.
#include <stdio.h>
int main()
{
char *p[ ] = {"KIIT UNIV", "KIMS
MED", "KISS"};
char **q[ ] = {p + 3, p + 2, p + 1};
char ***r=q;
printf("/*kk*/ %s", ** ++ r);
return 0;
}
A. 1
B. 2
C. 35
D. 4
E. NONE

Consider the following C-prog. Find D CO1

the number of tokens in the output of
the following program if that is
passed as a string to a lexical
analyzer.
#include <stdio.h>
int main()
{

char *p[ ] = {"KIMS MED", "KIIT

UNIV","KISS"};
char **q[ ] = {p , p + 1, p + 2};
char ***r=q;
printf("I am in %s", ** ++ r);
return 0;
}
A. 3
 B. 43
C. 2
D. 1
E. NONE

Consider the following C-prog. Find C CO1

the number of tokens in the output of
the following program if that is
passed as a string to a lexical
analyzer.
#include <stdio.h>
int main()
{
char *p[ ] = {"KISS", "KIMS
MED", "KIIT UNIV"};
char **q[ ] = {p + 1, p + 2, p};
char ***r=q;
printf("I am in %s", **r);
return 0;
}
A. 3
B. 4
C. 1
D. 42
E. NONE

Consider the following C-prog. Find B CO1

the number of tokens in the output of
the following program if that is
passed as a string to a lexical
analyzer.
#include <stdio.h>
int main()
{
char *p[ ] = {"KISS", "KIMS
MED", "KIIT UNIV"};
char **q[ ] = {p + 2, p, p+1};
char ***r=q;
printf("/*I am*/ %s", **r);
return 0;
}
A. 35
B. 1
C. 2
D. 3
E. NONE

Q.No:1 MCQ Consider the following grammar: C CO3

(b) S-> A & S | S $ A
A-> B @ B
A-> id
B-> id
Which of the following options is
correct?
A. $ is left associative.
B. & is right associative.
C. The associativity of @ cannot be
 determined.
D. The associativity of $ cannot be
determined.
E. None

Consider the following grammar: D CO3

S -> B @ S | S & A
B-> A $ A
A -> id
B -> id
Which of the following options is
correct?
A. $ is left associative.
B. & is right associative.
C. The associativity of @ cannot be
determined.
D. The associativity of $ cannot be
determined.
E. None

Consider the following grammar: B C)3

S --> A * B
A --> C | A * C
B --> D + B | D
D --> Id
C --> Id
Which of the following options is
correct?
A) + is left associative ,while * is
right associative
B) + is right associative,while * is
left associative
C) Both + and * are right associative
D) Both + and * are left associative
E) None

Consider the following grammar: D CO3

S --> A * B
A --> C | A * C
B --> B + D | D
D --> Id
C --> Id
Which of the following options is
correct?
A) + is left associative ,while * is
right associative
B) + is right associative,while * is
left associative
C) Both + and * are right associative
D) Both + and * are left associative
E) NONE

Q.No:1 MCQ Eliminate left recursion from the A CO2

 (c) following grammar.
S→ SAa |Sb|a|b
which of the following is correct
grammar.
A. S→aB|bB, B→AaB|bB
B. S→aB|bB, B→aB|AbB
C. S→aA|bA, A→aA|BbA
D. S→aA|bA, A→aBA|bA
E. NONE

Eliminate left recursion from the B CO2

following grammar.
S→ Sa |SAb|a|b
which of the following is correct
grammar.
A. S→aB|bB, B→AaB|bB
B. S→aB|bB, B→aB|AbB
C. S→aA|bA, A→aA|BbA
D. S→aA|bA, A→aBA|bA
E. NONE

Eliminate left recursion from the C CO2

following grammar.
S→ Sa |SBb|a|b
which of the following is correct
grammar.
A. S→aB|bB, B→AaB|bB
B. S→aB|bB, B→aB|AbB
C. S→aA|bA, A→aA|BbA
D. S→aA|bA, A→aBA|bA
E. NONE

Eliminate left recursion from the D CO2

following grammar.
S→ SaB |Sb|a|b
which of the following is correct
grammar.
A. S→aB|bB, B→AaB|bB
B. S→aB|bB, B→aB|AbB
C. S→aA|bA, A→aA|BbA
D. S→aA|bA, A→aBA|bA
E. NONE

Q.No:1 MCQ Find FIRST() & FOLLOW() of the A, E CO3

(d) following grammar.
S → AB|a
A → Bb | ɛ
B→ c | ɛ
Choose the correct option.
A. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={c, $}
B. FIRST(S)={a, c },
FOLLOW(A)={c}
C. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={b, c, $}
 D. FIRST(S)={a,b, c},
FOLLOW(A)={c, $}
E. NONE

Find FIRST() & FOLLOW() of the B,E CO3

following grammar.
S → AB|a
A → Bb | ɛ
B→ c
Choose the correct option.
A. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={c, $}
B. FIRST(S)={a, c },
FOLLOW(A)={c}
C. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={b, c, $}
D. FIRST(S)={a,b, c},
FOLLOW(A)={c, $}
E. NONE

Find FIRST() & FOLLOW() of the C, E CO3

following grammar.
S → AB|a
A → BAb | ɛ
B→ c | ɛ
Choose the correct option.
A. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={c, $}
B. FIRST(S)={a, c },
FOLLOW(A)={c}
C. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={b, c, $}
D. FIRST(S)={a,b, c},
FOLLOW(A)={c, $}
E. NONE

Find FIRST() & FOLLOW() of the D, E CO3

following grammar.
S → AB
A → Bb|a
B→ c | ɛ
Choose the correct option.
A. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={c, $}
B. FIRST(S)={a, c },
FOLLOW(A)={c}
C. FIRST(S)={a, b, c, ɛ },
FOLLOW(A)={b, c, $}
D. FIRST(S)={a,b, c},
FOLLOW(A)={c, $}
E. NONE

Q.No:1 MCQ Consider the grammar A CO2

(e) S -> SS / (S) / a
 A ) ambiguous
B) Unambiguous
C) Left recursion
D) Right recursion
E) None
Given the grammar D CO2
S -> A * S / A
A -> B + A / B
B -> a / b
Which of the following is wrong?
A ) Grammar is not ambiguous
B ) priority of + over * is assured
C ) Right to left evaluation of * and +
happens
D ) None of these
The grammar is D CO2
S -> SS / (S) / a
A ) Right Recursion
B ) Left recursion
C ) Ambiguous
D ) All of the above
F) None
Given the grammar A CO2
S -> A * S / A
A -> B + A / B
B -> a / b
Which of the following is correct?
A )Grammar is not ambiguous.
B ) priority of * over + is assured
C ) Left to right evaluation of * and +
happens
D ) none of the above

SECTION-B(Answer Any One Question. Each Question carries 10 Marks)

Time: 30 Minutes (1×10=10 Marks)

Question No Question CO
Mappi
ng
Q.No:2 A) Show the output for each phase for the expression S CO1,
= a + b * c + 20 with a neat and clean diagram of CO2
translation of the given statement( where the variables
a ,b,c are of floating type and S is of integer type).

Ans:
B) Remove left recursion from the following grammar:
S -> A / a / BAC
A -> B / b
B -> S / c
C -> d

Ans.
X-> xYw / xZC => X-> xX′, X′->Yw / ZC
Y -> x / xy / xyZy / xYy
Z -> zzw / zwZ / z / ε => Z -> zZ′, Z′->zw / wZ / ε

C) Left factor the following grammar:

X-> xYw / xZC
Y -> x / xy / xyZy / xYy
Z -> zzw / zwZ / z / ε

Ans.
Remove left-recursion from S -> A / a / SAC / cAC
S->AS′ / aS′ /cACS′
S′->AC / ∈
A -> S / b / c
C -> d

Sub substituting this A -> S / b / c in the above production

 S>SS′ / aS′ /cSCS′ /bS′ /cS′/cbCS′/ccCS′
S′->SC / bC /cC /∈

Remove left-recursion
S->aS′T/cSCS′T /bS′T /cS′T/ cbCS′T/ ccCS′T
T->S′/∈
C -> d

Q.No:3 A) Show the output for each phase for the expression S = CO1,
X / Y - Z + 20.0 with a neat and clean diagram of CO2
translation of the given statement( where the variables
X ,Y are of floating type and Z , S are of integer type).

Ans:
B) Remove left recursion from the following grammar:
S -> Xa / Sa / b
 X -> Xc / Se / d
Ans-
S -> XaS' | bS'
S'->aS' | ε
X -> SeX' | dX'
X' -> cX' | ε

C ) Left factor the following grammar:

S-> abcd | abce | abf | ag
S->aA | abAa | abcA | abA
A-> ab| b
Ans:
S-> abcd | abce | abf | ag

S->aS'''
S'''->bS'' | g
S''->cS'| f
S'-> d | e

S->aA | abAa | abcA | abA

A-> ab| b

S->aS'
S'->A | bS''
S''->Aa | cA | A
A-> ab| b

Replace A with its production everywhere to simplify the

grammar

S->aS'
S'-> ab| b | bS''
S''->aba | ba|cab|cb | ab| b

Q.No:4 A) Show the output for each phase for the expression a= CO1,
b*c/d+e-60.0 with a neat and clean diagram of translation CO2
of the given statement( where the variables b ,c and d are
of floating type and a , e are of integer type).

Ans:-
B) Remove left recursion from the following grammar:
X -> Ya / Xa / c
Y -> Yb / Xb / d
Ans:-
C ) Left factor the following grammar:
X-> xYw / xZ
Y -> x / xy
Z -> zzw / wwZ / z / w
Ans:-
Q.No:5 A) Compute the FIRST and FOLLOW sets of each non-terminal CO2,
in the grammar given bellow. Also construct the LL(1) parsing CO3
table.
S->aABh
A->cC
C->bC|ε
B->ED
E->g|ε
D->f|ε
Ans:-
First Functions-

First(S) = { a }
First(A) = { c }
First(C) = { b , ∈ }
First(B) = { First(E) – ∈ } ∪ First(D) = { g , f , ∈ }
First(E) = { g , ∈ }
First(D) = { f , ∈ }

Follow Functions-

Follow(S) = { $ }
Follow(A) = { First(B) – ∈ } ∪ First(h) = { g , f , h }
Follow(C) = Follow(A) = { g , f , h }
Follow(B) = First(h) = { h }
Follow(E) = { First(D) – ∈ } ∪ Follow(B) = { f , h }
Follow(D) = Follow(B) = { h }

a b c g f h $
S S→
aABh
A A→
cC
B B→B→
EDED
C C→ C→∈ C→ C→
bC ∈ ∈
D D→f D→
∈
E E→g E→ E→
∈ ∈

B) Write down the procedures for the recursive descent

parser for the given grammar:
E -> 0E*A / E+A / E%0
A -> 1A01 / 1
Compare between predictive recursive and predictive
non-recursive descent parser. Which one is better justify
your answer.
Ans:-
Modified Grammar (post removal of Left Recursion and Application
of Left Factoring):

E 0E*AX
X  YX | 
Y  +A | %0
A 1B
BA01 | 

void E();
void X();
void Y();
void A()
void B();
void advance();
char input[10];
int lookahead;
int main()
{
printf("\nEnter the string to be parsed: ");
gets(input);
lookahead=0;
E();
printf("\n\n\t\tString successfully parsed.\n");
return 0;
}

void E()
{
if (input[lookahead]=='0')
{
advance();
if (E())
{
if (input[lookahead]=='*')
{
advance();
if (A())
X();
}
}
}
}
void X()
{
if(Y())
X();
else
return true;
}

void Y()
{
if (input[lookahead]=='+')
{
advance();
A();
}
else if (input[lookahead]=='%')
{
advance();
if (input[lookahead]=='0')
return true;
}
}

void A()
{
if (input[lookahead]=='1')
{
advance();
 B();
}
}
void B()
{
if (A())
if (input[lookahead]=='0')
if (input[lookahead]=='1')
return true;
}
void advance()
{
if (input[lookahead]=='\0')
error();
lookahead++;
}

Predictive Recursive Descent Predictive Non-Recursive Descent Parser

Parser

It is a technique which may or It is a technique that does not

may not require backtracking require any kind of backtracking.
process.

It uses procedures for every It finds out productions to use

non-terminal entity to parse by replacing input string.
strings.

It is a type of top-down parsing It is a type of top-down approach,

built from a set of mutually which is also a type of recursive
recursive procedures where each parsing that does not uses
procedure implements one of technique of backtracking.
non-terminal s of grammar.

It contains several small The predictive parser uses a look

functions one for each non- ahead pointer which points to
terminals in grammar. next input symbols to make it
parser back tracking free,
predictive parser puts some
constraints on grammar.

It accepts all kinds of grammars. It accepts only a class of grammar

known as LL(k) grammar.

Q.No:6 A) Compute the FIRST and FOLLOW sets of each non-terminal CO2,C
in the grammar given bellow. Also construct the LL(1) parsing O3
table.
S-> aAC/Bb
A - >cD
B ->f/g
C ->h/i
D ->bE/ε
E ->eD/dD
 B) Consider the following grammar
S -> xXy / yY
X -> Xx / ε
Y -> Yy / ε
Write down the procedures for the non terminals of the given
grammar to make a recursive descent parser .
Ans:
Q. No:7 A) Construct the LL(1) parse table and verify whether it is LL(1) CO2,C
or not. O3
S-> ACB / CbB / Ba
A -> da / BC
B -> g / ε
C -> h / ε
B) Consider the following grammar
S -> A $
A -> - A B | id C
B -> - B | ""
C -> "" | . id
Write down the procedures for the non terminals of the given
grammar to make a recursive descent parser .

Ans:
Controller of Examinations