Grammars, Precedence, and Associativity

Three concepts here: the grammar as a specification, ambiguity and how precedence resolves it, and associativity. Each in the nine-part treatment.

This is the chapter where a language stops being a pile of features and becomes a thing with a definition you can hand to someone else.

Concept 1: The Grammar

1. Concept

A grammar is a finite set of rules that generates exactly the set of valid programs. Each rule says: this nonterminal can be replaced by this sequence of terminals and nonterminals.

exp  ::=  exp '+' exp  |  exp '*' exp  |  Numeral  |  '(' exp ')'

Terminals are tokens. Nonterminals are the named shapes. A program is valid if and only if you can derive it from the start symbol.

2. Problem

Without a written grammar you have a parser, and the parser is the specification — which means nobody can implement your language, review your parser, or tell whether a bug is a bug. Every language that lasted has a grammar in its reference manual, and the ones that did not (early PHP, early JavaScript) paid for it for a decade.

For you, personally, the practical problem is smaller and more immediate: without a grammar you will write a parser whose precedence is wrong and not know it.

3. Mental model

A grammar is a shape specification, and parsing is shape recognition. The output of parsing is not "valid / invalid" — it is the tree that shows how the input was derived. That tree is the only thing the rest of the compiler cares about.

4. Implementation — Ember's grammar

This is the whole language. Parts are marked with the lab that implements them, so you can see the target from here.

chunk       ::= block                                                       (* Lab 3  *)
block       ::= {stat} [retstat]                                            (* Lab 5  *)

stat        ::= ';'
              | varlist '=' explist                                         (* Lab 5  *)
              | functioncall                                                (* Lab 7  *)
              | 'do' block 'end'                                            (* Lab 5  *)
              | 'while' exp 'do' block 'end'                                (* Lab 6  *)
              | 'if' exp 'then' block {'elseif' exp 'then' block}
                                       ['else' block] 'end'                 (* Lab 6  *)
              | 'for' Name '=' exp ',' exp [',' exp] 'do' block 'end'       (* Lab 6  *)
              | 'for' namelist 'in' explist 'do' block 'end'                (* Lab 13 *)
              | 'function' funcname funcbody                                (* Lab 7  *)
              | 'local' 'function' Name funcbody                            (* Lab 7  *)
              | 'local' namelist ['=' explist]                              (* Lab 5  *)
              | 'break'                                                     (* Lab 6  *)

retstat     ::= 'return' [explist] [';']                                    (* Lab 7  *)

exp         ::= 'nil' | 'false' | 'true' | Numeral | LiteralString | '...'
              | functiondef | prefixexp | tableconstructor
              | exp binop exp | unop exp
prefixexp   ::= var | functioncall | '(' exp ')'
var         ::= Name | prefixexp '[' exp ']' | prefixexp '.' Name           (* Lab 13 *)
functioncall::= prefixexp args | prefixexp ':' Name args                    (* Lab 7  *)
args        ::= '(' [explist] ')' | tableconstructor | LiteralString
functiondef ::= 'function' funcbody
funcbody    ::= '(' [parlist] ')' block 'end'
tableconstructor ::= '{' [fieldlist] '}'                                    (* Lab 13 *)
field       ::= '[' exp ']' '=' exp | Name '=' exp | exp

binop       ::= '+' | '-' | '*' | '/' | '//' | '%' | '^' | '..'
              | '<' | '<=' | '>' | '>=' | '==' | '~=' | 'and' | 'or'
unop        ::= '-' | 'not' | '#'

If that looks like Lua's grammar, it is — deliberately, minus the bitwise operators, goto, and repeat. Copying a proven grammar is not laziness; it means every Lua program in your test corpus is a valid Ember program, which is worth a great deal in Section 6.

Note: Notice exp ::= exp binop exp. That production is ambiguous — it does not say how 1 + 2 * 3 groups. Lua's manual does the same thing and then resolves it with a separate precedence table, which is exactly the design this chapter is about.

5. Alternatives

6. Decision

We specify with option A and parse with a Pratt parser, which is option A executed directly.

The stratified grammar (B) is what most textbooks teach and it is genuinely clearer for a three-level expression language. At Lua's ten levels it produces ten nearly identical functions, and adding an operator means editing two of them plus writing a new one. The precedence table is one line per operator.

7. Tradeoffs

8. Production concerns

• A grammar that is not in the docs will drift from the parser. Ember's grammar lives in docs/architecture.md and Lab 26 adds a test that parses every production's example.

• Ambiguity in general context-free grammars is undecidable. You cannot write a tool that proves your grammar unambiguous. What you can do is generate programs from the grammar and check the parser round-trips them — which is exactly what the proptest generator in Lab 26 does.

• The one real ambiguity Lua has, and Ember inherits, is worth knowing:

  a = f
  (g).x = 1
  

  Is that one statement (a = f(g).x = 1, which is nonsense) or two? Lua's parser always reads the open parenthesis as the start of a call's arguments, so it sees one statement and errors. The manual's advice is to precede a statement that starts with ( with a semicolon. Ember copies the behavior and the advice. A language without statement terminators buys convenience with exactly this kind of edge, and knowing that is worth more than the edge itself.

