GATE CS 2015 Set 1 Q1 — Parsing (LL, LR)

In shift-reduce parsing, the contents of the parser stack always represent a prefix of a right-sentential form that does not extend past the right end of the rightmost handle. This is the definition of a viable prefix.

Specifically:

• A viable prefix is a prefix of a right-sentential form that can appear on the stack of a shift-reduce parser before a reduction takes place.
• If the stack contains a sequence of symbols $\alpha$, then $\alpha$ is a viable prefix.
• Furthermore, any prefix of a viable prefix is also a viable prefix. Since the stack grows from the bottom, any partial content of the stack from the bottom up to any position is also a viable prefix.

Thus, at any valid state during shift-reduce parsing, the stack contains only viable prefixes.

Therefore, Option C is the correct statement.