1. 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
Explanation: 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 }.
2. 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
Explanation: 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.
3. 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
Explanation: Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.
4. 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
Explanation: 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.
5. 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)
Explanation: Since there is no conflict, the grammar is LL (1) hence a predictive parse table with no conflicts can be constructed.
6. 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)
Explanation: If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous.
7. 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.
8. 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
Explanation: Successors depends on input .
9. 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.
10. 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
Explanation: The moves are n-1.