Studies,
University of Kalyani
B.Tech. Pt-III (IT) 2nd Semester
Examination, 2024
Subject: Compiler Design
Paper: IT601
Full marks=70 Time: 3 Hours
The figures in the right-hand margin indicate
marks.
Candidate are required to give their answers
in their own words as far as possible.
The notations follow their standard
meanings.
Answer question number one and
any five from rest.
1. Answer any ten questions:
(2 x 10 = 20)
a) What do you mean by utility program?
b) Define cross-compiler.
c) What do you mean by
Incremental-compiler?
d) Define top-down and bottom-up parsing.
e) What do you mean by shift / reduce
and reduce / reduce conflict?
f) What is the relation between regular
expressions a* and a+ ?
g) What do you mean by intermediate
code generation ?
h) What are the purpose of
activation record ?
i) Discuss the importance of symbol
table in compiler design.
j) What are the role of laxical analyzer
in compiler design?
k) What are the role of syntax analyzer
in compiler design?
l) What are the role of semantic analysis
in compiler design?
m) Write down the advantage of optimized
code over non-optimized code.
n) Show that for improving the locality
of reference the optimizer exchange the
inner loops with outer loops.
o) Compare the expression A * B and A + A + ... + A(B-times) in terms of strength
reduction from code.
2. a) Represents the relationship between
the phases of a compiler.
b) Match all items in Group 1 with correct
options from those given in Group 2.
Group 1 | Group 2 |
Regular expression | Syntax analysis |
Pushdown automata | Code g eneration |
Data flow analysis | Laxical analysis |
Register allocation | Code opti mization |
c) Distinguish between NFA and DFA.
Compare their powers as token
recognizer.
(4+2+4)
3. a) What do you mean by left recursive
grammar?
Eliminate the left recursion from
the following grammar rule
A -> Aɑ1 | Aɑ2 | ... | Aɑm | β1 | β2 | ... | βn .
b) What do you mean by operator
grammar? Give example.
c) What are the different types of
common error occuring in programs?
(4+3+3)
4. a) Define First(A), Follow(A), and
nullable(A) for a grammer.
b) Find the First, Follow and nullable for
each of the non-terminal in the following
grammar
E -> ME’ , E’ -> ɛ , E’ -> +ME’ , M -> AM’ ,
M’ -> ɛ , M’ -> *AM’ , A -> num , A -> (E) .
c) What do you mean by LR parsing ?
Write down different methods to perform
LR parsing.
(3+5+2)
5. a) Define non-recursive predictive
parsing-LL(k) parsing.
b) Write down the conditions that a given
grammar is LL(1) grammar.
c) Prove that the grammar
S -> A | B, A -> cA + b | a, B -> cB + a | b
is not LL(1).
(2+3+5)
6. a) What do you mean by code
optimization?
Discuss different types of code
optimization technique.
b) Discuss loop fission, loop fusion,
loop unrolling in a loop optimization technique.
c) Consider following piece of program:
a = c + d , e = a + b , f = e – 1
What is the fewest number of register
that are needed for the program ?
(5+3+2)
7. a) What do you mean by Abstract Syntax
Trees (AST) ?
b) Draw a Abstract Syntax Trees (AST)
of the following piece of code.
If x > 0 then x = 3 * (y + 1) else y = y + 1
c) What do you mean by Directed Acyclic
Graphs (DAGs)?
d) Construct a Directed Acyclic Graphs (DAGs)
of the following piece of code.
If x > 0 then x = 3 * (y + 1) else y = y + 1
(2+3+2+3)
8. Short notes:
(2 x 5)
Answer any two of the following:
a) Compiler vs. Interpreter.
b) The lexical analysis tool-LEX.
c) Parser generator-YACC.
d) Challenges in complier design and
its application.
--------------------End-------------------
.png)