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$

1 Answer 1

1
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ Canonical/full LR(1) with no table compression gives the least number of reductions (detects errors as early as possible). $\endgroup$
    – vonbrand
    Feb 25, 2020 at 16:23
  • 1
    $\begingroup$ @vonbrand: The point I was trying to make is that there is only a difference in the number of reductions if the parse fails, which presumably is not the primary use case for the parse. Successful parses always have the same number of reductions. I'll try to edit this answer to make this point even clearer. $\endgroup$
    – rici
    Feb 25, 2020 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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