Which one of the following is TRUE at any valid state in shift-reduce parsing?
2015
Which one of the following is TRUE at any valid state in shift-reduce parsing?
Answer: C. The stack contains only a set of viable prefixes — Key fact: At any valid shift-reduce parser state, the symbols on the stack form a viable prefix. Viable prefix definition: a prefix of a right-sentential form…
- A.
Viable prefixes appear only at the bottom of the stack and not inside
- B.
Viable prefixes appear only at the top of the stack and not inside
- C.
The stack contains only a set of viable prefixes
- D.
The stack never contains viable prefixes
Attempted by 48 students.
Show answer & explanation
Correct answer: C
Key fact: At any valid shift-reduce parser state, the symbols on the stack form a viable prefix.
Viable prefix definition: a prefix of a right-sentential form that does not extend beyond a handle and therefore can legitimately appear on the parser stack.
Why this holds: a shift pushes a grammar symbol and preserves the viable-prefix property; a reduce replaces a handle by its left-hand side, producing another viable prefix. These operations keep the stack content always viable.
Consequence: the stack never contains non-viable strings, so the correct statement is that the stack contains only viable prefixes.
A video solution is available for this question — log in and enroll to watch it.