A natural and common way of representing programs inside a computer is to use trees (encoded as terms for example in Prolog, of structures or records in some other languages). Obviously these trees are not ordinary trees, but there is a type structure that tells which trees are well formed (for example the definition of a particular language may state that a statement cannot be an argument of an arithmetic expression). This type structure is called abstract syntax.
An abstract syntax consists of mutually recursively defined types, that we call phyla, a cartesian product of phyla, and typed constructors called operators. We have chosen to admit in this scheme type inclusions (that are not present in every abstract syntax systems). This means that even if an operator is defined to belong to a unique phylum, it can also be assigned many types due to type inclusions, expressing the fact that it can appear in different contexts (for example, an identifier can be the first argument of an assignment, but can also appear in an expression). We have also chosen to admit homogeneous lists in our type schemes.
Operators are defined by their signatures (the phylum to which it belongs and the number and types of its descendents, or sons). Up to now, this type structure is the one used in Metal and SDF, bringing to what is known as first-order abstract syntax. The formalism AS also admit some functional types to express syntactical bindings, bringing to second-order abstract syntax.
Choosing an abstract syntax for a particular language is not always an obvious task. It is a question of taste and experience. A good rule is to try to reflect the concepts and the semantics of the language. But it is sometimes easier if the language already exists to follow the concrete syntax if it is reasonable. One have also to make a compromise between a very strict type system that may need a large number of phyla and operators and a more permissive but more compact system (in this case the missing constraints will have to be checked later on in the semantics, for example by a type-checker). There is also the temptation to sacrifice the abstract syntax to some practical and independent reasons, for example when we want to generate a syntactical editor or a pretty printer. These are bad reasons that reveal some lacks of the tools that are used, and should not be taken into account.
This section give some examples that form a good basis to construct abstract syntaxes.
Thierry Despeyroux