GATE CSE 2015 Set 1 | Question: 1‏3

Question

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

• 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

Comments

For viable prefix:

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

Refer these questions for practice:

https://gateoverflow.in/tag/viable-prefix

---

It was helpful @Kushagra गुप्ता Thanks!😊

Answer 1

Answer - C

Explanation:

A handle is actually the one which is always on the top of the stack. A viable prefix(prefix of the Right-hand side of a production or productions), is actually a prefix of the handle and so can never extend past the right end of the handle(i.e. the top of the stack).

The structure of the stack can be considered as a set of viable prefixes - 

$Stack = \{Prefix_1 Prefix_2 Prefix_3 \ldots Prefix_{n-1} Prefix_{n} \}$  and so it is not wrong to say that the stack contains a set of viable prefixes.

Comments

Now, viable prefix is defined in Ullman Compilers text as :

1. Possible strings which appear on the stack during shift reduce parsing
2. Or formally, viable prefix is a prefix of the right sentential form which does not move past the right end of the right most handle.

Well, with this being said lets us check the options:

(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.

Viable prefix as stated in point (1) as per Ullman, is present along the entire length of the stack. Neither at the bottom nor on the top.

So options (A) and (B) are clearly wrong.
Now,

(D) The stack never contains viable prefixes

is wrong as well as viable prefix is present along the entire length of the stack.

So option (C) remains, which is supposed to be correct. But why?

Suppose if :
$$X_0X_1X_2...X_{n-1}$$

is the contents of the stack at any point in time, [$X_i$ can be a variable or terminal],

Then,

$$X_0$$

$$X_0X_1$$

$$X_0X_1X_2$$

…

$$X_0X_1X_2...X_{n-1}$$

Are all viable prefix on the stack. Why? Because at sometime in the past,

each of $X_0..X_i$, $i=0,1,2..,n-1$ were the only contents on the stack.

Please correct me if I am wrong.

---

@HitechGa

prefix of the right sentential form which does not move past the right end of the right most handle.

Can any right sentential form contain more than one handle. If not, then why in definition everywhere rightmost handle is mentioned.

One more doubt, Can viable prefix contain $\epsilon$ but I am not finding anywhere written. ( as every prefix also contains $\epsilon$)? According to me it can contain as $\epsilon$ can also be a handle and prefix of $\epsilon$ is $\epsilon$.

https://www.geeksforgeeks.org/viable-prefix-in-bottom-up-parsing/

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

---

@Arpit Patel
Two handle are possible if your grammar is ambiguous…

Yes $\epsilon$ as a viable prefix is possible. You encounter it actually when at the very beginning your stack is $\text{empty}$ (or has the bottom of the stack pointer $\$$)

Answer 2

Ans C.

The following statement is true at any valid state in shift-reduce parsing:

The stack contains only a set of viable prefixes

In shift-reduce parsing, the stack is used to store a set of viable prefixes of the input string, which are sequences of terminals and non-terminals that can potentially form a valid sentence in the grammar. At any valid state in the parsing process, the stack contains a set of viable prefixes that have been generated so far, and the top of the stack represents the currently active prefix. The parser uses a set of shift and reduce actions to transform the input and stack, until the entire input string has been processed and a complete sentence is formed on the stack.

The other statements are not necessarily true, as viable prefixes can appear inside the stack as well, not only at the top or bottom. The stack may contain not only a set of viable prefixes but also non-viable prefixes.