0
$\begingroup$

Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as below.

In the bottom up parser section, it gives following definition of handle:

  • Handle: If $S\xrightarrow{*rm} \alpha A \omega \xrightarrow{rm} \alpha\beta w$, then production $A\rightarrow \beta$ in the position following $\alpha$ is a handle of $\alpha\beta\omega$. For covenience, we refer to the body $\beta$ rather than $A\rightarrow\beta$ as a handle. enter image description here

(Above, $\xrightarrow{*rm}$ means rightmost derivation of length $n$ and $\xrightarrow{rm}$ means rightmost derivation of length 1)

Then after some pages, in SLR parser section, it gives below definitions:

  • Viable prefix: A viable prefix is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form.
  • Valid item: We say item $A\rightarrow\beta_1.\beta_2$ is valid for a viable prefix $\alpha\beta_1$ if there is a derivation $S'\xrightarrow{*rm}\alpha A\omega\xrightarrow{rm}\alpha\beta_1\beta_2\omega$

The book further says:

The fact that $A\rightarrow \beta_1.\beta_2$ is valid for $\alpha\beta_1$ tells us a lot about whether to shift or reduce when we find $\alpha\beta_1$ on the parsing stack. In particular, if $\beta_2\neq \epsilon$, then it suggests that we have not yet shifted the handle onto the stack, so shift is our move. If $\beta_2=\epsilon$, then it looks as if $A\rightarrow\beta_1$ is the handle, and we should reduce by this production.

Doubts:

  1. In most discussions, the book uses all these definitions together. However, above the definitions are given separately but not together. How can I relate them together? Can I relate them as follows:

    a. In the definition of handle, can we say $A\rightarrow\ \beta$ is a valid item?
    b. In the definition of valid item, can we say $\beta_1.\beta_2$ is a handle?

Definition of handle is given in the section 4.5.2. (Section 4.5 is of bottom up parsers) Definition of viable prefix and valid item is given in the section 4.6.5 (Section 4.6 is of SLR parsers). So none of these definitions are given in the context of LR(1) items or CLR(1) or LALR(1) items. So I want to know whether these definitions applies to LR(1) items too without modifications and if not then what will be corresponding definitions for LR(1) items. Below questions detail this doubt.

  1. For canonical collection state with final item $E\rightarrow \gamma$, SLR parser reduces $\gamma$ to $E$, if next input symbol is in $FOLLOW(E)$. Does the above definition of valid items adheres with this? That is, does that definition gives sense that $FIRST(\omega)\in FOLLOW(A)$? (In other words, does this definition applies to LR(0) items?) If yes, how? I feel, this definition means $FIRST(\omega) = LOOKAHEAD(A) \neq FOLLOW(A)$, and hence it is talking about LR(1) items and applies to CLR/LALR parsers, but not to SLR parsers, as stated by the book. Am I wrong? If yes, how? Do these definition apply to both LR(0) and LR(1) items equally and I am unable to see how? If even that is not the case (that is above definitions apply only to LR(0) items, not to the LR(1) items), how we can give equivalent definitions for LR(1) items?
$\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.