Learning path

Full curriculum

Full curriculum

Unit content

Formal syntax and metavariables

A programming language can be studied independently of concrete punctuation by describing its abstract syntax: the tree-shaped forms from which valid programs are built.

A grammar such as

$$e ::= n \mid x \mid e+e \mid \lambda x.e \mid e\ e$$

defines a family of expressions $e$. Here $e$, $x$ and $n$ are metavariables: symbols in our mathematical description, not literal tokens of the language. The vertical bar means “one of these forms.”

For example, $\lambda x.(x+1)$ is generated by the abstraction form $\lambda x.e$, whose body is the addition expression $x+1$. Its construction can be represented as a syntax tree.

Concrete syntax answers how a programmer writes a construct; abstract syntax answers what construct it is. Parentheses, whitespace and precedence rules may disappear after parsing because they only disambiguate the concrete text.

Formal definitions often proceed by syntax-directed cases. If a theorem is stated for every expression generated by a grammar, each constructor gives a natural proof or evaluation case. This connection between grammar and cases is why compact syntax definitions are so useful in semantics and type systems.