Compilers Questions and Answers – Predictive Top-Down Parsing


This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses 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)
View Answer

Answer: a
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)
View Answer

Answer: a
Explanation: If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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 *
View Answer

Answer: b
Explanation: e.g. input is 3*4-5 r

     /  |  \
     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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: c
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?
b) Canonical LR ,LALR
c) SLR canonical LR
d) LALR canonical LR
View Answer

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
View Answer

Answer: d
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?
a) n/2
b) n-1
c) 2n-1
d) 2^n
View Answer

Answer: b
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
View Answer

Answer: d
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.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.