In what sense a type of parser is less power than the other?

Question

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

Doubts

1. 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?

2. 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 2 and terminal ), whereas CLR(1) did not. I took an invalid string for which SLR(1) was able to incorrectly reduce when stack top was state 2 and 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?

Edit

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?

Answer 1

Assuming that by "CLR" you mean "canonical LR", then you have the order wrong; the correct containment order is

$LR(0) < SLR(1) < LALR(1) < CLR(1)$

A possibly more meaningful way of saying that is that if we define $G_X$ to be the set of context-free grammars which can be parsed with algorithm $X$, then

$G_{LR(0)} \subset G_{SLR(1)} \subset G_{LALR(1)} \subset G_{CLR(1)}$

That containment sequence does not apply to languages. If we say that $L_X$ is the set of languages for which there is a grammar in $G_X$, then we will find that

$L_{LR(0)} \subset L_{SLR(1)} \subseteq L_{LALR(1)} \subseteq L_{CLR(1)}$

For all of these parsing algorithms, the fact that the algorithm cannot produce a conflict-free parsing table for a particular grammar means that that grammar cannot be parsed with that algorithm. The word "accept" is quite confusing here: an algorithm produces a parser from a grammar (or fails to do so); the parser then accepts those sentences which are in the grammar's language. If an algorithm produces a parser for a grammar, then that parser will be 100% precise: it will accept all sentences in that grammar's language and reject all other sentences.

Furthermore, all these LR parsers have linear time and space complexity (in the size of the sentence to be recognised), and all of them reject invalid inputs at the earliest possible point, which is as soon as the prefix of the input cannot be the prefix of any sentence in the language. It is true that some of the parsers may perform extra reduce actions before reporting failure, but that is not considered in the definition of a grammar's "power".