I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I present my doubts here in a systematic manner, with a hope for clarification.

Viable Prefixes: The set of prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.

This is the actual definition. No problem with it, since it is a definition after all.

An equivalent definition of a viable prefix is that it is a prefix of a right-sentential form that does not continue past the right end of the rightmost handle of that sentential form.

I do not quite understand why "the rightmost handle"? And why not the leftmost handle?

Is it so because of grammars like:


can have the two possible rightmost derivations for $id_1+id_2*id_3$:

Derivation 1 Derivation (1)

enter image description here Derivation (2)

where for the right sentential form $E+E*id_3$ there are two handles:

left: $\require{color}\colorbox{pink}{E+E}*id_3$ and

right: $E+E*\require{color}\colorbox{pink}{$id_3$}$

By this definition, it is always possible to add terminal symbols to the end of a viable prefix to obtain a right-sentential form.

Is it something like this, Suppose

$$(1) S \xrightarrow [\text{rm}]{\text{*}} ABCDE \xrightarrow[\text{rm}]{\text{*}} ABpqr$$

$$(2) S \xrightarrow [\text{rm}]{\text{*}} ABCDE \xrightarrow[\text{rm}]{\text{*}} ABxyz$$

So adding terminals $pqr$ or $xyz$ to the viable prefix $AB$ we can get 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.

This I feel from the actual definition is true, because a viable prefix is a prefix appearing on the stack...

Is my understanding fine? If not please rectify me.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.