Printed Page: 1 of 2

Subject Code: KCS502

0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM V) THEORY EXAMINATION 2023-24
COMPILER DESIGN
TIME: 3 HRS M.MARKS: 100

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A
1. Attempt all questions in brief. 2 x 10 = 20
Q no. Question Marks CO
a. Define bootstrapping in the context of compilers. 2 1
b. Which phase of compiler is optional and why? 2 1
c. Explain the concept of shift-reduce parsing. 2 2
d. Differentiate Parse tree and Syntax tree with an example. 2 2
e. Define syntax-directed translation schemes. 2 3
f. What are the two types of attributes that are associated with a grammar 2 3
symbol?
g. Discuss how scope information is represented in a symbol table. 2 4
h. What is mean by Activation record? 2 4
i. Discuss two design issues in code generation. 2 5
90

1
j. Explain the concept of global data-flow analysis. 2 5

13
_2

2.
SECTION B
P1

24
2. Attempt any three of the following: 10x3=30
a. Describe the relationship between finite state machines and regular 10 1
4D

5.
expressions. Discuss how regular expressions are used in lexical analysis
.5
P2

and pattern matching.

17
b. For the grammar 10 2
Q

|1

SaAd |bBd |aBe |bAe , Af , Bf

Construct LR(1) Parsing table. Also draw the LALR table.
5

c. Explain the concepts of quadruples and triples in the context of syntax- 10 3

3

directed translation. Discuss how they represent intermediate code and

7:

support optimization.
:2

d. Describe a simple stack allocation scheme for managing memory during 10 4

13

program execution. Explain how it is used for storing local variables and
4

managing function calls.

02

e. Explain the role of a code generator in a compiler. Discuss its 10 5

-2

responsibilities and how it translates intermediate code into the target

code.
01
4-

SECTION C
|2

3. Attempt any one part of the following: 10x1=10

a. Given a regular expression a(b|c)*, construct the corresponding 10 1
Nondeterministic Finite Automaton (NFA) that recognizes the language
described by the regular expression.
b. Check whether given grammar is ambiguous or not. If ambiguous then convert 10 1
it into unambiguous grammar: E→E+E|E*E|id.

1|Page
QP24DP1_290 | 24-01-2024 13:27:35 | 117.55.242.131
Downloaded from: uptukhabar.net
 Printed Page: 2 of 2
Subject Code: KCS502
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM V) THEORY EXAMINATION 2023-24
COMPILER DESIGN
TIME: 3 HRS M.MARKS: 100

4. Attempt any one part of the following: 10x1=10

a. Check whether the given grammar is LR(0) or not: S→PQy, P→Sy|x, Q→yS. 10 2
b. Consider the following grammar for a simple expression language: 10 2
E→E+T|T
T→T*F|F
F → ( E ) | id
Consider expression id * (id+id).Apply shift reduce parsing to construct parse
tree.

5. Attempt any one part of the following: 10x1=10

a. Write syntax directed definition for a given assignment statement: 10 3
S → id=E
E → E+E
E →E*E
E→-E
90
E → (E)

1
13
E→id
_2

b. Explain how syntax-directed translation handles array references within 10 3

2.
P1

arithmetic expressions.

24
4D

5.
6. Attempt any one part of the following: 10x1=10
.5
P2

a. Define Symbol table? Explain about the data structures used for symbol 10 4
17
table.
Q

b. Define semantic errors in a compiler. Discuss the challenges associated 10

|1

with detecting and handling semantic errors. Provide examples to

5

illustrate semantic issues.

3
7:

7. Attempt any one part of the following: 10x1=10

:2

a. Consider a basic block with the following three instructions: 10 5

13

1. x = a + b
2. y = x * c
4
02

3. z = y – d
Apply common sub expression elimination to optimize the basic block.
-2

b. Construct a Directed Acyclic Graph (DAG) to represent the following 10 5

01

basic block:
4-

1. x = a + b
|2

2. y = c - d
3. z = x * y

2|Page
QP24DP1_290 | 24-01-2024 13:27:35 | 117.55.242.131
Downloaded from: uptukhabar.net
Printed Pages:02 Sub Code:KCS-502
Paper Id: 231842 Roll No.

B. TECH.
(SEM V) THEORY EXAMINATION 2022-23
COMPILER DESIGN

Time: 3 Hours Total Marks: 100

Note: Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 10 = 20

(a) How will you group the phases of compiler?
(b) Mention the role of semantic analysis.
(c) What are the various parts in LEX program?
(d) Differentiate Parse tree and Syntax tree with an example.
(e) Give the properties of intermediate representation.
(f) Differentiate between LR and LL parsers.
(g) What is phrase level error recovery?
(h) Discuss the capabilities of CFG.
(i) Define loop jamming.

