Compiler Design
Lexical Analysis & Parsing
GATE 2015
Hard
Which one of the following is TRUE at any valid state in shift-reduce parsing?
- AViable prefixes appear only at the bottom of the stack and not inside
- BViable prefixes appear only at the top of the stack and not inside
- The stack contains only a set of viable prefixes
- DThe stack never contains viable prefixes
Explanation
By definition, at every valid configuration of a shift-reduce (LR) parser, the entire stack content (from bottom to top) is always a viable prefix — a prefix of some right-sentential form that can still be extended to derive a valid string without having to pop past a syntax error. This is the core invariant that makes LR parsing well-defined.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.