ToolSphere
Back to all articles
student

Yacc Precedence and Associativity Explained

2026-11-039 min read

Try it: free LR Parser (LR(0), SLR, LALR, CLR)

Build LR parsing tables and trace shifts and reductions

Open →

A precedence declaration tells an LR parser how to choose between a shift and a reduction for selected conflicts. It does not add a new grammar production or make an ambiguous grammar mathematically unambiguous. The LR parser supports yacc-style declarations and records the reason for each resolved cell. All states, actions and traces below are generated by its libraries.

The example grammar is deliberately ambiguous:

E -> E + E | E * E | E ^ E | id

We build an SLR table before applying declarations. The raw table contains 9 shift/reduce conflict cells. Each expression rule can be complete while an operator lookahead is also eligible to shift. The question is whether to finish the expression already on the stack or extend it through that incoming operator.

Declare increasing precedence levels

Use the following declarations, listed from lowest precedence to highest:

%left +
%left *
%right ^

Addition groups left at the lowest level. Multiplication also groups left at a higher level. Power has the highest level and groups right. The order of declaration lines creates levels; the order in which alternatives happen to appear in the grammar is not a substitute for these declarations.

For the rules in this example, a reduction gets the precedence of its rule's operator. The parser compares that rule precedence with the lookahead operator's precedence. Higher lookahead precedence selects shift. Higher rule precedence selects reduce. At equal precedence, left selects reduce, right selects shift and nonassoc creates an error action.

These principles match the GNU Bison explanation of precedence resolution. Bison has additional features such as explicit rule-precedence overrides. The teaching tool here supports the documented declaration panel; it is not a full Bison grammar-file compiler.

Read every conflict decision

The generated production numbering is:

Rule Production
0 E' → E
1 E → E + E
2 E → E * E
3 E → E ^ E
4 E → id

An action s followed by a number shifts to that state. An action r followed by a number reduces by the numbered production above. State numbering is specific to this generated automaton, so compare item contents or rules before comparing numbers from a different construction order.

All original conflict cells are resolved as follows:

State / lookahead Original actions Kept action Generated reason
6 / + s3 / r1 r1 + and + have equal precedence and are %left: reduce, so they group to the left.
6 / * s4 / r1 s4 * has higher precedence than + in E → E + E: shift.
6 / ^ s5 / r1 s5 ^ has higher precedence than + in E → E + E: shift.
7 / + s3 / r2 r2 E → E * E takes the precedence of *, which is higher than +: reduce.
7 / * s4 / r2 r2 * and * have equal precedence and are %left: reduce, so they group to the left.
7 / ^ s5 / r2 s5 ^ has higher precedence than * in E → E * E: shift.
8 / + s3 / r3 r3 E → E ^ E takes the precedence of ^, which is higher than +: reduce.
8 / * s4 / r3 r3 E → E ^ E takes the precedence of ^, which is higher than *: reduce.
8 / ^ s5 / r3 s5 ^ and ^ have equal precedence and are %right: shift, so they group to the right.

After resolution the table has 0 remaining conflicts. In the addition-complete state, an incoming multiplication shifts because multiplication has the higher level. In the multiplication-complete state, an incoming addition reduces the completed multiplication. The power-versus-power decision shifts on equal precedence because its declaration is right-associative.

Follow actual reductions for three expressions

An accepted result alone does not establish the intended associativity, since several parse policies may accept the same token string. The reduction order shows which expression is completed first. The following complete traces use the resolved table and start from its initial state.

id + id * id

Stack before action Remaining input Action
0 id + id * id end Shift id, go to state 2
0 id 2 + id * id end Reduce by E → id (r4)
0 E 1 + id * id end Shift +, go to state 3
0 E 1 + 3 id * id end Shift id, go to state 2
0 E 1 + 3 id 2 * id end Reduce by E → id (r4)
0 E 1 + 3 E 6 * id end Shift *, go to state 4
0 E 1 + 3 E 6 * 4 id end Shift id, go to state 2
0 E 1 + 3 E 6 * 4 id 2 end Reduce by E → id (r4)
0 E 1 + 3 E 6 * 4 E 7 end Reduce by E → E * E (r2)
0 E 1 + 3 E 6 end Reduce by E → E + E (r1)
0 E 1 end Accept

