GATE CSE MCQs - Compiler Design: Parsing, SDT and Code Optimization

Q1. How many tokens does a C lexical analyser produce for this statement?

if (x >= 10) y = x * 2;

a) 13

b) 12

c) 11

d) 10

Q2. Which formal model does a lexical analyser generator such as Lex use to recognise tokens?

a) Finite automata built from regular expressions

b) Pushdown automata

c) Turing machines

d) Context-free grammars with LR tables

Q3. For the grammar S → AB, A → a | ε, B → b | ε, what is FIRST(S)?

a) {a, b, ε}

b) {a, ε}

c) {a, b}

d) {a}

Q4. For the grammar E → T E', E' → + T E' | ε, T → id, what is FOLLOW(T)?

a) {id, +, $}

b) {+, $}

c) {+}

d) {$}

Q5. Why is the grammar S → S a | b not LL(1)?

a) It has an ε-production

b) It is left recursive

c) It is ambiguous

d) It is not context-free

Q6. Which relationship between the classes of grammars accepted by bottom-up parsers is correct?

a) LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)

b) LR(0) ⊂ LALR(1) ⊂ SLR(1) ⊂ CLR(1)

c) SLR(1) ⊂ LR(0) ⊂ LALR(1) ⊂ CLR(1)

d) LR(0) = SLR(1) ⊂ LALR(1) = CLR(1)

Q7. A grammar is CLR(1) with no conflicts. When its LR(1) states with identical cores are merged to build the LALR(1) parser, which conflict can appear?

a) Shift–reduce only

b) Both shift–reduce and reduce–reduce

c) No conflict can appear

d) Reduce–reduce only

Q8. How do the number of states in the SLR(1), LALR(1) and CLR(1) parsers for a grammar compare?

a) SLR = LALR ≤ CLR

b) SLR = LALR = CLR always

c) CLR ≤ LALR = SLR

d) SLR ≤ LALR ≤ CLR, all usually different

Q9. For the ambiguous grammar E → E + E | id, how many distinct parse trees does the string id + id + id + id have?

a) 3

b) 6

c) 4

d) 5

Q10. Which statement about S-attributed definitions is correct?

a) They use only inherited attributes

b) They need a separate pass over a dependency graph with cycles

c) They cannot be evaluated by any parser

d) They use only synthesized attributes and can be evaluated during bottom-up parsing

Q11. The translation scheme below is used in a bottom-up parse of the input 2 + 3 * 4. What does it print?

E → E + T   { print('+') }
E → T
T → T * F   { print('*') }
T → F
F → num     { print(num.val) }

a) 2 3 4 * +

b) + 2 * 3 4

c) 2 + 3 * 4

d) 2 3 + 4 *

Q12. How many nodes, including leaves, are in the DAG for the expression a = (b * −c) + (b * −c), not counting the assignment?

a) 8

b) 5

c) 4

d) 6

Q13. How many basic blocks does this three-address code have?

1: i = 1
2: j = 1
3: t1 = 10 * i
4: t2 = t1 + j
5: j = j + 1
6: if j <= 10 goto 3
7: i = i + 1
8: if i <= 10 goto 2
9: x = 0

a) 4

b) 6

c) 5

d) 3

Q14. In this basic block only b is live at the exit. Which variables are live at the entry?

a = b + c
d = a - e
b = d * 2

a) {b}

b) {a, b, c}

c) {b, c, d, e}

d) {b, c, e}

Q15. Replacing the expression i * 4 inside a loop with a variable that is increased by 4 on each iteration is an example of:

a) Loop unrolling

b) Strength reduction

c) Dead code elimination

d) Constant folding