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!😊

---

@KUSHAGRA गुप्ता thanks bhai

 

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.

Answer 3

First: What is a viable prefix?

A viable prefix is any prefix of a right sentential form that does not go beyond the handle.

In simpler shift-reduce parser terms:

👉 At any valid moment, the contents of the stack form a viable prefix.

That is the key theorem used in LR parsing.

---

Statement 1:

“Viable prefixes appear only at the bottom of the stack and not inside”

❌ Incorrect

Why?

If the whole stack is a viable prefix, then many prefixes of the stack are also viable prefixes.

Example stack:

id + id

Then:

• id
• id +
• id + id

can all be viable prefixes (depending on grammar).

So viable prefixes are not only bottom portion.

They can occur as prefixes inside stack growth.

Hence false.

---

Statement 2:

“Viable prefixes appear only at the top of the stack and not inside”

❌ Incorrect

Same reason.

Viable prefixes are not only topmost suffixes.

They are related to prefixes from bottom of stack.

Top symbols alone may not form viable prefix.

Example:

Stack =

E + T

Top = T

But viable prefix usually refers to stack content from bottom, not isolated top portion.

Hence false.

---

Statement 3:

“The stack contains only a set of viable prefixes”

✅ Correct

This is the standard LR parsing property.

At every valid shift-reduce step:

• stack content itself is a viable prefix
• every prefix of stack is also viable prefix

Thus stack consists of symbols whose cumulative prefixes are viable prefixes.

This is exactly why LR automata recognize viable prefixes.

Hence TRUE.

---

Statement 4:

“The stack never contains viable prefixes”

❌ Incorrect

Completely opposite of LR theory.

In fact:

👉 LR parser stack always represents a viable prefix at any valid state.

So false.

Answer 4

 C

The stack of a shift-reduce parser always holds a viable prefix at any valid intermediate step. Thus, stack contains a set of viable prefixes.

Answer 5

• By definition in bottom-up compiler design, a viable prefix is a prefix of a right-sentential form that does not extend beyond the right end of the rightmost handle.

• In a shift-reduce (LR) parser, the sequence of grammar symbols on the parser stack always forms a viable prefix at any valid state.

• Since the stack contents from the bottom up to the current top always constitute a viable prefix, the entire stack holds a viable prefix (and any prefix of the stack contents is also a viable prefix).

• Options A, B, and D are false because viable prefixes are not restricted to just the top or bottom, and they are definitely present in the stack.

Correct Option: C. The stack contains only a set of viable prefixes

Answer 6