2
$\begingroup$

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont:

Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$ and a is in $FOLLOW(A)$. In some situations, however, when state i appears on top of the stack, the viable prefix $βα$ on the stack is such that $βA$ cannot be followed by $a$ in any right-sentential form. Thus, the reduction by $A→a$ should be invalid on input $a$.

Let us consider the below grammar and its LR0 items:

$S→L=R | R$
$L→ *R | id$
$R→L$

enter image description here

In state 2 we had item $R→L$., which could correspond to $A→a$ above, and $a$ could be the $=$ sign, which is in $FOLLOW(R)(=FOLLOW(L))$. Thus, the SLR parser calls for reduction by $R→L$ in state 2 with $=$ as the next input (the shift action is also called for, because of item $S→L.=R$ in state 2). However, there is no right-sentential form of the grammar in that begins $R=⋯$.. Thus state 2, which is the state corresponding to viable prefix L only, should not really call for reduction of that $L$ to $R$.

DOUBTS

  1. I didnt get:

    However, there is no right-sentential form of the grammar in that begins $R=⋯$..

    Do the authors mean that there is no productions with its right hand side starting with $R$? If yes, what is the significance of this statement?

  2. Are lookaheads (as in case of LR(1) items for CLR(1) and LALR(1) parsers) always subset of FOLLOW of production heads (that is non terminal of the left of production)? If yes, why so? That is which of the FOLLOW of production heads are not lookaheads?

Edit 1: Doubt extended based on rici's answer and comments (deprecated, see Edit 2)

I understood following comment by rici:

ll you need to do is try a few derivations to see (1). $S→L=R$ cannot derive a sentential firm starting with $R$ and after $S→R$, the only possible next derivation results in $L$.

However, this is specific to this particular grammar. I wanted generalized characteristics of non FOLLOW lookaheads and more importantly "generalized reason of why they happen". So I thought better to try some example and see why particular string is accepted and rejected by hitting and non hitting this particular production $R\rightarrow L$. I prepared canonical collections.

SLR(1) Canonical Collection

enter image description here

CLR(1) Canonical collection

enter image description here

I2 of SLR involves SR conflict for =. So better look for string containing $, which is also in FOLLOW(R).

Stack contents while parsing string *id$ by CLR (Reduced number of stack content means reduce move, increased number of stack content means shift move)
================================================
[0]
[0,*,4] (shift * and transit to state 4)
[0,*,4,id,5] (shift id and transit to state 5)
(5,$)= no shift/reduce move ---> reject string


Stack contents while parsing string *id$ by SLR  
================================================
[0]
[0,*,4]
[0,*,4,id,5] (shift id and transit to state 5)
[0,*,4,L]
[0,*,4,L,8]
[0,*,4,R]  (Reduce L to R)
[0,*,4,R,7]
[0,L]   (Reduce *R to L)
[0,L,2] (Transit to state 2)
[0,R]
[0,R,3]
[0,S]
Accept

Looking at grammar, I felt CLR also should accept the string, as the parse tree will be:

  S
  |
  R
  |
  L   
/  \ 
|   R
|   |
|   L
|   |
*  id  

Then why CLR rejects the string? Did I make any mistake above?


Edit 2 (Both SLR and CLR will do reduction $R\rightarrow L$ in state 2 with $=$ as the next input) (Deprecated see edit 3, sorry for mistakes)

I made a mistake in above CLR(1) canonical collection. The correct one will be as follows:

enter image description here

As you can see, CLR(1) automata contains $R\rightarrow L.,=/\$$ in $I_2$. So, similar to SLR(1), CLR(1) will also do the reduction $R\rightarrow L$ on next input symbol $=$ Right? Or am I doing some mistake again?


Edit 3

There was a mistake in $I_0$. $I_0$ should not contain $R\rightarrow .L,=$. After trying out several strings & parsing, I feel I came to know why SLR(1) is weaker than CLR(1), or why & when some FOLLOWS(head of final item) are invalid. I wanted to generalize why and where such FOLLOW occur & wanted to put in precise words to get clear understanding. I need confirmation for following:

