Compilers Multiple Choice Questions & Answers (MCQs) on “Predictive Top-Down Parsing”.
1. Find the TRUE statement?
I. There exist parsing algorithms for some programming languages which has O(3) complexity. II. A programming language which allows recursion can be implemented with static storage allocation. III. No L-attributed definition can be evaluated in The framework of bottom-up parsing. IV. Code improving transformations can be performed at both intermediate code level and source Language.
a) I and II
b) I and IV
c) III and IV
d) I III and IV
Answer: b
Clarification: In recursion, space used but recursive call can’t be calculated by the compiler.
2. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
a) Position where next reduce or shift operation will occur
b) The next step has use of Non-terminal for reduction
c) Used for reduction in a coming-up step along with a position in the sentential form where the next shift or reduce operation will occur
d) Used in the next step for reduction along with a position in the sentential form where the right hand side of the production may be found
Answer: d
Clarification: the next step in LR parsing shall have a Reduction.
3. 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: Recursive Descent also known as top down parsing also known to be LL(1).
Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Regular is LR(1) grammar.
4. Which of the following is TRUE?
a) Both P and Q are true
b) P is true and Q is false
c) P is false and Q is true
d) Both P and Q are false
Answer: c
Clarification: Ambiguity can be seen in regular grammar
S → aA/a
A → aA/ε
In above grammar, string ‘a’ has two leftmost
derivations.
S → aA
S → a
S->a (using A->ε).
5. Consider the grammar defined by the following production rules:
S --> T * P
T --> U | T * U
P --> Q + P | Q
Q --> Id
U --> Id
Which one of the following is TRUE?
a) + is left associative, while ∗ is right associative
b) + is right associative, while ∗ is left associative
c) Both + and ∗ are right associative
d) Both + and ∗ are left associative
Answer: b
Clarification: It is associative we can see and tell.
Second productions latter part shows left recursion and is left associative.
6. The grammar A → AA | (A) | e is not suitable for predictive-parsing because the grammar is?
a) Ambiguous
b) Left recursive
c) Right recursive
d) An operator grammar
Answer: b
Clarification:
A ::= A a
| b is the left recursive language.
7. Consider the grammar.
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are __________
a) n, E + n and E + n × n
b) n, E + n and E + n × n
c) n, n + n and n + n × n
d) n, E + n and E × n
Answer: d
Clarification: E → E + n {Applying E → E + n }
→ E + E * n {Applying E → E * n }
→ E + n * n {Applying E → n }
→ n + n * n {Applying E → n }.
8. Which grammar rules violate the requirements of an operator grammar?
1. P → Q R 2. P → Q s R 3. P → ε 4. P → Q t R r
a) 1 only
b) 1 and 3 only
c) 2 and 3 only
d) 3 and 4 only
Answer: b
Clarification: Top down parsin: We begin with the start symbol and compare the right side of the different productions against the first piece of input to see which of the productions should be used.
9. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
a) Removing left Recursive alone
b) Factoring the grammar alone
c) Along with removing left recursion we also perform the factoring of the grammar
d) None of the mentioned
Answer: d
Clarification: Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.
10. In a bottom-up evaluation of a syntax directed definition its inherited attributes can do which of the following?
a) Always evaluated
b) Can be evaluated if the definition is L attributed
c) Can be evaluated if the definition has synthesized attributes
d) Never be evaluated
Answer: b
Clarification: A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes. Also the L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them.