Project ForgeSign up free
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.

Start revising free