Name:

Enrolment No:

UNIVERSITY OF PETROLEUM AND ENERGY STUDIES

End Semester Examination, May 2018
Course: Compiler Design Semester: IV
Program: B.Tech.-CS (All IBM specialization)
Time: 03 hrs. Max. Marks: 100

Instructions: Attempt all the questions.

SECTION A

S. No. Marks CO
Q1 How a parser generator can be used to facilitate the construction of the front end compiler. 4 CO1
Q2 Define the term reduction, handle and right sentential form. Explain with a suitable
4 CO2
example.
Q3 Find the reduced grammar equivalent to the following CFG:-
S  AC / SB
A  BaSC / a 4 CO2
B  aSB / bbC
C  Bc /ad
Q4 Discuss the peephole optimization? 4 CO4
Q5 What is a directed acyclic graph? Discuss the steps for constructing DAG. 4 CO5
SECTION B

Q6 Write Syntax Directed translation rules such that along with the parsing, the infix expression
will be converted into postfix form for the following grammar.
EE+T
ET
T  T*F 10 CO3
TF
F  (E)
F  id
Illustrate the rules with a suitable example.
Q7 Convert the following pseudo code into 3-Address code.

while (A < C and B >D) do

{if A=1 then
C:= C+1
else 10 CO5
While ( A< =D) do
{A:=A+3
}
}
Q8 Construct a predictive parsing table for the following grammar.
S  (L) / 𝜖
10 CO3
A  , SA / 𝜖
L  SA
Q9 Write quadruples, triples and indirect triples for the expression:-
-((A/B) + B)* (C+(D*E)) - (A+B+C)
Or,
CO1/C
Create a cross compiler for EQN using following compilers (i) C compiler, written in 10
O5
PDP-11, producing code in PDP-11 (ii) An EQN language compiler producing code for text
formatter, TROFF and written in C. Show your steps using T-diagram.
SECTION-C

Q 10 Construct SLR parsing table for the following grammar and identify the problem
which may encounter while parsing a string. Resolve the problem encountered by
constructing the CLR parsing table. Parse id=id*id + id*id with LALR parsing table
constructed for the same grammar prescribed below. CO2/C
20
O3
G → E = E | id
E→E+T|T
T → T * id | id
Q11 Construct the basic blocks, draw the flow graph and identify the loop invariant
statements for the following pseudo code.
x =1
i= 1
y =1
while( i <= n){
x= x + A[i]
y=2
i=i+1 20 CO5
}
Or,

Discuss the following terms-:

(a) Activation Record
(b) Handle Pruning
(c) Leading
(d) Symbol Table Organization
Name:
Enrollment No:

UNIVERSITY OF PETROLEUM AND ENERGY STUDIES

End Semester Examination, May 2018
Course: Compiler Design Semester: VI
Program: B.Tech.- CSE (All IBM specialization)
Time: 03 hrs. Max. Marks: 100

Instructions: Attempt all the questions.

SECTION A
(All questions are compulsory)
S.No. Marks CO
Q1 Discriminate between the front end and back end of a compiler? What are the advantages of
breaking up the compiler functionality into these two distinct stages
4 CO1

Q2 Describe the role of symbol table in compiler 4 CO4

Q3 State the problems with Top-Down Parsing. 4 CO2
Q4 State the difference between synthesized attributes and inherited attributes. 4 CO3
Q5 Translate the following expression into triple representation:
4 CO5
x[ i ] = interest(p, n, r) + y[ i ] +p
SECTION B
(All questions are compulsory)
Q6 Explain the role of syntax directed translation scheme in detail. 10 CO3
Q7 List various operations that can be implemented in a symbol table. 10 CO4
Q8 For the following C code, generate the intermediate code (Three-address code only).
while ( a > b && a <= 2*b-5)
{
10 CO5
a=a+b;
}

Q9 Create a cross compiler for EQN using following compilers (i) C compiler, written in
PDP-11, producing code in PDP-11 (ii) An EQN language compiler producing code for text
formatter, TROFF and written in C. Show your steps using T-diagram.
Or,
Consider the following grammar: - CO1/C
10
A  AcB | cC | C O2
B  bB | id
C  CaB | BbB | B
Construct the first and follow sets for the grammar. Also design a LL(1) parsing table for the
grammar.
 SECTION C
(All questions are compulsory)
Q 10 Construct LALR(1) for the following grammar.
S B
B  begin DA end
D  Dd; / 𝜖
20 CO2
AA,E/𝜖
EB/S
Check the validity of the string “ begin d ; end”.

Q 11 Perform different code optimizations for the following code by first constructing Basic Blocks
and flow graph

(1) PROD := 0
(2) I: = 1
(3) T1:= 4*I
(4) T2 := addr(A) - 4
(5) T3 := T2[T1]
(6) T4:= addr(B) - 4
(7) T5:= T4[T1]
(8) T6:= T3*T5 CO5/C
(9) PROD:= PROD+T6 O1/C0
20
(10) I:= I+1 2/CO3
(11) If I ≤ 20 goto (3) /CO4

Or,

Define the following terms:

a) DAG
b) Handle Pruning
c) Trailing
d) L-Attributed SDD