9. References

• The Lua 5.4 Reference Manual, §9 ("The Complete Syntax of Lua") — two pages, and the direct ancestor of the grammar above.
• The Rust Reference's grammar chapters, for a modern EBNF that is honest about where it is informal.
• Aho, Lam, Sethi & Ullman, Compilers: Principles, Techniques, and Tools ("the dragon book"), chapter 4 — the canonical treatment. You do not need to read it; you should know what is in it.

Concept 2: Precedence

1. Concept

Precedence decides which operator grabs an operand when two compete for it. In 1 + 2 * 3, the 2 is wanted by both + and *. Precedence says * wins.

2. Problem

exp ::= exp binop exp permits both derivations. Two parse trees, two different answers:

      1 + 2 * 3

  CORRECT (* binds tighter)      WRONG
        Add                        Mul
       /   \                      /   \
      1    Mul                  Add    3
          /   \                /   \
         2     3              1     2

      = 1 + 6 = 7             = 3 * 3 = 9

3. Mental model

Give every operator a binding power: a number saying how hard it pulls on its operands. When two operators compete for the operand between them, the stronger pull wins. * at 10 beats + at 8, so 2 goes to *.

That is the whole idea, and it is why "precedence climbing" and "Pratt parsing" are the same technique under two names.

4. Implementation

Ember's table. It is Lua's, minus the bitwise rows, and the numbers are ours — only the order matters, so leave gaps to make future insertions painless.

#![allow(unused)]
fn main() {
/// (left binding power, right binding power) for infix operators.
/// left < right  → LEFT-associative      left > right → RIGHT-associative
fn infix_bp(kind: &TokenKind) -> Option<(u8, u8)> {
    use TokenKind::*;
    Some(match kind {
        Or                                        => (1, 2),
        And                                       => (3, 4),
        Less | Greater | LessEq | GreaterEq
             | NotEq | Eq                         => (5, 6),
        DotDot                                    => (9, 8),   // right-assoc
        Plus | Minus                              => (10, 11),
        Star | Slash | DoubleSlash | Percent      => (12, 13),
        Caret                                     => (17, 16), // right-assoc
        _ => return None,
    })
}

/// Prefix operators bind their single operand with this power.
fn prefix_bp(kind: &TokenKind) -> Option<u8> {
    use TokenKind::*;
    match kind { Minus | Not | Hash => Some(14), _ => None }
}
}

5. Alternatives

Option D is worth a moment. Smalltalk's 2 + 3 * 4 is 20, and Smalltalk programmers consider this a feature: one fewer table to memorize. APL evaluates strictly right to left. Precedence is a convention, not a law of arithmetic, and remembering that makes the design space visible.

6. Decision

We use a binding-power table (option A).

It is one row per operator, it is the same mechanism that handles associativity, and it makes the parser's precedence behavior something you can read as data rather than infer from control flow.

7. Tradeoffs

8. Production concerns

• Gaps in the numbering. If + is 10 and * is 11, inserting an operator between them means renumbering. Leave gaps. This is the kind of thing that costs five minutes now and an hour later.
• Precedence disagreements are silent. A wrong binding power produces a program that runs and computes the wrong thing. There is no error to catch it. The only defense is a differential test against a reference — which is why the verification step in the section index compares against lua for a list of expressions, and why that list should grow every time you add an operator.
• ^ and unary minus is where every implementation slips. -2 ^ 2 must be -4. See Concept 3.

9. References

• The Lua 5.4 Reference Manual §3.4.8 — the precedence table Ember's is derived from.
• The C operator precedence table, for a cautionary example: 15 levels, several of which (& vs ==) are widely agreed to be historical mistakes that cannot now be fixed.
• Python's operator precedence documentation, and PEP 465's discussion of where to put @ — a real, recent, well-argued precedence decision you can read the reasoning for.

Concept 3: Associativity

1. Concept

Associativity decides the grouping when two operators of equal precedence compete. 1 - 2 - 3 can be (1 - 2) - 3 = -4 or 1 - (2 - 3) = 2. Subtraction is left-associative, so it is -4.

2. Problem

Precedence alone does not disambiguate a op b op c when both ops are the same operator. You need a second rule, and for some operators the answer is not the common one:

1 - 2 - 3     left    (1 - 2) - 3 = -4
2 ^ 3 ^ 2     RIGHT   2 ^ (3 ^ 2) = 512      -- exponentiation
"a".."b".."c" RIGHT   "a"..("b".."c")        -- concatenation
x = y = z     RIGHT   in languages where assignment is an expression (not Ember)

3. Mental model

