This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Predictive Top-Down Parsing”.
1. S → C C
C → c C | d
The grammar is
b) SLR(1) but not LL(1)
c) LALR(1) but not SLR(1)
d) LR(1) but not LALR(1)
Explanation: 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)
If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous.
3. Which of the following derivations does a top-down parser use while parsing an input string?
a) Leftmost derivation
b) Leftmost derivation in reverse
c) Rightmost derivation
d) Rightmost derivation in reverse
Explanation: Left to right constructing leftmost derivation of the sentence.
4. 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 *
Explanation: 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 ‘ *’
5. 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
Explanation: The prefixes on the stack of a shift-reduce parser are called viable prefixes.
6. 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 no. of successors of a node in an AST and a CFG depends on the input program
d) None of the mentioned
Explanation: Successors depends on input .
7. 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 B C D
(a) 2 3 1 4
(b) 2 1 4 3
(c) 2 4 1 3
(d) 2 3 4 1
Explanation: 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
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
Explanation: 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?
Explanation: 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
Explanation: All these are valid reasons.
Sanfoundry Global Education & Learning Series – Compilers.
To practice all areas of Compilers, here is complete set of 1000+ Multiple Choice Questions and Answers.