GO-Compiler1: Parsing-8

Question

Which of the following sentences regarding Viable prefixes is/are CORRECT?

1. Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser
2. Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the right-most handle
3. Viable prefixes can be recognized using a DFA
    
   • A. Only (i)
   • B. Only (ii)
   • C. Only (i) and (ii)
   • D. (i), (ii) and (iii)

Comments

$D$.

$I$ and $II$ is the definition of viable prefixes.

The set of viable prefixes for any grammar is a regular language so can be recognized by a $DFA$

---

Please provide some references for above statements.

---

https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/

Answer 1

Answer is D.

I : Definition of viable prefix -

Viable prefixes are the prefixes of right sentential forms that do not extend beyond the end of its handle.

i.e. a viable prefix either has no handle or just one possible handle on the extreme RIGHT which can be reduced.

II :  Definition of viable prefix -

viable prefixes are the set of prefixes of right sentential forms that can appear on the stack of a shift­reduce parser

III :The set of all viable prefixes of a context-free language is a REGULAR LANGUAGE. i.e., viable prefixes can be recognized by using a FINITE AUTOMATA.

So I, II & III are true.

References:

1. https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/
2. https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/handouts/100%20Bottom-Up%20Parsing.pdf