Grammars and BNF

A context-free grammar is a 4-tuple $G = (N, \Sigma, P, S)$: a finite set of nonterminal symbols $N$ (syntactic categories like "expression" or "statement"), a finite set of terminal symbols $\Sigma$ (the actual tokens of the language, like `+`, `if`, or an identifier), a finite set of production rules $P$, and a designated start symbol $S \in N$. Each production has the form $A \to \alpha$, where $A$ is a single nonterminal and $\alpha$ is any string of terminals and nonterminals. The word "context-free" refers to this restriction: the left-hand side is always a lone nonterminal, so a rule can be applied regardless of what surrounds it — no contextual conditions are checked.

Backus-Naur Form is simply a standardized textual syntax for writing down such rules. A nonterminal is written `` (or in modern usage often just `Name`), the rule arrow is written `::=`, and alternative right-hand sides are separated by `|`. For example: ``` ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ::= | ```

EBNF (Extended BNF) adds regular-expression-style shorthand on top of plain BNF, without changing the underlying formal power: `{ X }` or `X` for zero-or-more repetitions, `X+` for one-or-more, `[ X ]` or `X?` for optional, and parentheses for grouping alternatives. EBNF is more convenient to write and read, but every EBNF grammar can be mechanically expanded into an equivalent plain BNF grammar by introducing auxiliary nonterminals for each repetition or option — so EBNF adds no generative power, only notational sugar. The language generated by a grammar, $L(G)$, is the set of all terminal strings reachable from $S$ by repeatedly applying productions — a process called <strong>derivation</strong>. Crucially, a grammar is a generative* device: it does not describe how to check a string, only how to produce one. Parsing is the inverse problem — given a string, find a derivation (if one exists) that produces it — and that inversion is what a parser algorithm computes.

Step 1 — Define the vocabulary. Decide the terminals (actual characters or tokens the lexer produces, such as `id`, `num`, `+`, `(`, `)`) and the nonterminals (syntactic categories such as `Expr`, `Term`, `Factor`).

Step 2 — Write productions for each nonterminal. Each nonterminal gets one or more alternative right-hand sides describing every shape that category can take.

Step 3 — Designate a start symbol. This is the nonterminal representing "a whole valid program" or, in a small example, "a whole valid expression".

Step 4 — Derive strings by rewriting. Starting from the start symbol, repeatedly replace one nonterminal in the current string with the right-hand side of one of its productions, until only terminals remain. This sequence of rewrites is a derivation; if at each step we always rewrite the leftmost nonterminal, it is a leftmost derivation.

Step 5 — Record structure with a parse tree. Each derivation corresponds to a tree: the root is the start symbol, and each internal node's children are the symbols on the right-hand side of the rule used to expand it. The leaves, read left to right, spell out the derived string. Here is a small, standard grammar for arithmetic expressions with `+`, ``, parentheses, and identifiers, written in BNF, designed to already encode precedence (multiplication binds tighter than addition) and left-associativity: ``` <expr> ::= <expr> "+" <term> | <term> <term> ::= <term> "" | ::= "(" ")" | "id" ``` The equivalent EBNF, using repetition instead of recursion, is more compact but describes the same language: ``` expr ::= term ( "+" term ) term ::= factor ( "" factor ) factor ::= "(" expr ")" | "id" ``` A general algorithm for producing a leftmost derivation of a target string (the essence of what a top-down parser automates) looks like this: ``` function DERIVE(grammar, target_string): frontier = [ grammar.start_symbol ] // current sentential form, as a list steps = [] while frontier contains a nonterminal: A = leftmost nonterminal in frontier choose a production A -> alpha // choice guided by lookahead at target_string replace A in frontier with the symbols of alpha steps.append(frontier.copy()) if frontier's terminal prefix does not match the corresponding prefix of target_string: backtrack: undo the last choice, try the next alternative for A if no alternatives remain: fail // string not in the language, or wrong path if frontier == target_string: return steps // a successful derivation else: return "not in L(grammar)" ``` This is a search procedure, not a magic trick: at each nonterminal there may be several productions to try, and a naive implementation may need to backtrack. Real parsers avoid this cost by restricting grammars to forms where the correct production can be chosen from a small amount of lookahead (the subject of predictive and LL/LR parsing), but the definition* of "valid string" never changes — it is always "some derivation from $S$ reaches it".

Recognition complexity. For an arbitrary context-free grammar, deciding whether a string of length $n$ belongs to $L(G)$ can be done in $O(n^3)$ time by the CYK algorithm (after converting the grammar to Chomsky Normal Form) or by the Earley parser, which is also $O(n^3)$ worst-case but $O(n^2)$ for unambiguous grammars and $O(n)$ for the deterministic, bounded-lookahead grammars (like LL(1) or LR(1)) that real compilers use. The cubic bound comes from dynamic programming over all $O(n^2)$ substrings, each combined in $O(n)$ ways at the split point. Practical language grammars are engineered to be LL(k) or LR(k) precisely so that parsing collapses to $O(n)$, avoiding the general cubic cost entirely — this is a central reason language designers write grammars in restricted, "parser-friendly" shapes rather than arbitrary CFGs.