"The idea that the body / right hand side of the production can be reduced to the head of the production whenever the next input symbol is in the FOLLOW of the head, is itself wrong. The FOLLOW set of the head forms the set of terminals. which when appear as next input symbol, the tail "may be" reduced to head, however not at all time. Each FOLLOW symbol is valid next input terminals for reduction only at specific position / state / point in the parse. This fact is ignored by SLR parser and is captured by CLR by having different set of lookaheads for same LR(1) item in different closures. Those different closures are nothing but different points in parse, whereas lookaheads are subset of FOLLOW of head which are valid next input symbols for reduction at that point in the parse."

$\endgroup$

1 Answer 1

4
$\begingroup$
  1. No, the authors meant that there is no right-sentential form of the grammar that starts with R =. That is, the = in that observation is a literal terminal symbol.

    A right-sentential form is a sequence of terminal and/or non-terminal symbols which might appear in a rightmost derivation. So what they are saying is that no rightmost derivation of that grammar contains an intermediate sequence starting with the two symbols R =.

    That's fairly easy to prove, and if you still don't feel confident about what this statement neans, proving the assertion is probably a useful exercise.

  2. The lookahead set for an LR item $A\to \alpha .$ is most certainly a subset of $FOLLOW(A)$, since whatever comes next in a valid input obviously follows the non-terminal $A$, and $FOLLOW(A)$ is defined as the set of terminals which might follow $A$ in some right-sentential form. (The lookahead for the item $A\to \alpha .$ is the set of terminals which might follow this particular $A$ when the parser is in this state.)

    But it is not necessarily the case that every terminal in $FOLLOW(A)$ is in that lookahead set, and this example is intended to be precisely an illustration of that fact.

$\endgroup$
10
  • $\begingroup$ (1) I felt the author was not talking about right sentential form only because I am not able to see how it is immediately (visually, without requiring some proof) evident from grammar that there is no right sentential form that begins with R= (2) " which of the FOLLOW of production heads are not lookaheads?" = what are the characteristics of such non lookahead FOLLOW symbols so that merely looking at grammar we can say this is FOLLOW but not lookahead, without requiring to prepare LR(1) items? $\endgroup$
    – RajS
    May 24, 2019 at 11:42
  • $\begingroup$ @anir: all you need to do is try a few derivations to see (1). $S\to L=R$ cannot derive a sentential firm starting with $R$ and after $S\to R$, the only possible next derivation results in $L$. How is that not visually evident? $\endgroup$
    – rici
    May 24, 2019 at 13:03
  • $\begingroup$ @anir: as for (2), I don't think you can do that in any way which is not equivalent to producing the LR(1) parser. But note that it is the parser's states you need to compute. A state is (equivalent to) a set of items, but a given item can be in more than one such set, with different lookaheads in each case. $\endgroup$
    – rici
    May 24, 2019 at 13:09
  • 1
    $\begingroup$ @anir: sort of. For many grammars, it will turn out that the FOLLOW sets overestimate the set of possible successor tokens for a prefix. But the lookaheads computed by the LR(1) algorithm are not necessarily perfect either; there can still be parsing conflicts, either because more lookahead -- possibly an unlimited amount -- is needed to decide whether to reduce, or because the grammar is not deterministic. All you can say is that LR(1) discriminates better than SLR(1). $\endgroup$
    – rici
    May 26, 2019 at 18:27
  • 1
    $\begingroup$ Also, a parsing state is a slightly more subtle concept than "a point in the parse". There are a potentially unlimited number of points in a parse, since most languages don't have a limit on the length of a sentence, but the parsing automaton is finite, meaning that there is a finite number of parsing states. It's this fact which makes the parsing algorithm easy to implement. $\endgroup$
    – rici
    May 26, 2019 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.