Compilers Multiple Choice Questions & Answers (MCQs) on “Intermediate code-Generation”.
1. The below grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
E -> number Eval number val
E E .val E .VAL E .val
E # E E .val E .VAL E .val
;
a) It detects recursion and eliminates recursion
b) It detects reduce-reduce conflict and resolves
c) It detects shift-reduce conflict and resolves the conflict in favor of a shift over a reduce action
d) It detects shift-reduce conflict and resolves the conflict in favor of a reduce over a shift action
Answer: c
Clarification: Yacc tool is used to create a LALR (1) parser. This parser can detect the conflicts but to resolve the conflicts it actually prefers shift over reduce action.
2. Assume the conflicts part (a) of this question are resolved and an LALR (1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 # 2 + 1. What precedence and associativity properties does the generated parser realize?
E -> number Eval number val
E E .val E .VAL E .val
E # E E .val E .VAL E .val
;
a) Equal precedence and left associativity; expression is evaluated to 7
b) Equal precedence and right associativity, expression is evaluated to 9
c) Precedence of ‘x’ is higher than that of ‘+’, and both operators are left associative; expression is evaluated to 7
d) Precedence of ‘ # ‘ is higher than that of ‘#’, and both operators are left associative; expression is evaluated to 9
Answer: b
Clarification: The grammar has equal precedence and it is also ambiguous. Since LALR (1) parser prefer shift over reduce so + operation will be executed here before). 2 + 1 = 3 & 3 # 3 = 9 also the operators are right associative.
3. Consider the following grammar.
S -> S * E
S -> E
E -> F + E
E -> F
F -> id
Consider the following LR (0) items corresponding to the grammar above.
(i) S -> S * .E
(ii) E -> F. + E
(iii) E “F + .E
Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?
a) (ii)
b) (i) and (iii)
c) (iii)
d) None of the mentioned
Answer: c
Clarification: If S -> S): E is in LR (0) then E -> F +: E will also be there because both of them has ‘: ‘ before E.
4. Consider the following grammar:
S -> FR
R -> * S | ε
F -> id
In the predictive parser table, M, of the grammar the entries M [S, id] and M [R, $] respectively.
a) {S ” FR} and {R ” ε}
b) {S ” FR} and {}
c) {S ” FR} and {R ” * S}
d) {F ” id} and {R ” ε}
Answer: a
Clarification: The predictive parser table is given as. Non Terminal) id $ S S “FR F F “id R R “) S R “! R “! So at M [ S, id] = { S ” FR} M [ R,$] = {R “!}.
5. Consider the following translation scheme.
S -> ER
R -> * E{print{’ * ’);
R | f
E -> F + E{print(’ + ’); | F
F -> (S) | id{print(id.value);}
Here id is a taken that represents an integer and id. value represents the corresponding integer value. For an input ‘2 * 3 + 4’, this translation scheme prints?
a) 2 * 3 + 4
b) 2 * + 3 4
c) 2 3 * 4 +
d) 2 3 4 + *
Answer: b
Clarification: Input string 2 ) 3 + 4 S ” ER FR idR {print(2)} id)ER {print())} id) F+ER {print(+)}id) id + ER {print(3)} id) id ) id +id So 2 )+ 3 4 are printed.
6. Consider the following C code segment.
for for if i # i } } }
Which one to the following false?
a) The code contains loop-in variant computation
b) There is scope of common sub-expression elimination in this code
c) There is scope strength reduction in this code
d) There is scope of dead code elimination in this code
Answer: d
Clarification: All the statements are true except option (There is scope of dead code elimination in this code ) since there is no dead code to get eliminated.
7. Which one of the following grammars generates the language L = (a i b i | i ! j}?
a)
b)
S -> aS | Sb | a | b
C -> aCb | a | b
A -> aA | ε
B -> Bb | ε
c)
d)
S -> AC | CB
C -> aCb |!
C -> aCb |!
A -> aA |!
A -> aA | a
B -> Bb |!
B -> bB | b
View Answer
Answer: d
Clarification: The grammar S -> AC CB
C ->aCb !
A ->aA a
B->” bB b
Consider string aaabb S -> AC AaCb AaaCbb Aaabb aaabb But string aabb S ” AC And ->his string is not derivable.
8. In the correct grammar above, what is the length of the derivation (number of steps starting from S to generate the string a l b m with l ! m?
a) max (l, m) + 2
b) l+m+2
c) l + m + 3
d) max (l, m) + 3
Answer: a
Clarification: It is very clear from the previous solution that the no. of steps required depend upon the no. of a’ s & b ‘ s which ever is higher & exceeds by 2 due to S ” AC CB & C “! So max(l , m) + 2.
9. Which one of the following is a top-down parser?
a) Recursive descent parser
b) Operator precedence parser
c) An LR(k) parser
d) An LALR(k) parser
Answer: a
Clarification: Clearly LR & LALR are not top down they are bottom up passers. Also not operator precedence parser. ut yes recursive descent parser is top down parser. Starts from start symbol & derives the terminal string.
10. Consider the grammar with non-terminals.
N = {S , C , S}, terminals T = {a, b , i , t, e}, with S as the start symbol, and the following of rules
S -> iCtSS1 | a
S1 -> eS | ε
C -> b
The grammar is NOTLL(1) because ________
a) It is left recursive
b) It is right recursive
c) It is ambiguous
d) It is not context-free
Answer: a
Clarification: The grammar has production S ” iCtSS1 here the right hand side of grammar has the same symbol as left side. So the grammar is left recursive. The grammar is not ambiguous.