HANDBOOK / GENTLE PRIMER / At a Glance /
We presented above a concrete syntax for expressions. In this section, we discuss a so-called abstract syntax.
Abstract syntax is often much better suited as the basis for the specification of program transformations, and is used as an intermediate program representation in compilers.
Similar to concrete syntax, a class of phrases (here called terms) are defined by listing the alternatives (corresponding to the rules) and specifying the constituents of each alternative. Each alternative has a name (called a functor).
'type' Expr plus(Expr, Expr) minus(Expr, Expr) mult(Expr, Expr) div(Expr, Expr) neg(Expr) num(INT)
This introduces the type Expr. Values of this type are constructed as specified by the given alternatives.
For example, the alternative
num(INT)specifies that the functor num used with an argument of type INT represents a value of type Expr. For example, num(20) and num(30) are values of type Expr.
mult(Expr, Expr)specifies that the functor mult may be used with two arguments of type Expr. E.g. since num(20) and num(30) are values of type Expr the term mult(num(20), num(30)) is also a value of type Expr.
Similarly the alternative
plus(Expr, Expr)can be used to construct the value plus(num(10), mult(num(20), num(30))). This abstract syntax term can be used as a representation of the expression 10+20*30.
Note that in abstract syntax the structure of terms is uniquely determined.
Thus, we do not need to introduce several types to reflect the binding strength
plus(num(10), mult(num(20), num(30)))
is used as a representation of 10+(20*30)
and also as a representation of
the expression 10+20*30.