2
90

13
(j) What is induction variable?
_2

2.
P1

24
SECTION B

5.
3D

.5
2. Attempt any three of the following: 10 x 3 = 30
P2

(a) Write SDD to produce three-address code for Boolean expressions and 17
Q

|1
obtain the three-address code for the statement given below:
7

while a < b do
:2

if c < d then
29

x=y*z
:

else
13

x=y+z
(b) Discuss the stack allocation and heap allocation strategies of the runtime
3
02

environment with an example.

(c) What do you mean by attributed grammars? Discuss the translation
-2

scheme for converting an infix expression to its equivalent postfix form.

01

(d) Construct the NFA and DFA for the following regular expression.
8-

(0+1)*(00+11)(0+1)*
|1

(e) Explain the lexical analysis and syntax analysis phases of the compiler
with a suitable example. Explain the reporting errors in these two phases
as well.

SECTION C

Downloaded from|:18-01-2023
QP23DP1_290 uptukhabar.net
13:29:27 | 117.55.242.132
3. Attempt any one part of the following: 10 x 1 = 10
(a) Construct the CLR parse table for the following Grammar:
ABB
B cB
Bd
(b) Construct the SLR parsing table for the following Grammar.
S→ 0S0
S→ 1S1
S→ 10

4. Attempt any one part of the following: 10 x 1 = 10

(a) What is back patching. Generate three address code for the following
Boolean expression using back patching:
a < b or c > d and e < f
(b) What is top down parsing? What are the problems in top down parsing?
Explain each with suitable example.

5. Attempt any one part of the following: 10 x 1 = 10

2
90
(a) What is an activation record? Draw diagram of general activation

13
record and explain the purpose of different fields of an activation
_2

2.
record.
P1

(b) How do we represent the scope information? Explain scope by number

24
and scope by location.

5.
3D

.5
P2

6. Attempt any one part of the following: 10 x 1 = 10

(a) Define Symbol table? Explain about the data structures used for 17
Q

|1
symbol table.
(b) Explain the following:
7

(i) Copy Propagation

:2

(ii) Dead-Code Elimination

29

(iii) Code Motion

:

(iv) Reduction in Strength.

13
3

7. Attempt any one part of the following: 10 x 1 = 10

02

(a) Explain in the DAG representation of the basic block with example.
-2

(b) Write quadruple, triples and indirect triples for following expression :
01

a = b * – c + b * – c.
8-
|1

Downloaded from : uptukhabar.net

QP23DP1_290 | 18-01-2023 13:29:27 | 117.55.242.132
 Printed Page: 1 of 2
Subject Code: KCS502
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

B.TECH.
(SEM V ) THEORY EXAMINATION 2021-22
COMPILER DESIGN

Time: 3 Hours Total Marks: 100

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A
1. Attempt all questions in brief. 2 x 10 = 20
a. What is the difference between parse tree and abstract syntax tree?
b. Explain the problems associated with top-down Parser.
c. What are the various errors that may appear in compilation process?
d. What are the two types of attributes that are associated with a grammar symbol?
e. Define the terms Language Translator and compiler.
f. What is hashing? Explain.
g. What is do you mean by left factoring the grammars? Explain.
h. Define left recursion. Is the following grammar left recursive?
E → E+E | E*E| a| b

1
90
i. What is an ambiguous grammar? Give example.

13
j. List down the conflicts during shift-reduce parsing.
_2

2.
1P

24
SECTION B
2O

5.
2. Attempt any three of the following: 10 x 3 = 30

.5
P2

a. Construct the LALR parsing table for the given grammar

17
S →BB
Q

|1

B→ aB / b
b. What is an activation record? Explain how it is related with runtime storage organization?
59

c. Write the quadruple, triple, indirect triple for the following expression
0:

(x + y)*(y + z) + (x + y + z)
:0

d. Discuss the following terms:

i. Basic block
09

ii. Next use information

2

iii. Flow graph

02

e. Construct predictive parse table for the following grammar.

E → E + T/T
-2

T →T *F/F
n
Ja

F →F /a/b
2-

SECTION C
|1

3. Attempt any one part of the following: 10 x 1 = 10

a. Construct the SLR parse table for the following Grammar
E→E+E
E→E*E
E→id
b. Differentiate between stack allocation and heap allocation.

Downloaded from : uptukhabar.net

QP22O1P_290 | 12-Jan-2022 09:00:59 | 117.55.242.131
 Printed Page: 2 of 2
