skip to content

When a parser generator reports a shift-reduce conflict in one state of a grammar, what has it found and how does it resolve it?

level: seniorimportance: must knowfreq 56%

answer

  1. one cell, two legal actions
  2. the report names a state and a token
  3. one item complete, one item not
  4. the default breaks the tie, conventionally shift
  5. shifting keeps the token in the innermost construct

basics

~20 s

A shift-reduce conflict means one state can both shift the next token and reduce a completed rule on that same token, so the table is not deterministic. Generators conventionally prefer shift, silently binding the construct to the innermost open one.

solid answer

~50 s

The report names a **state** and a **token**. In that state the item set contains a rule whose dot sits just before that token (so shifting is legal) and another rule that is already complete with that token in its lookahead set (so reducing is legal too). The grammar is therefore not LR for the lookahead the construction uses. Because a table cell holds one action, the generator applies a default — conventionally **shift** — and emits a working parser anyway. That default is a decision about what the language *means*: in the usual trailing-clause shape, shifting attaches the pending element to the construct currently being built, the innermost one, and no reading of the source file says so. An unread conflict is not a harmless warning; it is a language rule nobody wrote down.

code

pseudocode · 11 lines
pseudocode
-- generated report for one state
state 12:
    section -> header body .          reduce on { footer, end_of_input }
    section -> header body . footer   shift on footer

conflict: ACTION[12, footer] has two candidate entries
default applied: shift

-- consequence on the input:  header header body footer
--   shift  -> the footer closes the INNER section
--   reduce -> the footer would have closed the outer one

go deeper

for a junior

Know that the message means the generator found two possible actions for the same token and picked one for you, and that this is worth asking about rather than scrolling past.

for a middle

Explain the state's two items, why both are legal, and what the conventional shift default does to the shape of the tree for the construct involved.

for a senior

Demonstrate the workflow: reach the state with a real input, inspect the tree the shipped parser builds, decide whether that is the intended language, and make the choice explicit with a test.

for a principal

Set the policy: which conflicts a build may carry, how they are recorded as language decisions, and who signs off when a tie-break changes what existing files mean.

## What the report is actually saying A generated parser is a table: for every state and every lookahead token there is at most one action. A shift-reduce conflict is the generator telling you that for one cell it computed **two** legal actions: - an item of the form `A -> alpha . t beta`, so the token `t` can be shifted; and - an item of the form `B -> gamma .`, complete, with `t` in the lookahead set that permits reducing it. Both are consistent with everything read so far. The grammar is not LR for the lookahead the construction uses, and the usual underlying cause is that the rule set admits two readings of the same text — a property of the rule set itself, owned by the grammar-ambiguity material rather than by the table. ## A concrete state A data-definition language with nestable sections and an optional closing marker: - `section -> header body` - `section -> header body footer` - `body -> section_list` After `header body` is on the stack and the lookahead is `footer`, the state holds both `section -> header body .` (reduce, because a footer may legally follow an enclosing section) and `section -> header body . footer` (shift). Two readings of `header header body footer`: 1. The footer closes the **inner** section, and the outer section ends without one. 2. The inner section ends without a footer, and the footer closes the **outer** one. ## The default and what it decides | | Action taken | Effect on the input above | Visible where? | |---|---|---|---| | Conventional default | shift | footer closes the inner section | only in the build log | | The other choice | reduce | footer closes the outer section | not taken | | Doing nothing | — | the conflict stands | in every future log line | The parser that ships is perfectly deterministic and perfectly fast. It simply implements reading 1, forever, and the specification of the language says nothing about it. That is the risk: not a crash, but **a semantic decision made by a tie-break rule**. ## How to read the report in practice 1. **Find the token.** The conflict is always on one specific lookahead; that token is the clue to which construct is involved. 2. **Read the two items.** One is complete, one is not. The complete one tells you what the parser would close; the other tells you what it would extend. 3. **Write the input that reaches the state.** A conflict you cannot reach with a real file may still matter later, but the reachable one tells you what changed for users. 4. **Run that input through the shipped parser** and inspect the tree. Now you know what the default already decided. 5. **Decide whether that is the language you want**, then make it explicit rather than leaving it implicit. ## Making it explicit - **Reshape the rules** so only one action is legal in that state — usually by introducing a token or a nonterminal that distinguishes the two readings. - **Declare the choice** where the generator supports precedence or associativity declarations. The behaviour is identical to the default; the difference is that the decision is now in the grammar file and reviewable. - **Accept it deliberately** and record it, along with a test that pins the tree. A known conflict with a test is a documented rule; an unknown one is a trap. - **Do not** reach first for a larger table construction. A conflict caused by the rule set meaning two things survives every construction; only conflicts that are artefacts of state merging disappear that way. ## Misreadings to avoid - A conflict is not a runtime error. Nothing fails at parse time; a reading is simply chosen. - A conflict is not nondeterminism. The emitted parser is deterministic — it was determinised by the default. - "It builds, so it is fine" hides the exact class of bug that surfaces years later as "this file used to mean something else".

  • How do you tell a conflict that encodes the language you want from one hiding a bug?
    Construct the smallest input that reaches the state, parse it, and look at the tree. If the shape matches the documented intent, pin it with a test and record the decision; if it does not, the default chose the wrong reading and the rules must change.
  • Why does the report name a state number rather than a line in the grammar file?
    Because the conflict is a property of a position in the recognizer, not of one rule: the state is a set of items drawn from several rules, reachable by many inputs. The items listed in the report are the bridge back to the rules involved.
  • Is a shift-reduce conflict ever safe to leave in place permanently?
    Yes, when the default's reading is the intended one and the team knows it. The trailing-clause shape is the classic case. What makes it safe is not the conflict's kind but that the choice is written down and covered by a test that would fail if the table changed.

saying these in an interview costs you the question

  • Says the conflict makes the generated parser nondeterministic
  • Treats it as harmless because the build still produces a parser
  • Expects a runtime crash when the conflicted state is reached
  • Thinks a bigger table construction removes every conflict
  • Cannot name which action the conventional default prefers
  • Believes the conflict is reported against a single grammar rule