This set covers bottom-up parsing, the technique behind most production parser generators. It tests handles and viable prefixes, counting LR(0) items and states, how SLR, canonical LR and LALR place reduce actions, why conflicts arise and how YACC resolves them. It is useful for GATE CSE, where LR questions are frequent, for university compiler design exams and for interviews that probe parsing theory.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Shift-reduce parsing and handles
- Viable prefixes and LR(0) items
- Canonical collection and state counting
- SLR, CLR and LALR table differences
- Shift-reduce and reduce-reduce conflicts
- Operator precedence parsing
- YACC precedence and default conflict rules
Compiler Design MCQs with answers and explanations
Q1. A bottom-up parser effectively constructs which of the following?
a) A leftmost derivation in forward order
b) A rightmost derivation in forward order
c) A rightmost derivation in reverse
d) A leftmost derivation in reverse
Q2. In shift-reduce parsing, a handle is best defined as
a) any substring that matches the right side of some production
b) the leftmost terminal of the current input
c) the symbol on top of the parsing stack
d) a substring matching a production's right side whose reduction is one step of a reverse rightmost derivation
Q3. Which of the following is NOT one of the actions of a shift-reduce (LR) parser?
a) Expand a non-terminal using a production
b) Shift
c) Reduce
d) Accept
Q4. Which ordering correctly compares the sets of grammars handled by these parsers?
a) LR(0) < SLR(1) < LALR(1) < CLR(1)
b) SLR(1) < LR(0) < LALR(1) < CLR(1)
c) LR(0) < LALR(1) < SLR(1) < CLR(1)
d) LR(0) < SLR(1) < CLR(1) < LALR(1)
Q5. When canonical LR(1) states with identical cores are merged to form LALR(1) states, which new conflicts can appear?
a) Reduce-reduce conflicts only
b) Shift-reduce conflicts only
c) Both shift-reduce and reduce-reduce conflicts
d) No conflicts can ever appear
Q6. How many states are in the canonical collection of LR(0) items for the augmented grammar below?
S' -> S S -> ( S ) | a
a) 4
b) 6
c) 5
d) 7
Q7. In an SLR(1) parsing table, the reduce action for a complete item A -> alpha. in state I is entered under
a) every terminal of the grammar
b) every terminal in FIRST(A)
c) every terminal in FOLLOW(A)
d) only the lookahead carried by that item
Q8. By default, how does YACC resolve a shift-reduce conflict when no precedence rules apply?
a) It prefers the reduce
b) It prefers the shift
c) It reports an error and produces no parser
d) It picks randomly
Q9. By default, how does YACC resolve a reduce-reduce conflict?
a) It reduces by the production with the longer right side
b) It reduces by the production that appears earlier in the specification
c) It reduces by the production that appears later
d) It shifts instead of reducing
Q10. How many LR(0) items can be formed from the single production A -> X Y Z?
a) 3
b) 5
c) 1
d) 4
Q11. The grammar S -> L = R | R, L -> * R | id, R -> L is LALR(1). What happens if an SLR(1) table is built for it?
a) A reduce-reduce conflict arises on id
b) The table has no conflicts
c) A shift-reduce conflict arises on the token =
d) A conflict arises only on the end marker $
Q12. Which restriction must a grammar satisfy to be an operator grammar suitable for operator precedence parsing?
a) No right side contains epsilon or two adjacent non-terminals
b) Every production must be left recursive
c) The grammar must have only one non-terminal
d) Every right side must begin with a terminal
Q13. Which statement about LR grammars is true?
a) Every ambiguous grammar is LALR(1)
b) Every LR(1) grammar is also LL(1)
c) No ambiguous grammar can be LR(1)
d) Every SLR(1) grammar is also LL(1)
Q14. A viable prefix is
a) any prefix of the input string
b) a prefix of a right-sentential form that does not extend past the right end of its handle
c) a prefix of a leftmost sentential form
d) the part of the input not yet shifted
Q15. An LR parser for the grammar S -> a S | b parses the input aab. Excluding the final accept action, how many shift and reduce moves are made in total?
a) 5
b) 7
c) 4
d) 6
Q16. An LR(0) state contains the two complete items A -> c. and B -> c. When will an SLR(1) table have no conflict in this state?
a) When FOLLOW(A) and FOLLOW(B) are disjoint
b) When FIRST(A) and FIRST(B) are disjoint
c) Never, because two complete items always conflict
d) When A and B have the same FOLLOW set
Q17. In an LR(1) item [A -> alpha . beta, a], when does the lookahead a influence the parsing action?
a) Only when beta begins with a terminal
b) Only when beta is empty, that is, for a reduce
c) At every shift
d) Never; it is used only for building the goto table
Q18. A YACC specification declares %left '+' '-' on one line and %left '*' '/' on the next line. What does this mean?
a) + and - have higher precedence than * and /
b) All four operators have equal precedence
c) * and / are right associative
d) * and / have higher precedence than + and -, and all four are left associative
Quick revision notes
- Bottom-up parsing traces a rightmost derivation in reverse.
- Power: LR(0) < SLR(1) < LALR(1) < CLR(1) = LR(1); LALR and SLR have the same number of states as LR(0).
- A production with RHS of length n gives n + 1 LR(0) items.
- SLR places reduce A -> alpha under FOLLOW(A); CLR uses the item's own lookahead.
- Merging LR(1) states with the same core can introduce reduce-reduce but never shift-reduce conflicts.
- No ambiguous grammar is LR(k) for any k.
- YACC default: shift-reduce resolved as shift; reduce-reduce resolved in favour of the earlier production.
- In YACC, operators declared on later %left/%right lines get higher precedence.
Frequently asked questions
Why is LALR preferred over canonical LR in practice?
Canonical LR(1) tables can have many times more states than LR(0). LALR merges states with identical cores, giving tables as small as SLR while handling almost all programming language constructs that CLR handles.
What is a handle in shift-reduce parsing?
A handle is a substring of a right-sentential form that matches the right side of a production and whose reduction gives the previous step of a rightmost derivation. The parser's job is to find the handle at the top of the stack and reduce it.
Why does SLR fail on some grammars that LALR accepts?
SLR uses the whole FOLLOW set of a non-terminal as lookahead for every reduction of it, which can be too broad. LALR computes lookaheads specific to each state, so it avoids conflicts caused by tokens that can follow the non-terminal elsewhere but not in that context.
Comments
Post a Comment