Subject Code: KCS502
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

4. Attempt any one part of the following: 10 x 1 = 10

a. Write syntax directed definition for a given assignment statement:
S → id=E
E → E+E
E →E*E
E→-E
E → (E)
E→id
b. What are the advantages of DAG? Explain the peephole optimization.

5. Attempt any one part of the following: 10 x 1 = 10

a. What do you understand by lexical phase error and syntactic error? Also suggest methods
for recovery of errors.
b. Discuss how induction variables can be detected and eliminated from the given
intermediate code
B2: i:= i+1
t1:=4*j

1
90

13
t2:=a[t1]
_2

if t2<10 goto B2

2.
1P

24
6. Attempt any one part of the following: 10 x 1 = 10
2O

5.
a. Test whether the grammar is LL(1) or not, and construct parsing table for it.
.5
P2

S1AB / ε
17
A1AC/0C
Q

|1

B0S
C1
59

b. Distinguish between static scope and dynamic scope. Briefly explain access to non local
0:

names in static scope.

:0

7. Attempt any one part of the following: 10 x 1 = 10

09

a. What are the various issues in design of code generator & code loop optimization?
2
02

b. Generate the three address code for the following code fragment.
-2

while(a>b)
n

{
Ja

if(c<d)
2-

x=y+z;
|1

else
x=y-z;
}

Downloaded
QP22O1P_290 from : uptukhabar.net
| 12-Jan-2022 09:00:59 | 117.55.242.131
 Printed Page: 1 of 2
Subject Code: KCS502
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

B TECH
(SEM-V) THEORY EXAMINATION 2020-21
COMPILER DESIGN
Time: 3 Hours Total Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A

1. Attempt all questions in brief. 2 x 10 = 20

Qno. Question Marks CO
a. What is YACC? Discuss about it. 2 CO 1
b. Design a DFA for the following regular expression: 2 CO 1
(x+y)*xyy
c. Consider the following grammar: 2 CO 2
S→B|SabS, B→bB| ε
Compute FOLLOW(B)
d. Discuss about shift-reduce parsing. 2 CO 2
e. Find the postfix notation for the following expression: 2 CO 3
(a+b+c)*(c+q)

P
f. Discuss about non-linear type intermediate code. 2 CO 3
0Q

1
g. Write short note on “Activation Record” 2 CO 4

13
29

h. Discuss about hash table. 2 CO 4

2.
i. Discus about constant folding. 2 CO 5
0E

24
j. Discuss about designing issues of code generator. 2 CO 5
P2

SECTION B

5.
_Q

.5
2. Attempt any three of the following: 17 3 x 10 = 30
TU

Qno. Question Marks CO

|1

a. Explain in detail the process of compilation for the statement 10 CO 1

AK

a=b+c*70.
4 8

b. Construct the CLR(1) parsing table for the following grammar: 10 CO 2

8:

S→AA, A→aA|b
:1

c. Consider the following grammar and give the syntax directed 10 CO 3

09

definition to construct parse tree for the input expression 4*7+3*9.

Also construct an annotated parse tree according to your syntax
1

directed definition.
02

E→E+T|T, T→T*F|F, F→num.

2

d. Explain lexical, syntax, semantic phase errors in detail. 10 CO 4

b-

e. Explain in detail about loop optimization. 10 CO 5

Fe

SECTION C
5-

3. Attempt any one part of the following:

|2

Qno. Question Marks CO

a. (i). Write a regular expression to represent a language consisting of 10 CO 1
strings made up of odd number of a & odd number of b.
(ii). Write a CFG to represent the language L={an+mbn|m,n≥1}.
b. (i). Check whether given grammar is ambiguous or not. If ambiguous 10 CO 1
then convert it into unambiguous grammar:
E→E+E|E*E|id
(ii). Discuss about cross compiler.
1|Page
AKTU_QP20E290QP | 25-Feb-2021 09:18:48 | 117.55.242.131
 Printed Page: 2 of 2
Subject Code: KCS502
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

4. Attempt any one part of the following:

Qno. Question Marks CO
a. Check whether the given grammar is LR(0) or not: 10 CO 2
S→PQy, P→Sy|x, Q→yS
b. Find the precedence and function table of the following grammar by 10 CO 2
using operator precedence technique.
P→SR|S, R→bSR|bS, S→WbS|W, W→L*W|L, L→id

5. Attempt any one part of the following:

