Abstract and Concrete Syntax

Write down the expression "one plus two times three". Already you feel the itch: does it mean (1+2)\times 3 = 9, or 1+(2\times 3) = 7? The string "1 + 2 * 3" does not say. It is a flat row of characters; the grouping — the thing that decides the answer — lives in your head, supplied by a precedence convention you learned long ago. This gap, between the text you type and the structure that has meaning, is the subject of this lesson, and it is one of the most clarifying distinctions in all of language theory.

We split syntax into two layers. Concrete syntax is the surface: the actual strings of characters, with their brackets, keywords, whitespace, and operator-precedence rules — everything a parser must wrestle with. Abstract syntax is what is left once parsing has done its job: a tree that records the essential structure and throws away the incidental punctuation. Theory — semantics, type systems, proofs — works almost entirely on the tree, because the tree is where the meaning lives. The string is merely how humans key the tree in.

Concrete syntax: strings and grammars

Concrete syntax is defined by a context-free grammar, traditionally written in BNF (Backus–Naur Form). A grammar for our arithmetic language that builds in precedence and associativity needs several nonterminals — one "level" per precedence tier — plus parentheses for grouping:

expr ::= expr "+" term | term term ::= term "*" factor | factor factor ::= number | "(" expr ")"

This grammar is doing a lot of quiet work. Because expr recurses on its left (expr "+" term), + is left-associative, so 1 - 2 - 3 groups as (1-2)-3. Because * lives on a deeper tier than +, multiplication binds tighter, so 1 + 2 * 3 is forced to mean 1 + (2*3). And "(" expr ")" lets you override both. All of this machinery — precedence tiers, associativity direction, the parentheses — is concrete-syntax bureaucracy. It exists to make an unambiguous, comfortable-to-type surface language. None of it survives into the tree.

Abstract syntax: the tree

Parse 1 + 2 * 3 and you get exactly one tree — and that tree, all by itself, resolves the ambiguity we started with. The + is the root; its right child is the \times node; the multiplication is below the addition, which is precisely the statement "multiply first, then add." No precedence rule is needed any more, because the precedence is now structure. Reveal it node by node:

This is an abstract syntax tree (AST). Notice what it omits: there are no parentheses, no whitespace, no hint of which precedence tier each node came from — that scaffolding did its job during parsing and was discarded. Notice too what it guarantees: the tree for 1 + 2 * 3 and the tree for the fully-parenthesised 1 + (2 * 3) are identical. Two different strings, one abstract syntax — because they mean the same thing. Conversely, (1 + 2) * 3 parses to a different tree (a \times at the root), and that structural difference is the whole difference in meaning.

Abstract syntax as an inductive datatype

Here is the pivotal move. We can define the set of ASTs directly, with no strings and no parser, as an inductively-defined datatype. This is the grammar we actually reason about:

e \;::=\; n \;\mid\; e_1 + e_2 \;\mid\; e_1 \times e_2

Read as an inductive definition, this says: the set \mathsf{Exp} of expression trees is the smallest set such that every numeral n is in it (the base cases), and whenever e_1 and e_2 are in it, so are the trees e_1 + e_2 and e_1 \times e_2 (the inductive cases). Crucially, this abstract grammar is free of the precedence cruft: there is only one nonterminal e, no tiers, no parentheses. It is allowed to be "ambiguous" as a string grammar precisely because it is not describing strings — it is describing trees, and a tree carries its own grouping.

Concrete syntax is a grammar over strings. Its job is to be unambiguous and human-friendly, so it carries precedence tiers, associativity, keywords and brackets. A parser maps a string to a tree (or rejects it).
Abstract syntax is an inductive definition of trees (terms). It has one production per constructor and no disambiguation cruft, because a tree already encodes its own structure.
The parser is the bridge: \text{parse} : \text{String} \rightharpoonup \mathsf{Exp}, a partial function (ill-formed strings have no tree).

The tree, as a datatype and a fold

The inductive definition transcribes directly into a TypeScript algebraic datatype — one variant per production — and any function over expressions is written by structural recursion, one case per variant. Below, the same tree is built two ways (from the ambiguous-looking 1 + 2 * 3 and from the explicit 1 + (2*3)) and shown to be structurally equal, while (1+2)*3 differs. Press Run:

