The abstract syntax of Exp

We propose the following Metal syntax specification for Exp: 


definition of Exp is
  abstract syntax
    exp_s -> EXP + ...;
    assign -> VAR EXP;
    plus -> EXP EXP;
    minus -> EXP EXP;
    prod -> EXP EXP;
    uminus -> EXP;
    variable -> implemented as IDENTIFIER;
    integer -> implemented as INTEGER;

    EXP_S ::= exp_s;
    EXP ::= assign plus minus prod uminus variable integer;
    VAR ::= variable;
    INTEGER ::= integer;
end definition

The identifier following ``definition of'' is the name of the language.

The exp_s list operator must contain at least one expression. The variable and integer operators are atomic. Their implementation in Le-Lisp is described by the phrase implemented as TYPE. When an atomic value is recognized by the lexical analyzer, it is converted into the specified Vtp type. This value is stored in the abstract syntax tree and may be pretty printed or retrieved by program. The remaining operators of the specification are fixed arity.

The EXP_S phylum contains the ``root'' operator of the language, exp_s. It does not appear on the right hand side of any operator definition, so the Metal type checker issues the warning Unused Phylum. The INTEGER phylum does not appear on the right hand side of an operator definition, but we include for semantics purposes -it identifies a subset of expressions limited to integers. We refer to this phylum later in Typol programs.

Note that the variable operator belongs to two phyla. The VAR phylum allows us to restrict the type of operators considered valid on the left hand side of an assignment statement.

The abstract syntax defines valid sentences in the language that we represent as abstract syntax trees. For example, in figure we show a legal tree that corresponds to the expression B := A * (3 + 10). The definition of the assign operator prevents us from replacing the variable B with an operator that doesn't belong to the phylum VAR. Once we have an abstract syntax definition, we could manually construct abstract syntax trees using Vtp primitives, but we prefer designing a parser to do the job.

Tutorial