retagged by
18,907 views
53 votes
53 votes

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

  1. Viable prefixes appear only at the bottom of the stack and not inside
  2. Viable prefixes appear only at the top of the stack and not inside
  3. The stack contains only a set of viable prefixes
  4. The stack never contains viable prefixes
retagged by

2 Answers

Best answer
71 votes
71 votes

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.

edited by
1 votes
1 votes
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:

Related questions

2 votes
2 votes
3 answers
1
80 votes
80 votes
7 answers
2
makhdoom ghaya asked Feb 13, 2015
28,739 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...