Qno. Question Marks CO
a. Translate the following arithmetic expression into quadruples and 10 CO 3
triples:
(i). x=y*z+y*-z
(ii). a=-b*(c+d)+b
b. Generate three address code for the following code: 10 CO 3
Switch p+q
{

P
case 1: x=x+1
0Q

1
case 2: y=y+2

13
29

case 3: z=z+3

2.
default: c=c-1
0E

24
P2

5.
_Q

6. Attempt any one part of the following:

.5
17
TU

Qno. Question Marks CO

|1
AK

a. What is symbol table? Explain various data structures used for 10 CO 4

8

symbol table.
4

b. (i). Explain the function of error handling phase of a compiler. 10 CO 4

8:

(ii). Write short note on scoping.

:1
09

7. Attempt any one part of the following:

1
02

Qno. Question Marks CO

a. Construct the flow graph for the following code segment: 10 CO 5
2
b-

fact(n)
Fe

{
int f=1;
5-

for(i=2; i≤n; i++)

|2

f=f*i;
return f;
}
b. Define a DAG. Construct a DAG for the expression: 10 CO 5
p+p*(q-r)+(q-r)*s

2|Page
AKTU_QP20E290QP | 25-Feb-2021 09:18:48 | 117.55.242.131
Printed Pages:02 Sub Code:ECS603

Paper Id: 1 1 0 6 0 3 Roll No.

B. Tech.
(SEM VI) CARRY OVER THEORY EXAMINATION 2017-18
Compiler Design
Time: 3 Hours Total Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper specific instruction.

SECTION A

1. Attempt all questions in brief. 2 x 10 = 20

a) what is translator?
b) Differentiate between compiler and assembler.
c) Discuss conversion of NFA into a DFA . also give the algorithm used in this conversion.
d) Write down the short note on symbol table.
e) Describe Data structure for symbol table .
f) What is mean by Activation record
g) What is postfix notations ?
h) Define Three address Code

i) What are Quadruples.

j) what do you mean by regular expression?
SECTION B

2. Attempt any three of the following: 10 x 3 = 30

a). Write down the regular expression for
1. The set of all string over {a,b} such that fifth symbol from right is a.
2. The set of all string over {a,b} such that every block of four consecutive symbol contain
at least two zero.

b). Construct the NFA for the regular expression a/abb/a*b+ by using Thompson’s construction
methodology.
c). Eliminate left recursion from the following grammar
SAB , ABS | b , BSA | a

d). Discuss conversion of NFA into a DFA . also give the algorithm used in this conversion.
e). Explain non recursive predictive parsing. Consider the following grammar and construct the
predictive parsing table
ETE’
E’+TE’|€
TFT’
T’*FT’|€
FF*|a|b

Downloaded from : uptukhabar.net

 SECTION C
3. Attempt any one part of the following: 10 x 1 = 10
a). Give Operator –precedence parsing algorithm. Consider the following grammar and build up
operator precedence table. Also parse the input string (id+(id*id))
EE+T|T
TT*F|F
F(E)|id
b). For the grammar
SaAd |bBd |aBe |bAe Af , Bf
Construct LR(1) Parsing table .also draw the LALR table from the derived LR(1) parsing table.

4. Attempt any one part of the following: 10 x 1 = 10

a). What is postfix notations ? translate (C+D)*(E+Y) into postfix using syntax directed translation
scheme(STDS)
b). consider the following grammar EE+E | E*E|(E)|id . construct the SLR parsing table and
suggest your final parsing table.

5. Attempt any one part of the following: 10 x 1 = 10

a). Explain logical phase error and syntactic phase error . also suggest methods for recovery of error.
b). Generate three address code for C[A[I, j] ] = B[I ,j]+C[A[ I , j ] ]+D[ I + j ] (You can assume any data
for solving question , if needed) Assuming that all array elements are integer. Let A and B a 10 X 20
array with low1 =low2=1.

6. Attempt any one part of the following: 10 x 1 = 10

a). Give the algorithm for the elimination of local and global common Sub expression . discuss the
algorithm with the help of example also.
b). consider the following three address code segments
PROD := 0
I:= 1
T1:=4*I
T2:=addr(A)‐4
T3:=T2[T1]
T4:=addr(B)‐4
T5:=T4[T1]
T6:=T3*T5
PROD:=PROD +T6
I:=I+1
If i<=20 goto (3)
a. Find the basic blocks and flow graph of above sequence.
b. Optimize the code sequence by applying function preserving transformation and loop
optimization technique.

Downloaded from : uptukhabar.net

7. Attempt any one part of the following: 10 x 1 = 10
a). . Write short note on
i. Loop optimization
ii. Global data analysis

b). . Write short note on

i. Direct acyclic graph
ii. YACC parser generator

Downloaded from : uptukhabar.net