Generated verdict: accepted.

id + id + id

Stack before action Remaining input Action
0 id + id + id end Shift id, go to state 2
0 id 2 + id + id end Reduce by E → id (r4)
0 E 1 + id + id end Shift +, go to state 3
0 E 1 + 3 id + id end Shift id, go to state 2
0 E 1 + 3 id 2 + id end Reduce by E → id (r4)
0 E 1 + 3 E 6 + id end Reduce by E → E + E (r1)
0 E 1 + id end Shift +, go to state 3
0 E 1 + 3 id end Shift id, go to state 2
0 E 1 + 3 id 2 end Reduce by E → id (r4)
0 E 1 + 3 E 6 end Reduce by E → E + E (r1)
0 E 1 end Accept

Generated verdict: accepted.

id ^ id ^ id

Stack before action Remaining input Action
0 id ^ id ^ id end Shift id, go to state 2
0 id 2 ^ id ^ id end Reduce by E → id (r4)
0 E 1 ^ id ^ id end Shift ^, go to state 5
0 E 1 ^ 5 id ^ id end Shift id, go to state 2
0 E 1 ^ 5 id 2 ^ id end Reduce by E → id (r4)
0 E 1 ^ 5 E 8 ^ id end Shift ^, go to state 5
0 E 1 ^ 5 E 8 ^ 5 id end Shift id, go to state 2
0 E 1 ^ 5 E 8 ^ 5 id 2 end Reduce by E → id (r4)
0 E 1 ^ 5 E 8 ^ 5 E 8 end Reduce by E → E ^ E (r3)
0 E 1 ^ 5 E 8 end Reduce by E → E ^ E (r3)
0 E 1 end Accept

Generated verdict: accepted.

For the mixed addition/multiplication input, the multiplication reduction occurs before the outer addition reduction. For repeated addition, a completed left expression reduces before the next addition extends it. For repeated power, shifting delays the earlier power reduction so the right subexpression completes first. The traces demonstrate the grouping policy without claiming to evaluate an arithmetic result.

Use nonassoc to reject an equal-precedence chain

Now replace the power declaration with %nonassoc ^ while retaining the other levels. The same generated automaton and raw table are used, but the equal-precedence power conflict is changed into an error cell. Parsing id ^ id ^ id then gives:

Stack before action Remaining input Action
0 id ^ id ^ id end Shift id, go to state 2
0 id 2 ^ id ^ id end Reduce by E → id (r4)
0 E 1 ^ id ^ id end Shift ^, go to state 5
0 E 1 ^ 5 id ^ id end Shift id, go to state 2
0 E 1 ^ 5 id 2 ^ id end Reduce by E → id (r4)
0 E 1 ^ 5 E 8 ^ id end Error: no action in state 8 for "^"

The verdict is rejected. Nonassoc does not mean “choose whichever grouping is convenient,” nor does it mean that every appearance of the operator is forbidden. It rejects the conflicting unparenthesized chain under the chosen policy. A real language might use this for comparisons, where repeated operators should require explicit structure.

Separate tool limits from yacc defaults

The teaching resolver settles a shift/reduce cell only when it has the required declared precedence information. It leaves undeclared cases and reduce/reduce conflicts visible rather than pretending they were settled by the declarations. Inspect the remaining-conflict count after changing the panel.

Full yacc/Bison behavior includes defaults and more syntax than this tool implements. Do not infer a production compiler's complete policy from an undeclared conflict left unresolved in the visualizer. In particular, the example above avoids rule-precedence overrides and more complex right sides, so the displayed operator comparison is direct and inspectable.

Precedence is also different from the operator-precedence relation-table parsing method. That method uses LEADING/TRAILING sets and terminal-to-terminal relations; yacc-style conflict resolution works on LR actions. The operator-precedence guide explains the former construction.

Verify a changed declaration

Change one level or associativity declaration in the interactive LR parser, then inspect both the decision explanations and a repeated-operator trace. Check mixed operators to verify relative priority, repeated operators to verify association, and malformed input to verify rejection. Do not use only accepted words as your test suite.

The parse tree generator can demonstrate the grammar's multiple structures before a policy selects one. The SLR worked example explains how the raw actions arise, and the compiler lab links the surrounding stages.

Looking for other tools?

Explore ToolSphere Homepage →