GATE CS 2015 Set 1 Q.23 (CS Q.13): Parsing and Syntax Analysis (LL and LR)

Which one of the following is TRUE at any valid state in shift-reduce parsing?

Viable prefixes appear only at the bottom of the stack and not inside

Viable prefixes appear only at the top of the stack and not inside

The stack contains only a set of viable prefixes

The stack never contains viable prefixes

Official answer and solution

Solution

Recall the fundamental invariant of shift-reduce LR parsers regarding parser stack contents.

By definition in compiler theory:

A viable prefix of a right-sentential form is a prefix that does not extend beyond the right end of the handle.
As long as no error has occurred, the string of grammar symbols on the parser stack of a shift-reduce parser is always a viable prefix of some right-sentential form.
When the parser shifts a terminal or reduces by a production, the new stack contents continue to form a viable prefix.

Therefore, at any valid parsing state, the stack contains only a set of viable prefixes (option C).

Final answer

Common trap

Believing viable prefixes reside only at the top or bottom of the stack, rather than the entire stack prefix.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.