1
$\begingroup$

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:

Grammar

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.

$\endgroup$

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.