I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the relationship between these parsers can be shown as:
LR(0) < SLR(1) < CLR(1) < LALR(1)
However, I am not very clear about exactly what being "powerful" means. I can guess following possibilities for being less powerful:
a. Cannot accept valid string
b. Accept valid string very late
c. Cannot reject invalid string
d. Reject invalid string very late
f. Involves SR, RR conflict for some grammars
I know point 5 holds for sure. However what exact effect a conflict have on parsing? Do we say that parser is non deterministic and/or requires backtracking to steps involving conflict or we simply say parser of certain type cannot be simply prepared for given grammar?
Which of first four (a,b,c,d) holds? I tried solving one example, for which I prepared both SLR(1) and CLR(1) parsing table. I SLR(1) parsing table had reduce move for state
), whereas CLR(1) did not. I took an invalid string for which SLR(1) was able to incorrectly reduce when stack top was state
2and next input symbol was
). But eventually it failed to shift
). So, in the end rejecting the string. However, CLR(1) rejected the string right away without incorrectly reducing. Is this what all can happen? Or there can be an invalid string which SLR(1) may incorrectly accept (point c)? Or points (a) and (b) do also hold?
I feel only point (d) holds. Also SLR(1) and CLR(1) can accept valid string in same number of steps (that is, point b does not hold). Am I right with what I feel?
I concluded following for above points (a) through (d). Need someone to confirm:
(a) SLR(1) always accept valid strings as it will be able to correctly do shift reduce moves for such strings. So, point (a) is incorrect.
(b) Accepting valid strings late can only happen when valid string causes traversing through incorrect reduce moves of SLR(1) parsing table. However, this never happens. Valid strings can never be accepted by going through incorrect reduce move cells of parsing table. Those are only hit by invalid strings. Hence, point (b) is also wrong.
(c) SLR(1) can never fail to reject invalid string as it will always fail to shift some terminal in such string. So, point c is also not correct.
(d) SLR may reject some invalid strings late since it may do incorrectly do some reductions. So only point d is correct.
Another (possibly last) doubt
Though in (c) above, I said SLR(1) can never fail to reject invalid string, I doubt its correctness. If a parser accepts invalid string, we simply say that the parser does not implement that grammar, right? But my doubt is whether such parser always involve SR / RR and such "conflict is the only reason to fail to reject invalid string"? We know that SLR can do some incorrect reductions. So, "can't such incorrect reduction be reason for acceptance of invalid string"? Or in other words, for some invalid string, can't SLR shift all of it (so that no terminal will remain un-shifted in the end), and finally do incorrect reduction of whole invalid input string to starting symbol S, thus accepting invalid string? After all we know SLR parser may do some incorrect reductions. Then, why it cant do incorrect reduction of whole invalid input string to the start symbol?