2
$\begingroup$

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads:

"The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... The error will eventually be caught; in fact, it will be caught before any more input symbols are shifted."

I understand an LR(1) parsing table can be revised to an LALR(1) parsing table by combing states. However, I don't quite understand (for an LALR(1) grammar),

  • Why does the revised parser LALR(1) behave the same with the original LR(1)?
  • Why will the wrong reduce step in LALR(1) (relative to LR(1)) be caught before any more input symbols are shifted?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The explanation is given in the following paragraphs. Given a correct input, the LALR parser produces exactly the same sequence of reduce and shift actions as would an LR parser for the same grammar. On an incorrect input, the LALR parser produces the same sequence of actions up to the last shift action, although it might then do a few more reduce actions before reporting the error. So although the LALR parser has fewer states, its behaviour is identical for correct inputs, and extremely similar for incorrect inputs.

The shift error will be caught at exactly the same input point as with the LR parser because the shift actions are precisely the same between the two parsers, which is why the LALR construction cannot introduce a shift-reduce conflict which was not produced by the LR algorithm. A shift of a terminal $A$ can be done in any state whose itemset contains one or more items with the • marker just before $A$. The LR→LALR state merge only merges states with the same itemsets --that is, it merges lookaheads, not itemsets-- so the shift actions available are the same in both state machines.

This is also true of the reduce actions, available if the • is at the end of a production in the itemset. But because lookaheads are taken into account, it's possible that an itemset has more than one reduction action in the LALR state machine. The fact that the lookahead set in the LALR state machine includes tokens merged from different states does not affect the set of tokens which can eventually be shifted; it just means that the LALR state machine will not realise that the token cannot be shifted until it reaches a state in which a reduction is no longer available.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your explanation. "The fact that the lookahead set in the LALR state machine includes tokens merged from different states does not affect the set of tokens which can eventually be shifted": Why is it impossible that the wrong reduce action(s) in LALR eventually leads to a state where reduce actions are not allowed but the shift action is allowed? Do you mean that the fact "the shift actions are precisely the same between the two parsers" implies that they must perform the same sequence of shift actions on incorrect inputs? Why is that? $\endgroup$
    – hengxin
    Dec 3, 2021 at 3:17
  • $\begingroup$ @hengxin: the lookahead on a reduce action predicts what possible shift actions might follow. None of the algorithms eliminate a possible shift; imprecise algorithms SLR uses the FOLLOW set. LALR merges lookaheads between different states, which introduces entries which belong to another state and thus can't happen. So imprecise lookahead sets always err on the side of predicting a possible shift action which cannot, in fact, occur. So the parser might not know that a lookahead isn't shiftablr until it reaches a state which has no shift action for that symbol. $\endgroup$
    – rici
    Dec 3, 2021 at 5:37
  • $\begingroup$ That's not possible for an LR parser; the state construction algo for LR parsers means that the lookahead set is precise. So errors are detected immediately; the post-reduction state has the same lookahead sets as the state which did the reduction, which really is the set of symbols for which a shift action will eventually be found. $\endgroup$
    – rici
    Dec 3, 2021 at 5:41
  • $\begingroup$ If that's not clear enough, look at the LR lookahead discovery algo. And remember that LALR state merging never removes a token from the lookahead set; it can only add them. $\endgroup$
    – rici
    Dec 3, 2021 at 5:42

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.