Analysis of a LALR shift-reduce conflict

Question

I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example):

%token NEWLINE SPECIFIER
%token EQUALS STRING VAR

%start st

%%

st: toplevel;

toplevel:
| toplevel VAR EQUALS STRING NEWLINE
| toplevel list NEWLINE
;

list:
  maybe_specifier VAR
| list maybe_specifier VAR
;

maybe_specifier:
| SPECIFIER
;

However, it is warning about a shift-reduce conflict. If I remove maybe_specifier from the grammar entirely (so that variables cannot be prefixed by a specifier in a list), the conflict disappears. Similarly, if I remove the variable assignment from the grammar entirely, the conflict disappears too.

My questions are:

• Where does this shift-reduce conflict come from? Is it an artifact of LALR? Or would it be there even with an LR(1) parser generator?
• Does this shift-reduce conflict matter? Or is it always doing the right thing anyway by using shift instead of reduce?
• Is there any way to modify the grammar to accept the same language without having the shift-reduce conflict, other than by prefixing VAR in assignment line by maybe_specifier and then checking whether the SPECIFIER was there in a semantic action, and failing if the SPECIFIER was present?

My current approach is to modify the assignment rule to initially accept a SPECIFIER in the form of maybe_specifier but then terminate with a parse error if the SPECIFIER was there. I'm wondering if there's a cleaner approach that would allow me to do the same without adding a semantic action.

Answer 1

This conflict arises because when the parser is at the beginning of a line and the lookahead is VAR, it can't tell whether or not to reduce an empty maybe_specifier. In this simple grammar, that decision could be resolved with one more lookahead token, making the grammar LR(2), but that might not be true in the original unsimplified version.

So the conflict is not an artefact of the LALR algorithm, and it is important to fix. (The yacc default resolution "choise shift over reduce" will make it impossible to parse lists which don't start with a SPECIFIER.)

A simple fix is to defer the parsing decision for the first entry in a list:

list:
  VAR
| SPECIFIER VAR
| list maybe_specifier VAR
;

Again, that might or might not be useful in the context of your full grammar.