Total No. of Questions: 6 Total No.
of Printed Pages:3
Enrollment No......................................
Faculty of Engineering
End Sem Examination Dec-2023
CB3CO10 Compiler Design
Programme: B.Tech. Branch/Specialisation: CSBS
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. In a compiler, keywords of a language are recognized during- 1
(a) Parsing of the program
(b) The code generation
(c) The lexical analysis of the program
(d) Dataflow analysis
ii. Regular expression are- 1
(a) Type 0 language
(b) Type 1 language
(c) Type 2 language
(d) Type 3 language
iii. A PDA machine configuration (p, w, y) can be correctly 1
represented as:
(a) (current state, unprocessed input, stack content)
(b) (unprocessed input, stack content, current state)
(c) (current state(current state, unprocessed input, stack content),
stack content, unprocessed input)
(d) None of these
iv. Which of the following statement is correct? 1
(a) All Regular grammar are context free but not vice versa
(b) All context free grammar are regular grammar but not vice
versa
(c) Regular grammar and context free grammar are the same
entity
(d) None of these
P.T.O.
[2] [3]
v. Which one of the following is a top-down parser? 1 OR iii. Write the CFG for the following language: 8
(a) An LALR(k) parser (a) L = {0i 1j 2i+j |i , j>0}
(b) An LR(k) parser (b) L = {an bm cm dn | m ,n > 0}
(c) Operator precedence parser
(d) Recursive descent parser Q.4 i. What is Syntax Directed Definition? Write its type. 3
vi. What is the similarity between LR, LALR and SLR? 1 ii. Construct the SLR(1) parsing table for the following grammar. 7
(a) Use same algorithm, but different parsing table S→L=R/R
(b) Same parsing table, but different algorithm L → R / id
(c) Their Parsing tables and algorithm are similar but uses top R→L
down approach OR iii. Construct the LR(0) parsing table for the following grammar 7
(d) Both Parsing tables and algorithm are different S → AA
vii. Who is responsible for the creation of the symbol table? 1 A → aA | b
(a) Assembler (b) Compiler (c) Interpreter (d) All of these
viii. Which of the following is drawback of static allocation strategy? 1 Q.5 i. Explain in detail different dynamic storage allocation strategies. 4
(a) Size of the data objects must be known at compile time ii. Generate the three-address code for the following code segment: 6
(b) Data structures cannot be created dynamically while (a < c and b < d) do
(c) Recursive procedure are restricted if a = 1 then c = c + 1;
(d) All of these else while ( a < = d) do
ix. The method which merges the bodies of two loops is? 1 a = a + 3;
(a) Loop rolling (b) Loop jamming OR iii. What are the features and capabilities of the symbol table? 6
(c) Constant folding (d) None of these
x. The graph that shows basic blocks and their successor relationship 1 Q.6 Write short note on any two:
is called ____________. i. Peephole Optimization 5
(a) DAG (b) Flow Graph ii. Design Issues of Code generator 5
(c) Control Graph (d) Hamilton Graph iii. Code Optimization Techniques 5
Q.2 i. Differentiate Compiler and Interpreter. 3 ******
ii. What is Finite State Machine (FSM)? Design a DFA to accept 7
the binary numbers which are divisible by 3.
OR iii. Explain in detail the various phases of compiler with an example. 7
Q.3 i. What is Bottom-Up Parsing? 2
ii. Check whether the given grammar is LL(1) or not 8
S → iEtSS' / a
S' → eS / E
E→ b
OR iii. Each of : 4 Marks (Grammar 3 Marks and tuple 1 Marks) 8
Marking Scheme
CB3CO10 (T) Compiler Design
Q.1 i) (c) the lexical analysis of the program 1 Q.4 i. Definition: 2 Marks
Types: 1 Marks 3
ii) (d) Type 3 language 1 ii. First & follow : 3 Marks
iii) (a) (current state, unprocessed input, stack content) LR(0) items: 2 Marks
1
parsing table: 2 Marks 7
iv) (a) All Regular grammar are context free but not vice versa OR iii. First & follow : 3 Marks
1
LR(0) items: 2 Marks
v) (d) Recursive descent parser 1 parsing table: 2 Marks 7
vi) (a) Use same algorithm, but different parsing table 1
Q.5 i. Each type storage allocation : 1 Marks (1 Mark*4)
vii) (b) Compiler 4
1
viii)
ii. Three-address code upto if condition 3 Marks
(d) All of the above 1 Three-address else condition to end 3 Marks 6
ix) (b) Loop jamming 1
OR iii. Features : 3 Marks
x) (b) Flow Graph Capabilities : 3 Marks 6
1
Q.6
Q.2 i. At least 3 difference each of : (1 Mark*3) i. Concept : 2 Marks
3 Objective: 1 Marks 5
ii. Definition: 2 Marks Optimization Techniques : 2 Marks
Finite Automata design: 5 Marks 7 ii. Explain each issue : (1 Mark*5) 5
OR iii. Phases: 5 Marks
Exam: 2 Marks 7 iii. Explain each technique : (1 Mark*5) 5
Q.3 i. Definition: (As per explanation) ******
2
ii. First: 2 Marks
Follow : 2 Marks
Parsing table: 4 Marks
8
