0
$\begingroup$

From what I have learned the number of reducing moves in the parsers are generally in the order

LR(0)>= SLR(1) >= LALR(1).

But I am unable to understand where should I place CLR(1) in this category?

Is it CLR(1)>=LR(0)>= SLR(1) >= LALR(1) ?

$\endgroup$
0
$\begingroup$

The number of reductions in a parse is strictly dependent on the grammar, since every production must be reduced exactly once.

Consequently, all LR parsing algorithms which can parse a given grammar will do so with the same number of reduction steps (and the same number of shift steps).

The only moment in the parse where an extra reduction might possibly occur is just before an error action, for a sentence which cannot be parsed by the grammar. The sequence of reduction/shift steps is still the same for all parsing algorithms; the only difference is where the error is noted.

This will be affected not only by the choice of parsing algorithm but also by the particular parse table compression algorithm used, since table compression generally involves replacing some error actions with the state default action in order to reduce table size. (Since the sentence is not recognised by the grammart, the parser will not be able to shift the lookahead token. So replacing an error action with a default reduction action must still produce an error before the lookahead token is shifted.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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