Conflict resolution in LALR(1) parser

Question

Some questions about conflicts in LALR(1) parsers, mainly related to the details of parsing:

1. According to the different LALR(1) parsers described in the textbooks if one encounters a shift/reduce conflict then it is a sign the grammar is not LALR(1) to begin with, right?

2. Reduce/Reduce conflicts may appear in valid LALR(1) grammars, because of the state merging done from LR(1) to LALR(1), right?

3. Precedence and associativity, as used in YACC and GNU Bison, are tools introduced to help resolve shift/reduce conflicts, right?

4. Moreover, associativity should only be checked by the parser iff the conflicting shift/reduce rules precedence is equal to the lookahead symbol precedence, in any other case associativity is irrelevant, right?

I am asking because I am not 100% sure, and the books do not provide much detail about conflict resolution, the only few lines I found on the subject are in the GNU Bison Manual

A question related to the Bison manual link above:

• Why do they claim that absent precedence in the conflict rules or the lookahead token, the choice is SHIFT? I would think that if the reduction rule has any precedence it beats the lookahead with no precedence at all.

Answer 1

1. If any conflict (either shift/reduce or reduce/reduce) is found during LALR(k) construction, then the grammar is not LALR(k).

2. State merging from LR(1) to LALR(1) cannot produce a shift/reduce conflict, so if there is one, the grammar isn't LR(1) either. But it can produce a reduce/reduce conflict. If it does, the grammar is not LALR(1), even though it is LR(1). (It's not really a question of "validity"; it's a question of parsability by a particular algorithm.)

3. Yes, precedence (and associativity, which is just a subcase of precedence) allow resolution of shift/reduce conflicts.

4. Precedence is a comparison between a production (on the left) and a lookahead token (on the right). Associativity affects the comparison operator which is used: either ≤ or < (or, in the case of %nonassoc, error-on-equal).

There is an excellent discussion of the algorithm in the Dragon book. However, it's not very complicated: if the production "wins", the parser reduces; otherwise it shifts.

Bonus question: Precedence rules are only applied if there is a precedence defined for both the production (either through %prec or, by default, the precedence of the last terminal in the production) and the lookahead token. If either of these is missing a precedence declaration, then shift wins. That might not seem logical, but it's the way it is.