Give each operator two binding powers — one facing left, one facing right — and make them differ by one. If the right power is higher, the operator on the right wins the middle operand, and you get left-associativity. If the right power is lower, the operator on the left lets go, and you get right-associativity.

   1  -  2  -  3                 2  ^  3  ^  2
      ↑10 11↑                       ↑17 16↑
      (10,11): the SECOND '-'       (17,16): the SECOND '^' has left-bp 17,
      has left-bp 10, which is       which is > the first's right-bp 16,
      < the first's right-bp 11,     so the second '^' takes the 3.
      so the first '-' keeps the 2.  → 2 ^ (3 ^ 2)
      → (1 - 2) - 3

Read that twice. It is the entire mechanism, it is one comparison in the parser loop, and once it clicks you will never write an associativity bug again.

4. Implementation

The comparison lives in exactly one place, the Pratt loop (next chapter):

#![allow(unused)]
fn main() {
loop {
    let Some((l_bp, r_bp)) = infix_bp(&self.peek().kind) else { break };
    if l_bp < min_bp { break; }              // ← the operator to our left wins
    let op = self.advance();
    let rhs = self.expr_bp(r_bp)?;           // ← r_bp decides associativity
    lhs = Expr::Binary { op, lhs: Box::new(lhs), rhs: Box::new(rhs), span };
}
}

(10, 11) for - and (17, 16) for ^. One character of difference in the table; no if in the parser. That is the payoff for encoding associativity as a number rather than a flag.

5–7. Alternatives, decision, tradeoffs

Decision: option A. B is arguably more readable and produces identical behavior; if you prefer it, take it — but write the ADR, because "we chose the less clever encoding deliberately" is a legitimate and underused decision. Option C is how a stratified grammar does it, and noticing that left recursion means left associativity is the insight that connects the two worlds.

8. Production concerns

Unary operators and ^ are where implementations get it wrong. Lua's rule:

-2 ^ 2      -- -(2^2) = -4     : ^ binds TIGHTER than unary minus on the LEFT
2 ^ -3      -- 2^(-3) = 0.125  : unary minus is allowed as ^'s RIGHT operand
-2 ^ -3     -- -(2^(-3))
#t ^ 2      -- (#t)^2? or #(t^2)? -- check it. Predict first.

Both behaviors fall out of the table with no special case: unary's binding power (14) is less than ^'s left power (17), so when the parser has parsed - and is collecting its operand with expr_bp(14), it sees ^ with left-bp 17 ≥ 14 and lets ^ take the 2. And when ^ collects its right operand with expr_bp(16), the operand parser handles a prefix - before any binding-power comparison happens at all.

If your numbers are right, you get this for free. If they are wrong, you get a silently wrong answer. Test it against lua on day one:

for e in '-2 ^ 2' '2 ^ -3' '-2 ^ -3' '2 ^ 3 ^ 2' '1 - 2 - 3' '"a".."b".."c"'; do
  printf '%-16s ember=%-10s lua=%s\n' "$e" "$(ember run -e "return $e")" "$(lua -e "print($e)")"
done

9. References

• Lua 5.4 Reference Manual §3.4.8: "The exponentiation and concatenation operators are right associative. All other binary operators are left associative."
• Vaughan Pratt, Top Down Operator Precedence (POPL 1973) — the original, and short. The left/right binding power idea is in there.
• Aleksey Kladov ("matklad"), Simple but Powerful Pratt Parsing — the modern explanation that made the (l_bp, r_bp) encoding widely known in the Rust community. Read it alongside the next chapter.

Things to Notice

• Precedence stops existing after parsing. The evaluator, the compiler, and the VM never think about it. A tree has no precedence — it has shape. This is why getting it wrong is so dangerous: the information is destroyed at the boundary, so nothing downstream can detect the error.
• An ambiguous grammar plus a precedence table is not a worse specification than an unambiguous grammar — it is a factored one. Lua, C, Python, and Rust all do it this way in their manuals.
• Associativity is asymmetry. Any mechanism that can express "these two competing operators are not equal" can express associativity. Two numbers, a flag, or the side you recurse on.
• The dangling-else problem does not exist in Ember, because if ... then ... end is explicitly terminated. C's if (a) if (b) x(); else y(); ambiguity is a consequence of optional braces, and Lua's designers chose end in 1993 partly to avoid it. Terminators cost keystrokes and buy unambiguity; that is a real tradeoff and Lua picked a side.

Validation / Self-check

1. Write the two possible parse trees for 1 + 2 * 3 and say which the precedence table selects.
2. What does it mean for a grammar to be ambiguous, and why can no tool prove yours is not?
3. Give Ember's binding powers for +, ^, .., and unary -, and explain how each pair encodes its associativity.
4. Why is -2 ^ 2 equal to -4, in terms of binding-power comparisons — not "because Lua says so"?
5. Give three ways to express associativity and name a system that uses each.
6. Why is a precedence bug more dangerous than a syntax bug?
7. What is the one genuine ambiguity in Lua's statement grammar, how does the parser resolve it, and what is the recommended workaround?
8. Why does Ember copy Lua's grammar rather than inventing one? Name a concrete benefit that arrives in Section 6.

Next: Recursive Descent and Pratt Parsing.