The traditional method for specifying the syntax of a programming
language is in some variant of Backus-Naur form, or BNF. In this
method, one specifies the syntax by a grammar consisting of {\it
productions}. Each production defines the syntax of one element of the
language, say, a statement. For example, the Modula-3 WHILE
statement is defined as follows:
WhileSt = WHILE Expr DO S END.
S = [ Stmt { ";" Stmt } [";"] ].
Expr = ... .
Names that appear to the left of the = sign are called
non-terminals. Names, like WHILE, that only appear on the
right-hand side are called terminals. A terminal may denote a
language keyword like WHILE or an entity that is defined elsewhere,
for example a TEXT literal defined by the Modula-3 token grammar.
Such grammars define the {\it external} form of programs, which is
biased towards ease of reading by programmers and parsing by
compilers. As a result they tend to obscure the {\it essential}
structure of the language. For example, what is really important about
a WHILE statement is that it contains an Expr and an S
construct; the keywords WHILE, DO and END could be altered
without changing the meaning, as indeed could the order of occurrence
of the constructs. It should be obvious that the details of the
external syntax are of no help in analysing or reasoning on the
essential properties of programs. Therefore, we seek a more abstract
representation of programs that carries only the essential
information.
We will refer to the syntax of the external form of a language as the {\it concrete} syntax. If we abstract from the representational details of the concrete syntax, what we are left with is an {\it abstract} syntax for the language, defined by an {\it abstract grammar}.
Like the grammar for the concrete syntax, the abstract grammar is also
defined in terms of productions, terminals and non-terminals. To
define the abstract grammar we will use a slightly different syntax
for productions, one that is closer to the syntax of aggregate types
(e.g. RECORD) in programming languages. This syntax also
facilitates the mapping of the abstract syntax into Modula-3 data
types.
The abstract grammar defines a finite set of {\it constructs} using a finite set of {\it productions}, defined according to the conventions in the Modula-3 report, as follows:
Production = Construct "=" Aggregate | Choice .
Aggregate = { "[" AttributeName ":" AttributeType ";" "]" } .
Choice = Construct { "|" Construct } .
AttributeType = Construct | "{" Construct "}" .
A construct that is not defined by a production is a terminal;
otherwise it is a non-terminal. An AttributeName is a tag that
distinguishes repeated occurrences of the same construct in a
production. By convention Choice constructs are spelled in
upper-case and Aggregate constructs begin with an upper-case letter.
The abstract grammar production for a WhileSt might be defined as:
WhileSt = as_expr: EXPR; as_s: Stmts .
Stmts = as_stmt_s: { STM } .
STM = WhileSt | ... .
In the same way that a program defined by the concrete grammar has an
associated representation as a {\it parse tree}, so the equivalent
program defined in terms of the abstract grammar has a representation
as an {\it abstract syntax tree}. The leaves of the tree denote
terminal constructs, the interior nodes represent non-terminal
constructs, and the attribute names label the branches. The above
definition of the abstract grammar permits a node to have either a
fixed number of descendent nodes, a variable number, or a combination
of both. Some abstract grammar definitions restrict a node to have
either a fixed number of descendents or a variable number but not
both. However, this requires more constructs in the grammar. Indeed
the WhileSt production can be rewritten more compactly as follows:
WhileSt = as_expr: EXPR; as_stmt_s: { STM } .
STM = WhileSt | ... .
The acronym AST is widely used in place of abstract syntax tree. An
AST and its associated parse tree will always be similar in form;
however, the AST will usually contain less nodes, due to the reduction
in the number of constructs.
It is important to note that when we talk of a {\it tree}, we are referring to the {\it abstraction} of a tree. It is not implied that there is an actual data structure containing records and pointers. Such a structure is only one possible representation, although a convenient and common choice.
\subsection{Specifying an AST in Modula-3}
This section describes in general terms how the definition of a language in terms of an abstract grammar, and its associated AST, is mapped into an abstraction using the Modula-3 programming language.
There is an an obvious mapping from an Aggregate construct into
either a RECORD type or an OBJECT type. We choose the latter
because it supports abstraction better (the representation of
the components can more easily be hidden from a client) and
because the subtyping of OBJECT types directly supports the
Choice construct. For example, the production:
T = A | B | C.
can be expressed using objects as:
TYPE T <: ROOT; A <: T; B <: T; C <: T;
Modula-3 not only supports abstraction directly through interfaces and
opaque object types, it is also augmented with a formal specification
language called Larch/Modula-3, or LM3 for short. Amongst other things
LM3 allows object types to be annotated with abstract or
specification fields, thus permitting one to reason about these fields
without having to commit to a representation as an actual object
field. We will use specification fields to denote the attributes of an
aggregate production. LM3 also provides the notion of a {\it sequence}
as a primitive, again allowing the representation to be deferred. We
will use this facility to denote attributes that represent sequences
of nodes.
In this formalism, the WhileSt example would be defined as:
TYPE WhileSt <: STM;
<* FIELDS OF WhileSt
as_expr: EXPR;
as_stmt_s: SEQUENCE OF STM; *>
This is a simple, clear and concise notation in which to define an AST
for a given programming language. Furthermore, because it is defined
by a formal language, it offers the prospect of that some components
of a programming environment for the given language could be generated
automatically. For example, code could be generated that will
systematically visit every node in an AST. Note that the type of an
attribute must either be an object type denoting an abstract grammar
construct, or a sequence of such types. Later we will see how to add
additional attributes that can be any type allowed by the Modula-3
language.
The WhileSt node is an example of a situation that occurs frequently
in which all the members of a Choice construct in the grammar share
a common attribute. In such cases we can simplify the AST
specification by associating the attribute with the class that denotes
the choice. The different alternatives then inherit the attribute by
the normal rules of object subtyping.
Ultimately, this abstract definition of an AST node must be given a concrete representation. There are many possible representation for such a tree and there are trade-offs to be made between storage requirements and processing time. It is not the role of this interface to make those choices, only to provide mechanisms and standards to support them.
\subsection{Augmenting an AST}
There are many reasons why we might want to augment an AST definition
with additional constructs and attributes. The overriding reason is
that the abstract grammar is unable to define all the constraints on a
legal program. program. Many of the programs that can be generated
from the grammar are in fact illegal. There is no easy way in such a
context free grammar to express the fact that, for example, the type
of the EXPR construct of the WhileSt must be BOOLEAN. Nor that
all identifier uses must be bound to a declaration in scope. Such
constraints are defined by what is referred to as the static
semantics of the language, as opposed to the dynamic semantics
which define the meaning of the program when it is executed.
So, in order to analyse programs in a useful way we need, at the very
least, some way to represent the results of the static semantic
analysis. The obvious way to do this is to augment certain nodes in
an AST with additional attributes that specify this information, for
example the type of expressions. Choosing which nodes to annotate
and precisely what information to represent is a tricky task and
beyond the scope of this discussion. We can observe, however, that the
formalism that we have chosen is quite capable of specifying these
additional attributes, merely by adding them to the FIELDS
declaration. The result is an AST augmented with the additional
attributes. In truth the term augmented AST is somewhat of a misnomer
since there is nothing to prevent the augmented attributes in several
nodes having as value a reference to the same node, thus forming a
directed graph structure. However, it is conventional to continue to
use the term AST to refer to the entire structure. Note also that, unlike
the the attributes that denote the {\it pure} abstract syntax tree,
the additional attributes can be of any type that is provided by the
Modula-3 language.
Finally we can observe that practically all analyses of an AST will generate additional information that is of potential use by other tools. It is generally very much easier to attach this information directly to the AST than to create a separate data structure.
\subsection{AST Layers}
The previous section suggested augmenting the AST with attributes that capture the result of an analysis by a given tool. In a rich programming environment, consisting of many tools, many additional sets of attributes might be defined. If these attributes are all declared in the same interface, the result will be overwhelming. In addition, the scope for separate development will be greatly reduced. Previous AST designs, for example, DIANA, have specified the attributes for a fixed set of tools, thus placing additional tools at a disadvantage. One solution is to define a {\it property set} attribute on each node, that is capable of storing many attributes of different types, but this has the disadvantages of storage and access time overheads plus a more complex programming interface.
The basic idea is to define each set of nodes and attributes independently, and then define an AST as a combination of some or all of these sets. We refer to each set as an AST {\em layer} or, occasionally, a {\em view}.
\subsection{AST Layers in Modula-3}
This section describes how the notion of separate layers of an AST is mapped into the facilities available in Modula-3. The solution makes extensive use of {\it interfaces} and {\it partial revelations}.
An AST for a specific language is specified as a set of interfaces,
which share the naming convention LLAST, where LL is a
language-specific prefix, e.g. M3, for the Modula-3 AST. Each AST
layer is defined in an interface named LLAST_VV, where VV is a tag
denoting the layer, for example, AS for the syntactic layer. Each
interface defines the attributes available on a given node using the
FIELDS OF mechanism introduced previously. In order to quickly
relate an attribute to the layer in which is declared, attribute names
are given a prefix of the form vv_, for example, as_exp.
All AST nodes are declared to be subtypes of the AST.NODE class,
defined by this interface. An implementation of the interface will
define a set of standard methods that support common actions, such as
systematically visiting nodes in the AST. This interface does not
prescribe a set of methods; this is left to other interfaces.
Non-terminals that are defined as a set of alternatives using the
Choice construct in the abstract grammar are named using all upper
case characters. There are never any instances of these nodes in an
AST.
Sequence attributes are named with a suffix _s, to distinguish them
from other attributes.
Because of the prevalence of prefixes and suffixes in attribute names,
the standard Modula-3 capitalisation rules for multiword identifiers
are modified. Instead of WhileSt, we write While_st, and an
attribute of such a type in the AS layer would be named
as_while_st, rather than as_whileSt.
Using these conventions, interfaces are constructed as follows. The
WhileSt grammar fragment is used as an example.
INTERFACE LLAST_AS;
IMPORT AST;
TYPE
STM <: AST.NODE; EXPR <: AST.NODE;
WhileSt <: STM;
<* FIELDS OF WhileSt
as_expr: EXPR;
as_stmt_s: SEQUENCE OF STM; *>
Now consider a {\em static semantic} layer for the above grammer, in which
all EXPR nodes are given a type, denoted by the class LTYPE.
INTERFACE LLAST_SM;
IMPORT AST, LLAST_AS;
TYPE
LTYPE <: AST.NODE;
<* FIELDS OF LLAST_AS.EXPR
sm_ltype: LTYPE; *>
\subsubsection{Defining the concrete representation}
In practice there are two ways in which to represent the abstract
attributes defined in the FIELDS specifications, either directly as
fields of the object type, or indirectly through methods that set or
get the value. The convention is to reveal these access methods in
interfaces called LLAST_VV_F and LLAST_VV_M, respectively. In
either case this interface will contain, for each node to be
attributed, an object type with the same name as the abstract type,
plus a partial revelation that the abstract type is a subtype of this
new object type.
INTERFACE LLAST_AS_F;
IMPORT AST, LLAST_AS;
TYPE
While_st = LLAST_AS.STMT OBJECT
as_expr: LLAST_AS.EXPR := NIL;
as_stmt_s := REF ARRAY OF LLAST_AS.STMT := NIL;
END;
REVEAL
LLAST_AS.While_st <: While_st;
TYPE EXPR = LLAST_AS.EXPR; STMT = LLAST_AS.STMT;
END LLAST_AS_F.
When the LLAST_AS_F interface is imported, it allows access to
as_expr and as_stmt_s, and the REVEAL statement tells the
compiler that the actual node will have all of these fields, and
possibly some more. It is conventional to pass through the node and
class types that are not revealed, for example EXPR in the above, to
ensure that the next layer can access all the node names by referrring
to this layer alone.
The static semantic attributes can be given a similar concrete representation as follows:
INTERFACE LLAST_SM_F;
IMPORT AST, LLAST_AS, LLAST_SM;
IMPORT LLAST_AS_F AS Previous_View;
TYPE
EXPR = Previous_View.EXPR OBJECT
sm_ltype: LLAST_SM.LTYPE;
END;
REVEAL
LLAST_AS.EXPR <: EXPR;
TYPE
While_st = Previous_View.While_st;
STM = Previous_View.STM;
LTYPE = LLAST_SM.LTYPE;
END LLAST_SM_F.
Notice that in this layer the supertype is inherited from the previous
view, in this case, LLAST_AS_F.
Owing to the constraints of Modula-3 object subtyping, it is necessary to know the name of the layer that last added attributes to the node. If you get this wrong you will get an error message complaining about incompatible revelations at some point. However, whether this occurs at compile, link, or run-time depends on the Modula-3 implementation.
Ultimately, there must be an interface or module that chooses which layers
will actually exist in a given program, by making a concrete revelation
containing the corresponding declaration in the lowest layer that
is to be included. This is conventionally named LLAST_all. E.g.
INTERFACE LLAST_all;
IMPORT LLAST_AS, LLAST_SM;
IMPORT LLAST_SM_F AS Last_View;
REVEAL LLAST_AS.STMT = Last_View.STMT BRANDED OBJECT END;
REVEAL LLAST_AS.EXPR = Last_View.EXPR BRANDED OBJECT END;
REVEAL LLAST_AS.While_st = Last_View.While_st
BRANDED OBJECT END;
REVEAL LLAST_SM.LTYPE = Last_View.LTYPE
BRANDED OBJECT END;
END LLAST_all;
At first sight, this may all seem rather complicated. However, AST specifications for real languages and tools are inherently complex and there is much value to be gained in separating the specification into more manageable pieces. For example, the syntactic, semantic and code-generator attributes can be specified independently. To understand the syntactic specification, there is no need to see or understand the other two. Secondly, it is possible to replace a layer without affecting any of its ancestors, or add a completely new layer, for example to support a new programming environment tool. The key point to note is that although there may be many layers of a node, there is only one actual node type. Whenever an instance of a node is created it has the sum total of all the attributes that were specified in the contributing layers. So, although a parser might be separately compiled against the syntactic layer, it need only be relinked to incorporate a new tool with its own layer. This greatly facilitates the extensibility of the environment. It is perhaps unfortunate that Modula-3 does not support multiple inheritance, which would avoid the nuisance of the layer linearisation.
\subsection{Basic Definitions}
INTERFACEAnAST ; TYPE NODE <: ROOT; T = NODE;
AST.T is denoted by the node that defines the root of the tree.
A particular implementation of this interface will typically define
a standard set of methods on an AST.NODE.
END AST.