Compilers Multiple Choice Questions & Answers (MCQs) on “Predictive Top-Down Parsing”.
1. What is the grammar for the below equations?
S → C C C → c C | d
a) LL(1)
b) SLR(1) but not LL(1)
c) LALR(1) but not SLR(1)
d) LR(1) but not LALR(1)
Answer: a
Clarification: Since there is no conflict, the grammar is LL (1) hence a predictive parse table with no conflicts can be constructed.
2. Which of the following statements is false?
a) Unambiguous grammar has both kind of derivations
b) An LL(1) parser is a top-down parser
c) LALR is more powerful than SLR
d) Ambiguous grammar can’t be LR(k)
Answer: a
Clarification: If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous.
3. Given the following expression grammar:
E -> E * F | F + E | F F -> F - F | id
Which of the following is true?
a) * has higher precedence than +
b) – has higher precedence than *
c) + and — have same precedence
d) + has higher precedence than *
Answer: b
Clarification: e.g. input is 3*4-5 r
E
/ |
E * F
| / |
F F - F
| | |
id (3) id (4) id (5)
First ‘- ‘ is be evaluated then ‘ *’
4. Which one of the following is true at any valid state in shift-reduce parsing?
a) At the bottom we find the prefixes
b) None of the mentioned
c) Stack contains only viable prefixes
d) Stack consists of viable prefixes
Answer: c
Clarification: The prefixes on the stack of a shift-reduce parser are called viable prefixes.
5. In the context of abstract-syntax-tree and control-flow-graph. Which one of the following is true?
a) In both AST and CFG if node N2 be the successor of node N1
b) For any input program, neither AST nor CFG will contain a cycle
c) The max number of successors of a node in an AST and a CFG depends on the input program
d) None of the mentioned
Answer: c
Clarification: Successors depends on input .
6. Match the following.
List-I List-II A. Lexical analysis 1. Graph coloring B. Parsing 2. DFA minimization C. Register allocation 3. Post-order traversal D. Expression evaluation 4. Production tree
a) A – 2, B – 3, C – 1, D – 4
b) A – 2, B – 1, C – 4, D – 3
c) A – 2, B – 4, C – 1, D – 3
d) A – 2, B – 3, C – 4, D – 1
Answer: c
Clarification: The entire column an items matches the Column B items in a certain way.
7. Which of the following pairs is the most powerful?
a) SLR, LALR
b) Canonical LR ,LALR
c) SLR canonical LR
d) LALR canonical LR
Answer: c
Explanation parser algorithm is simple.
8. Consider the following grammar G.
S → F ⎪ H F → p ⎪ c H → d ⎪ c
Which one is true?
S1: All strings generated by G can be parsed with help of LL (1).
S2: All strings generated by G can be parsed with help of LR (1).
a) Only S1
b) Only S2
c) Both S1 & S2
d) None of the mentioned
Answer: d
Clarification: There is ambiguity as the string can be derived in 2 possible ways.
First Leftmost Derivation
S → F
F → c
Second Leftmost Derivation
S → H
H → c.
9. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production to parse a string with n tokens?
a) n/2
b) n-1
c) 2n-1
d) 2^n
Answer: b
Clarification: The moves are n-1.
10. Consider the following two sets of LR (1) items of an LR (1) grammar.
X -> c.X, c/d X -> .cX, c/d X -> .d, c/d X -> c.X, $ X -> .cX, $ X -> .d, $
Which one is false?
1. Cannot be merged since look ahead’s are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.
a) 1 only
b) 2 only
c) 1 and 4 only
d) 1, 2, 3 and 4 only
Answer: d
Clarification: All these are valid reasons.