Grammar & Rules
Grammar Basics
Formal grammars describe strings of tokens the same way recipes describe meals: ingredients on the left, process on the right.
Productions and Symbols
A production rewrites one nonterminal into a sequence of terminals (tokens) and other nonterminals. The root rule (usually called program or start) anchors everything. Example: request = "room", name; says a request can be the keyword room followed by a name.
EBNF Notation
Extended BNF adds three conveniences: alternation | (choose one), repetition { ... } (zero or more), and optionality [ ... ]. EBNF is itself a DSL for languages — the meta-DSL this chapter teaches.
(* the whole notation in seven lines *)
request = "room", name, [ "time-until", time ] ;
name = ? letters, digits or dashes ? ;
time = number, ":", number ;
number = digit, { digit } ;
digit = "0" | "1" | ... | "9" ;Ambiguity, Precedence & Associativity
If a sentence has two possible trees, the language is ambiguous and users will disagree about meaning. The grammar must pick one reading.
Figure 2 — Associativity changes the result; a grammar without a rule permits both.
Fixing with Levels
The standard cure is precedence levels: one nonterminal per binding strength. Multiplication gets its own level below addition, and each level’s rule fixes associativity explicitly:
(* resolved: lower level, tighter binding *)
expr = term, { ( "+" | "-" ), term } ; (* left-associative by iteration *)
term = factor, { ( "*" | "/" ), factor } ;
factor = number | "(", expr, ")" ;Classic Ambiguities
The dangling else (which if owns the trailing else?), optional separators, and empty rules are the usual culprits. Each must be resolved in the grammar, never in the parser by convenience.
Grammar Classes
Not every grammar parses equally easily; two families dominate practice.
LL (top-down)
Left-to-right scan, leftmost derivation, one token of lookahead: the rule decides by the next token. Elegant to write by hand (recursive descent works on LL grammars) but left recursion must be avoided.
LR (bottom-up)
Trees are built from the leaves up; LR parsers (including LALR, as in yacc) accept a much larger language family and handle left recursion naturally — at the cost of tables and tooling instead of readable functions.
Choice of Weapon
Hand-written recursive descent is the best default for small DSLs; ANTLR, PLY/lark, or Menhir are the choice when the grammar grows or must stay provably unambiguous. Each is covered later in the DSL Implementation Languages phase: ANTLR generates recognizers from a grammar, OCaml hosts Menhir’s LR(1) parser generator inside a type-safe compiler, and Racket lets you define the language itself.
Validating the Grammar
An Example Suite
Keep a corpus of must-parse examples (the vocabulary in action) and must-reject examples. If the grammar cannot explain one of its own examples, the grammar is wrong, not the example.
Tooling Checks
EBNF checkers and parser generators will report ambiguity, useless rules (nonterminals never used), and unreachable rules. Treat each report as a design finding, because every one of them is a corner a user will find.
Example: Resolving the Grammar
Start ambiguous, end resolved. The two grammars below describe the same arithmetic — only the second one is a specification.
Ambiguous (do not ship)
(* expr = expr, "+", expr | number — two trees for 1+2+3 *)
expr = expr, ( "+" | "-" ), expr | number ;Resolved (ship this)
(* one level per precedence; iteration makes it left-associative *)
expr = term, { ( "+" | "-" ), term } ;
term = factor, { ( "*" | "/" ), factor } ;
factor = number | "(", expr, ")" ;The Check
Hand-parse two examples against both: 1 + 2 + 3 and 2 * 3 + 4. The first grammar offers two trees for the former; the second offers exactly one for both — that is the whole job of this chapter in miniature.
Next Steps
Continue Phase 1
Rules produce the tree; Parsing & Trees shows how the machine builds it, and Semantics & Scoping explains what it means.