GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 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 the right sentential forms of a grammar 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

Answer 2

A viable prefix is a legitimate prefix that could lead to a handle.

Since handle will always be found on top of the stack, all the viable prefixes of it can appear below it in the stack. If handle is not found yet, the stack would contain just viable prefixes.

I is true.

---

Viable prefix can't extend past the handle. That's why it's a prefix!

II is true.

---

The set of all viable prefixes of a language is a Regular Language, so it can be recognised by a DFA.

III is true.

---

Option D