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$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
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?
- 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
CLR(1) Canonical collection
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:
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."