[NEXT] [PREV]    HANDBOOK / GENTLE PRIMER / At a Glance /

Abstract Syntax

Gentle
Applications
Concepts
Examples
Handbook
Support
Download

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.

The alternative


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 of operators. 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.



[NEXT] [PREV]