Abstract vs Concrete Grammars

The abstract grammar of a language is the parse tree; the concrete
grammar is the bracketed string. This distinction is crucial in compilers and
symbolic AI.

Definition 7.5.1 (notes p. 128): A tree grammar is a grammar where the
result data type is trees, not strings.

Definition 7.5.2: A regular tree grammar is a triple $\langle S, N, P \rangle$ with start symbol $S$, nonterminals $N$, and productions $A \to t$
where $A \in N$ and $t$ is a "well-formed expression" over $\Sigma$ (terminal
constructors) and $N$.

Definition 7.5.3 (notes p. 129): The underlying tree grammar of a language is
often called the abstract grammar; any derived (string) grammars — there
may be multiple — are called concrete grammars.

Why abstract is better:
- No need for brackets/parens to disambiguate.
- One canonical tree per formula (often).
- Tree manipulation is direct — recursion over tree structure.

Why concrete is needed:
- Humans want to read and write strings.
- Files and network communication use strings.
- We need a way to convert between abstract and concrete.

Example: an arithmetic expression $(2 + 3) \times 5$.

• Abstract (parse tree):

prod
/   \
sum   5
/ \
2  3

• Concrete: the string $(2 + 3) \times 5$ (with explicit brackets and infix).

Both describe the same expression. In a compiler, the front-end parses the
concrete syntax into the abstract syntax tree (AST); the back-end optimizes and
generates code from the AST.

SML datatypes give a concrete representation of term languages. For arithmetic:

Example term representing $-((X_{29} + 3) * 555)$:

This datatype is recursive: anum, aneg, etc. all contain aterms. Pattern matching on the constructors is how we write recursive functions over terms.

Evaluating an arithmetic term (variable bindings as int list):

Serialising a term to a string:

Test: aprint ex2 evaluates to "-(((X29+3)*555))". ✓

Mathematical expressions can be classified into five categories that capture the main syntactic patterns:

• Literal — a constant number: 3, 42, 3.14.
• Named variable — a variable symbol: x, y_{i,j}.
• Operator application — f(a, b), +, *, =.
• Named constant — a named constant (different from a literal): $\pi$, $e$, $c$.
• Binding — introduces new variables: $\forall x. P(x)$, $\int_0^1 f(x) dx$, $\sum_{i=0}^n a_i$.

In OpenMath (Def 5.5), these are abstract symbols:

Where omsymbol is a Content Dictionary entry — a URI identifying a known mathematical object. This lets expressions be transmitted symbolically with full semantic meaning.

Renaming bound variables preserves meaning: $\forall x. q(x) = \forall y. q(y)$. This is called $\alpha$-renaming or bound-variable renaming.

OpenMath objects can be serialised as XML using a small set of tags:

• <OMOBJ> — wraps an OpenMath object.
• <OMA> — operator application.
• <OMBIND> — binding (binder + bound vars + body).
• <OMBVAR> — list of bound variables.
• <OMS> — a symbol reference (a named constant or operator).
• <OMV> — a variable.

Example: $\forall a, b.\, a + b = b + a$ encodes as:

This is a concrete XML grammar for an abstract syntax — same idea as our abstract vs concrete grammars, with cd="..." pointing to a Content Dictionary.