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) ?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The number of reductions in a successful 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 parse all sentences accepted by the grammar using 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 up to and including the last shift; the only possible difference is some algorithms can perform more reductions before 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.)