// Abstract syntax as an inductive datatype: one variant per grammar production. type Exp = | { tag: "num"; n: number } // e ::= n | { tag: "add"; l: Exp; r: Exp } // e ::= e1 + e2 | { tag: "mul"; l: Exp; r: Exp }; // e ::= e1 * e2 const num = (n: number): Exp => ({ tag: "num", n }); const add = (l: Exp, r: Exp): Exp => ({ tag: "add", l, r }); const mul = (l: Exp, r: Exp): Exp => ({ tag: "mul", l, r }); // Structural recursion: render a tree as a fully-parenthesised string. function show(e: Exp): string { switch (e.tag) { case "num": return String(e.n); case "add": return `(${show(e.l)} + ${show(e.r)})`; case "mul": return `(${show(e.l)} * ${show(e.r)})`; } } // Structural equality of trees (are these the SAME abstract syntax?). function equal(a: Exp, b: Exp): boolean { if (a.tag !== b.tag) return false; if (a.tag === "num" && b.tag === "num") return a.n === b.n; if (a.tag !== "num" && b.tag !== "num") return equal(a.l, b.l) && equal(a.r, b.r); return false; } // The tree the parser builds for "1 + 2 * 3" (× binds tighter → nested on the right). const parsed = add(num(1), mul(num(2), num(3))); const explicit = add(num(1), mul(num(2), num(3))); // what "1 + (2*3)" means const other = mul(add(num(1), num(2)), num(3)); // what "(1+2)*3" means console.log("1 + 2 * 3 as a tree:", show(parsed)); console.log("1 + (2*3) as a tree:", show(explicit)); console.log("(1+2) * 3 as a tree:", show(other)); console.log("'1+2*3' == '1+(2*3)' ?", equal(parsed, explicit)); // true console.log("'1+2*3' == '(1+2)*3' ?", equal(parsed, other)); // false

The output makes the whole point concrete: two different strings collapse to one tree, and a third string that looks similar is a genuinely different tree. Once you are holding the tree, the string's ambiguity is simply gone — which is why every subsequent phase of a compiler, and every proof in this course, operates on the AST.

Why theory lives on the tree

Working on abstract syntax is not a convenience — it is what makes the mathematics tractable. Three payoffs stand out:

Recursion follows the definition. Because the datatype is inductive, we get structural recursion to define functions (an evaluator, a type checker, a compiler) and structural induction to prove things about them — one case per constructor, no strings in sight. (These are the next two lessons.)
No parsing noise. A rule like "to evaluate e_1 + e_2, evaluate the parts and add" would be hopeless to state over strings (which +? at which precedence tier?). Over trees it is a single, unambiguous clause.
Separation of concerns. Surface syntax can change — add a new bracket style, tweak precedence, switch to a Python-like layout — without touching the semantics, because the semantics only ever sees the tree. Concrete and abstract syntax evolve independently.

This is why a language-theory paper will write e_1 + e_2 and never worry about parentheses: it is silently working in abstract syntax, where e_1 + e_2 is a tree with a + at the root, fully grouped, unambiguous by construction.

The notation is a direct fossil of the ALGOL era. John Backus (who had just led the FORTRAN project) proposed the metasyntax for the 1959 ALGOL 58 report; Peter Naur, editing the landmark 1960 ALGOL 60 report, refined and popularised it — hence Backus–Naur Form. It was arguably the first time a real programming language's syntax was defined with full mathematical precision, and it set the template every language since has followed. The phrase abstract syntax was crystallised a little later by John McCarthy (of Lisp fame), who pointed out that a compiler really cares about the abstract structure of a program, not its concrete character-level form — and Lisp took the idea to its logical extreme by letting you write the AST directly as nested parentheses (S-expressions), erasing the concrete/abstract gap almost entirely. That is why Lisp has "no syntax": you are typing the tree.

A frequent confusion is to think the abstract grammar e ::= n \mid e_1+e_2 \mid e_1\times e_2 is "broken" because, read as a string grammar, it is ambiguous — the string 1+2*3 has two parse trees under it. That is not a bug; it is the whole point. An abstract grammar is not a description of strings and is not handed to a parser. It is an inductive definition of trees, and a tree cannot be ambiguous about its own grouping — it simply is a particular shape. Disambiguation (precedence, associativity, parentheses) is the responsibility of the concrete grammar, and it happens once, during parsing, before the tree ever exists.

The mirror-image mistake is to drag concrete details into the abstract world — to store parentheses, source whitespace, or "which precedence level produced this node" inside AST nodes and then let a proof depend on them. Resist it. If a piece of information does not affect meaning, it does not belong in the abstract syntax. (Real compilers do keep source positions for error messages, but they hang them off to the side as annotations — the semantic shape of the tree stays pristine.)