Space. Representing the grammar itself takes space proportional to the total length of all right-hand sides — a small constant relative to program size. Parse trees take $O(n)$ space for a string of length $n$, since a context-free derivation produces a tree with $O(n)$ leaves (terminals) and at most a linear number of internal nodes for grammars without useless unit-rule chains.

Correctness — what "the grammar is correct" even means. A grammar $G$ is correct for an intended language $L$ if $L(G) = L$ exactly: every string the language designer intends to be legal has some derivation, and no illegal string has any derivation. This is proved, not asserted, typically by structural induction on derivations:

• Soundness (every derivable string is intended-legal): induct on the length of the derivation. The base case is a single production reaching only terminals; the inductive step shows that if all shorter derivations produce intended-legal substrings, substituting them via a valid production keeps the whole string intended-legal.
• Completeness (every intended-legal string is derivable): induct on the structure of the intended string (e.g., "every arithmetic expression is a sum of products, each product a sequence of atoms") and exhibit the matching production at each level.

Ambiguity is a correctness defect, not just an inconvenience. A grammar is ambiguous if some string has two distinct parse trees (equivalently, two distinct leftmost derivations). This matters because a parse tree is what downstream semantic analysis is anchored to; two different trees for `a - b - c` could mean $(a-b)-c$ or $a-(b-c)$ — different values. The grammar ``` expr ::= expr "+" expr | expr "-" expr | "id" ``` is ambiguous: `id - id - id` has two derivations corresponding to the two possible groupings. The fix used in the earlier grammar — separate `expr`/`term`/`factor` layers with left recursion `expr ::= expr "+" term | term` — removes the ambiguity by forcing a single, canonical grouping (here, left-associative), and this can be proved by showing the layered grammar generates a unique leftmost derivation for every string, via induction on the number of operators.

Left recursion is a parsing hazard, not a generative one. The rule `expr ::= expr "+" term` is left-recursive and generates exactly the intended language, but a naive recursive-descent (top-down) parser following this rule literally would call `expr()` inside `expr()` before consuming any input, looping forever. This is purely an artifact of the parsing strategy, not a flaw in the language $L(G)$ itself — it is routinely eliminated by rewriting left recursion into right recursion or iteration (as the EBNF version above does with `term ( "+" term )*`), a transformation provably preserving $L(G)$.

Trace a leftmost derivation of the string `id + id id` using the layered BNF grammar from above. ``` expr ::= expr "+" term | term term ::= term "" factor | factor factor ::= "(" expr ")" | "id" ```

The final sentential form matches the target string exactly, so the derivation succeeds and the string is confirmed in $L(G)$. The parse tree built from these eight steps is exactly the tree drawn in the SVG figure above: `` binds tighter because `factor "" factor` is nested one level deeper than the top-level `+`, and this nesting is what a later semantic pass (evaluation, type checking) will walk over — a preview of how Expressions and Statements get their structure directly from grammar shape, not from any special-casing in the compiler. Contrast this with the ambiguous flat grammar `expr ::= expr "+" expr | expr "" expr | "id"` on the same string: it admits a derivation where `+` is applied last (grouping as `id + (id id)`, correct) and one where the tree structurally allows `*` to attach to the wrong operand under different bracketings for longer strings — the ambiguity becomes concrete once you try `id + id + id`, which yields two distinct trees, one grouping as $(id+id)+id$ and the other as $id+(id+id)$; both are valid parses under the flat grammar, and nothing in the grammar itself picks one over the other. This is precisely the defect the layered grammar was designed to eliminate.

Every major language specification — the ISO C and C++ standards, the Java Language Specification, the Python reference grammar, the ECMAScript specification — publishes its syntax as an (E)BNF grammar, and that grammar is the ground truth compiler and interpreter authors implement against. Parser generator tools such as Yacc, Bison, ANTLR, and Menhir take a BNF/EBNF-style grammar as literal input and automatically produce a working parser, turning the formalism directly into executable infrastructure. Data-interchange formats like JSON, configuration languages like YAML and TOML, and query languages like SQL all ship an official grammar so that independent implementations can agree on exactly what counts as valid input. Beyond programming languages, the same formalism underlies markup validation (XML DTDs and schemas), network protocol message formats (RFC grammars written in ABNF), and even some natural-language processing pipelines that use context-free grammars as an approximate model of sentence structure. Understanding grammars is the direct prerequisite to understanding how parsers, the next layer of any compiler front end, actually work.

Ask the tutor: Can you show me why the layered `expr`/`term`/`factor` grammar is provably unambiguous while the flat `expr ::= expr op expr | id` grammar is not?