Total No. of Questions: 6 Total No.
of Printed Pages:3
Enrollment No......................................
Faculty of Engineering
End Sem (Even) Examination May-2022
IT3CO24 Compiler Design
Programme: B.Tech. Branch/Specialization: IT
Duration: 3 Hrs. Maximum Marks: 60
Note: All questions are compulsory. Internal choices, if any, are indicated. Answers of
Q.1 (MCQs) should be written in full instead of only a, b, c or d.
Q.1 i. The total number of states required to design minimum DFA of the 1
given regular expression (ab + ba + aa + bb):
(a) 3 (b) 4 (c) 2 (d) 6
ii. Number of final state require to accept zero length string i.e. ε in 1
minimal finite automata.
(a) 1 (b) 2 (c) 3 (d) None of these
iii. Which of the following is used as compiler constructor tool for 1
implementing various phases of compiler?
(a) LEX
(b) YACC
(c) Syntax directed translation
(d) All of these
iv. scanf("a = %d, &a = %x", a, &a); how many token are there in 1
given c statement:
(a) 9 (b) 5 (c) 10 (d) 6
v. Which of the following is not top down parsing technique? 1
(a) LL(1) parsing (b) Predictive parsing
(c) LR(0) parsing (d) Recursive Descent Parser
vi. Which of the following is correct in terms of their number of states? 1
(a) CLR(1)>=LR(0) (b) LR(0)=SLR(1)
(c) SLR(1)=LALR(1) (d) All of these
vii. For the following SDT X->YZ { Y.att= X.att} the Y is: 1
(a) Synthesized attribute (b) Inherited attribute
(c) S-attribute (d) Both (a) and (c)
P.T.O.
[2] [3]
viii. If a attribute A is L-attribute then, which of the following is true: 1 Q.3 i. What is role of lexical Analyser? 2
(a) A is Synthesized attribute ii. (a) Explain the concept of pass. 8
(b) A is Inherited attribute (b) What do you mean specification of tokens?
(c) A is synthesize and inherited only when it inherits only from its (c) Explain concept of One buffer and two buffer schemes.
parents and left siblings OR iii. Difference between compiler and interpreter. Also explain different 8
(d) A is synthesize and inherited only when it inherits only from its phases of Compiler with example.
parent
ix. The loop optimization method, loop jamming is also known as: 1 Q.4 i. What do you mean by Left Recursion? Explain with example. 2
(a) Loop fusion (b) Loop rolling ii. What are the different types of parsing technique? 3
(c) Constant folding (d) Both (a) and (b) iii. Show that following grammar is LL(1): 5
x. Code optimization helps to: 1 S->AaAb
(a) Improve the efficiency of code S-> BbBa
(b) Improve execution time A-> ɛ
(c) Reduce the size of the code B-> ɛ
(d) All of these OR iv. Check whether the grammar is SLR(1) or not: 5
S->(L)/a
Q.2 i. Convert the following regular expression to DFA- (0+1)*0(0+1)*. 2 L->L,S | S
ii. What is Leftmost and Rightmost derivation? Explain with example. 3
iii. Design Finite automata over the alphabets (0,1) which accept – 5 Q.5 i. Explain Syntax directed translation? 4
(a) Odd number of 1’s and any number of 0’s ii. Draw syntax tree and DAG for the expression: 6
(b) Number of 0’s mod 3=2 and number of 1’s mod 4=3 (a*b)+(c-d)*(a*b)+b.
OR iv. What is Difference between NFA and DFA with respect to 5 OR iii. Explain implementation of three address code for the expression: 6
transition function? Convert the following NFA to DFA- a+b*c/e^f+b*a
Q.6 Attempt any two:
i. Explain concept of symbol table. 5
ii. What are various loop optimization method? 5
iii. Explain parameter passing technique with example of any two. 5
******
Marking Scheme
Q.3 i. Any two role of lexical Analyser 2
IT3CO24 Compiler Design
1 mark for each (1 mark * 2)
Q.1 i. The total number of states required to design minimum DFA of the 1
ii. (a) Concept of pass 2 marks 8
given regular expression (ab + ba + aa + bb):
(b) Specification of tokens 2 marks
(a) 3
(c) Concept of One buffer and two buffer schemes 4 marks
ii. Number of final state require to accept zero length string i.e. ε in 1
OR iii. Difference between compiler and interpreter 1 mark 8
minimal finite automata.
Phases of Compiler 4 marks
(a) 1
Example 3 marks
iii. Which of the following is used as compiler constructor tool for 1
implementing various phases of compiler?
Q.4 i. Definition of Left Recursion 1 mark 2
(d) All of these
Example 1 mark
iv. scanf("a = %d, &a = %x", a, &a); how many token are there in 1
ii. Types of parsing technique 3
given c statement:
iii. Show that following grammar is LL(1): 5
(c) 10
For First and follow 2 marks
v. Which of the following is not top down parsing technique? 1
Parsing Table 3 marks
(c) LR(0) parsing
OR iv. Check whether the grammar is SLR(1) or not: 5
vi. Which of the following is correct in terms of their number of states? 1
For Canonical collection 2.5 marks
(d) All of these
For Table 2.5 marks
vii. For the following SDT X->YZ { Y.att= X.att} the Y is: 1
(b) Inherited attribute
Q.5 i. Syntax directed translation 4
viii. If a attribute A is L-attribute then, which of the following is true: 1
ii. Draw syntax tree and DAG for the expression: 6
(d) A is synthesize and inherited only when it inherits only from its
parent Syntax Tree 3 marks
ix. The loop optimization method, loop jamming is also known as: 1 DAG 3 marks
(a) Loop fusion OR iii. Explain implementation of three address code for the expression 6
x. Code optimization helps to: 1 2 marks for each implementation for three address code
(d) All of these (2 marks *3)
Q.2 i. Regular expression to DFA- (0+1)*0(0+1)*. 2 Q.6 Attempt any two:
ii. Definition Leftmost and Rightmost derivation 2 marks 3 i. Concept of symbol table. 5
Example 1 marks ii. Loop optimization method 5
iii. (a) Odd number of 1’s and any number of 0’s 2.5 marks 5 At least 5 methods 1 mark for each (1 mark * 5)
(b) Number of 0’s mod 3=2 and number of 1’s mod 4=3 iii. Parameter passing technique 3 marks 5
2.5 marks Example of any two 2 marks
OR iv. Difference between NFA and DFA 2 marks 5
Convert the following NFA to DFA 3 marks ******
