Abstract syntax tree

LIDO is a specification language for abstract syntax trees. Here's a LIDO specification corresponding to Appel's Grammar 1.3:

Abstract syntax tree[32] :

RULE CompoundStm: Stm     ::= Stm ';' Stm             END;
RULE AssignStm:   Stm     ::= id ':=' Exp             END;
RULE PrintStm:    Stm     ::= 'print' '(' ExpList ')' END;
RULE IdExp:       Exp     ::= id                      END;
RULE NumExp:      Exp     ::= num                     END;
RULE OpExp:       Exp     ::= Exp Binop Exp           END;
RULE EseqExp:     Exp     ::= '(' Stm ',' Exp ')'     END;
RULE PairExpList: ExpList ::= Exp ',' ExpList         END;
RULE LastExpList: ExpList ::= Exp                     END;
RULE Plus:        Binop   ::= '+'                     END;
RULE Minus:       Binop   ::= '-'                     END;
RULE Times:       Binop   ::= '*'                     END;
RULE Div:         Binop   ::= '/'                     END;

This macro is invoked in definition 49.

Each rule is bracketed by the delimiters RULE and END;, its name is given as a label rather than a parenthesized suffix, and Appel's ``$\rightarrow$'' is rendered as ::=.

Grammar 1.3 doesn't define the type of the objects used to represent non-literal terminal symbols (here id and num), nor does it provide any handle for the root of the tree. Both of these deficiencies must be repaired:

Complete Appel's tree specification[33] :

RULE Axiom: Program ::= Stm END;

TERM id: CharPtr;
TERM num: int;

This macro is invoked in definition 49.

LIDO requires that every type be represented by an identifier. Thus it is not possible to use the type char* directly in a LIDO specification. CharPtr is used here to represent char*, and must be declared:

Representation of of char*[34] :

typedef char* CharPtr;

This macro is invoked in definition 53.