Take the 2-minute tour ×

In Ullman's book of compilers, in shift reduce parsing, following definition of viable prefix is given :

"The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. An equivalent definition of a viable prefix is that it is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that sentential form. By this definition, it is always possible to add terminal symbols to the end of a viable prefix to obtain a right sentential form. Therefore, there is apparently no error as long as the portion of the input seen to a given point can be reduced to a viable prefix."

I can't understand this definition. Could someone explain the meaning of viable prefix with an example ?
In particular, please explain the meaning of

share|improve this question
This just shows how experts (book authors) can make the learning experience so terribly complicated. They seem to think that concise language is understandable language. –  Domi Feb 26 at 18:07
add comment

2 Answers

up vote 22 down vote accepted

EDIT (or actually rewrite): The sentence you asked for a clarification of is a major hairball! I needed a bit of a refresher on language and automata myself to pick that hairball apart. I found these lecture notes very useful in that regard.

It also doesn't make it any easier that the terms are defined in terms of top-down expansion, while rightmost derivation is typically used with bottom-up parsing!

I'll use the following expression grammar to illustrate:

    expr -> expr + term | term
    term -> term * factor | factor
    factor -> NUMBER | ( expr )
  • A right-sentential form is a sentential form which can be reached by rightmost derivation, which is another way to describe repeated expansion of only the rightmost nonterminal symbol when proceeding top-down. This is a rightmost derivation, and all the forms in it are therefore right-sentential forms:
    expr -> expr + term
         -> expr + term * factor
         -> expr + term * NUMBER
         -> expr + factor * NUMBER
         -> expr + NUMBER * NUMBER
         -> expr + term + NUMBER * NUMBER
         -> expr + NUMBER + NUMBER * NUMBER
         -> term + NUMBER + NUMBER * NUMBER
  • A prefix of a sentential form (whether right or otherwise) is a sequence of input symbols that reduces to zero or more leading symbols of that sentential form. The empty sequence is trivially a prefix of every sentential form, and the complete sequence of symbols making up a sentential form is also trivially a prefix of it.

  • A simple phrase is the expansion of a single nonterminal symbol that holds a place in a sentential form. For example, term * factor is a simple phrase because it is an expansion of term, and term itself occurs in three productions.

  • The handle of a sentential form is the leftmost simple phrase within that form. (I admin, find the term 'handle' somewhat confusing here.) In a rightmost derivation, the handle is easy to identify -- it's the sequence of symbols that resulted from the most recently expanded nonterminal. If you're working bottom-up the way a shift-reduce parser does, the handle is the simple phrase that needs to be reduced next. (Read the derivation table above from the bottom up, looking at which symbols were reduced, to see what I mean.)

  • A viable prefix of a right-sentential form is a prefix which does not extend beyond that form's handle -- in other words, that prefix is valid and contains no reducible simple phrases, with the possible exception of the handle itself if said prefix extends to exactly the end of the handle.

From a shift-reduce parser's point of view, as long as you have a viable prefix on the stack, you have not yet been forced to either reduce the (possibly incomplete) simple phrase on top of the stack to a new nonterminal or fail out of parsing if it can't be reduced. If shifting the next symbol would result in something other than a viable prefix, you must at that point either reduce or fail.

If you're parsing a context-free language, there is a rather convenient property that helps with the building of a table-driven shift-reduce parser: the set of all viable prefixes of a context-free language is itself a regular language! You can therefore build a finite automaton that recognizes the regular language of viable prefixes, and use it to determine when to shift and when to reduce. This combination of a stack and a finite state machine is essentially a push-down automaton, which is exactly the class of automaton needed to recognize a context-free language.

share|improve this answer
Check this. The portion of an item before the dot represents a viable prefix. A viable prefix is a string of grammar symbols that can comprise the first part of the right side of a production. Example: a, aX, aXY, and aXYb are viable prefixes of the production A -> aXYb. –  Shashwat Jan 15 '13 at 12:45
@Shashwat I believe that's another way of explaining the same thing: aXYb is a simple phrase since it makes up the right side of a production, and the 'dot' in the linked notes is effectively a cursor representing a point of progress through potential inputs. I suppose it's meaningful to discuss viable prefixes of an individual production (and useful when constructing a shift-reduce parser's finite state machine), but a finished shift-reduce parser is normally interested primarily in viable prefixes of a complete sentential form. –  Jeffrey Hantin Jan 15 '13 at 23:19
add comment

Consider the grammar given in book(i'm restating it here)

E -> E+T | T
T -> T*F | F 
F -> (E) | id

which is augmented by adding E' -> E in it

Now have a look at this derivation,

E' -> E
   -> E+T
   -> E+T*F

Claim E+T* is a viable prefix

Argument: This derivation is a right sentential form & E+T* is a prefix of it. Handle currently is T*F (as reducing T*F to T we can reach the start symbol & hence a successful parse)

And hence, E+T* is a viable prefix as it is a prefix of right sentential form & doesn't extend past the rightmost handle for this sentential form. :)

Other way to define it is:

The prefixes of right sentential forms that can appear on the stack of a shiftreduce
parser are called viable prefixes.
share|improve this answer
add comment

Your Answer


