Abstract Syntax Tree

S-Expression Grammar

Compilation Units

Compilation Unit Node

compilationUnit :=
  '(' COMPUNIT filenameNode timestampNode digestNode moduleNode ')'
  ;

Generic Sample

(COMPUNIT
  (FILENAME ...)
  (COMPILED ...)
  (DIGEST ...)
  (DEFMOD ...))

Filename Node

filenameNode :=
  '(' FILENAME quotedLiteral ')'
  ;

Sample

(FILENAME "Foobar.def")

Timestamp Node

timestampNode :=
  '(' COMPILED quotedLiteral ')'
  ;

Sample

(COMPILED "202009242016000+900")

Digest Node

digestNode :=
  '(' DIGEST quotedLiteral ')'
  ;

Sample

(DIGEST "9E107D9D372BB6826BD81D3542A419D6")

Module Node

moduleNode :=
  defModNode | impModNode | progNode
  ;

Definition Modules

Definition Module Node

defModNode :=
  '(' DEFMOD idNode importNode* reExportNode* declarationNode* ')'
  ;

Generic Sample

(DEFMOD (ID "Foobar")
  (IMPORT ...)
  (REEXPORT ...)
  (CONST ...)
  (VAR ...)
  (TYPE ...)
  (PROC ...)
  (BIND ...))

Identifier Node

idNode :=
  '(' ID quotedLiteral ')'
  ;

Sample

(ID "Foobar")

Import Node

importNode :=
  '(' IMPORT quotedLiteral+ ')'
  ;

Sample

IMPORT Foo, Bar, Baz;

compiles to

(IMPORT "Foo" "Bar" "Baz")

Re-Export Node

reExportNode :=
  '(' REEXPORT quotedLiteral+ ')'
  ;

Sample

IMPORT Foo+, Bar+;

compiles to

(IMPORT "Foo" "Bar")
(REEXPORT "Foo" "Bar")

Declaration Node

declarationNode :=
  constDeclNode | varDeclNode | typeDeclNode | procDeclNode
  ;

Constant Declaration Node

constDeclNode :=
  '(' CONST idNode exprNode typeIdNode? ')'
  ;
alias typeIdNode = idNode ;

Samples

CONST Foo = 42;
CONST Bar : INTEGER = -1;

compiles to

(CONST (ID "Foo") (EXPR (NUM 42)))
(CONST (ID "Bar") (EXPR (NEG (NUM 1))) (ID "INTEGER"))

Variable Declaration Node

varDeclNode :=
  '(' VAR idListNode typeIdNode ')'
  ;

Samples

VAR foo : Foo;
VAR i, j : INTEGER;

compiles to

(VAR (ID "foo") (ID "Foo"))
(VAR (ID "i" "j") (ID "INTEGER"))

Identifier List Node

idListNode :=
  '(' ID quotedLiteral+ ')'
  ;

Sample

(ID "foo" "bar" "baz")

Type Declaration Node

typeDeclNode :=
  '(' TYPE idNode typeConstructorNode ')'
  ;
typeConstructorNode :=
  aliasTypeNode | derivedTypeNode | subrangeTypeNode |enumTypeNode |
  setTypeNode | arrayTypeNode | recordTypeNode | pointerTypeNode |
  opaqueTypeNode | procTypeNode
  ;

Generic Sample

(TYPE (ID "TypeIdent") ...)

Alias Type Node

aliasTypeNode :=
  '(' ALIAS baseTypeNode ')'
  ;
alias baseTypeNode = typeIdNode ;

Sample

TYPE Foo = ALIAS OF Bar;

compiles to

(TYPE (ID "Foo") (ALIAS (ID "Bar)))

Derived Type Node

alias derivedTypeNode = typeIdNode ;

Sample

TYPE Foo = Bar;

compiles to

(TYPE (ID "Foo") (ID "Bar))

Subrange Type Node

subrangeTypeNode :=
  '(' SUBR baseTypeNode lowerBound upperBound ')'
  ;
alias lowerBound, upperBound = exprNode ;

Sample

TYPE Hour = [0..23] OF INTEGER;

compiles to

(TYPE (ID "Hour") (ID "INTEGER") (SUBR (EXPR (NUM 0))(EXPR (NUM 23))))

Enumeration Type Node

enumTypeNode :=
  '(' ENUM valueListNode baseTypeNode? ')'
  ;
alias valueListNode = idListNode ;

Samples

TYPE Colour = ( Red, Green, Blue );
TYPE MoreColour = ( +Colour, Orange, Magenta );

compiles to

(TYPE (ID "Colour") (ENUM (ID "Red" "Green" "Blue")))
(TYPE (ID "MoreColour") (ENUM (ID "Orange" "Magenta") (ID "Colour")))

Set Type Node

setTypeNode :=
  '(' SET enumTypeIdNode ')'
  ;
alias enumTypeIdNode = typeIdNode ;

Sample

TYPE ColourSet = SET OF Colour;

compiles to

(TYPE (ID "ColourSet") (SET (ID "Colour")))

Array Type Node

arrayTypeNode :=
  '(' ARRAY capacity baseTypeNode ')'
  ;
alias capacity = exprNode ;

Sample

TYPE Str80 = ARRAY 80 OF CHAR;

compiles to

(TYPE (ID "Str80") (ARRAY (EXPR (NUM 80)) (ID "Colour")))

Record Type Node

recordTypeNode :=
  '(' RECORD baseTypeNode fieldListNode+ ')'
  ;

Samples

TYPE Point = RECORD ( NIL )
  x, y : REAL
END; (*RECORD*)

TYPE ColourPoint = RECORD ( Point )
  colour : Colour
END; (*RECORD*)

compiles to

(TYPE (ID "Point")
  (RECORD (ID "NIL")
    (FIELD (ID "x" "y") (ID "REAL"))))
(TYPE (ID "ColourPoint")
  (RECORD (ID "Point")
    (FIELD (ID "colour") (ID "Colour"))))

Field List Node

fieldListNode :=
  '(' FIELD idListNode fieldTypeNode ')'
  ;

Field Type Node

fieldTypeNode :=
  typeIdNode | arrayTypeNode | pointerTypeNode | procTypeNode
  ;

Pointer Type Node

pointerTypeNode :=
  '(' POINTER targetTypeIdNode ')'
  ;
alias targetTypeIdNode = typeIdNode;

Sample

TYPE FooPtr = POINTER TO Foo;

compiles to

(TYPE (ID "FooPtr") (POINTER (ID "Foo")))

Opaque Type Node

opaqueTypeNode :=
  '(' OPAQUE allocSize? ')'
  ;
alias allocSize = exprNode ;

Samples

TYPE String = OPAQUE POINTER;
TYPE HashKey = OPAQUE [KeyBits DIV 8];

compiles to

(TYPE (ID "String") (OPAQUE))
(TYPE (ID "HashKey") (OPAQUE (EXPR (DIV (ID "KeyBits") (NUM 8)))))

Procedure Type Node

procTypeNode :=
  '(' PROCTYPE formalTypeList returnTypeNode ')'
  ;
formalTypeList :=
  formalTypeNode+ | emptyNode
  ;
alias returnTypeNode = typeIdNode ;

Samples

TYPE BoolFunc = PROCEDURE () : BOOLEAN;
TYPE FooFunc = PROCEDURE ( Foo ) : INTEGER;
TYPE BarProc = PROCEDURE ( Bar; VAR Status );
TYPE WriteProc = PROCEDURE ( CONST ARRAY OF CHAR );

compiles to

(TYPE (ID "BoolFunc") (PROCTYPE () (ID "BOOLEAN")))
(TYPE (ID "FooFunc") (PROCTYPE (FT (ID "Foo")) (ID "INTEGER")))
(TYPE (ID "BarProc") (PROCTYPE (FT (ID "Bar")) (FT (VARP) (ID "Status"))))
(TYPE (ID "WriteProc") (PROCTYPE (FT (CONSTP) (ARRAYP) (ID "CHAR"))))

Formal Type Node

formalTypeNode :=
  '(' FT attrNode? idListNode+ structNode? typeIdNode ')'
  ;
attrNode :=
  '(' ( CONSTP | VARP ) ')'
  ;
structNode :=
  '(' ( ARRAYP | ARGLIST | CASTSEQ | CASTPTR ) ')'
  ;

Procedure Declaration Node

procDeclNode :=
  '(' PROC formalParamList returnTypeNode ')'
  ;
formalParamList :=
  formalParamNode+ | emptyNode
  ;

Samples

PROCEDURE isFoo () : BOOLEAN;
PROCEDURE length ( str : String ) : LONGCARD;
PROCEDURE Open ( f : File; VAR s : Status );
PROCEDURE Write ( CONST s : ARRAY OF CHAR );

compiles to

(PROC (ID "isFoo") () (ID "BOOLEAN"))
(PROC (ID "length") (FP (ID "str") (ID "String")) (ID "LONGCARD"))
(PROC (ID "Open") (FP (ID "f") (ID "File")) (FP (VARP) (ID "s") (ID "Status")))
(PROC (ID "Write") (FP (CONSTP) (ID "s") (ARRAYP) (ID "CHAR")))

Formal Parameter Node

formalParamNode :=
  '(' FP attrNode idListNode+ structNode typeIdNode ')'
  ;

Binding Declaration Node

bindDeclNode :=
  '( BIND idToBind targetToBindTo ')'
  ;
alias idToBind, targetToBindTo = idNode ;

Samples

CONST [TLIMIT] Capacity = 100;
PROCEDURE [LENGTH] length ( str : String ) : LONGCARD;

compiles to

(CONST (ID "Capacity) (EXPR (NUM 100)))
(BIND (ID "Capacity) (ID "TLIMIT"))
(PROC (ID "length") (FP (ID "str") (ID "String")) (ID "LONGCARD"))
(BIND (ID "length) (ID "LENGTH"))

Implementation and Program Modules

Program Module Node

progNode :=
  '(' PROG idNode importNode* declarationNode* blockNode ')'
  ;

Generic Sample

(PROG (ID "Foobar")
  (IMPORT ...)
  (CONST ...)
  (VAR ...)
  (TYPE ...)
  (PROC ...)
  (BIND ...)
  (UNQ ...)
  (BLOCK ...))

Implementation Module Node

impModNode :=
  '(' IMPMOD idNode importNode* declarationNode* blockNode? ')'
  ;

Generic Sample

(IMPMOD (ID "Foobar")
  (IMPORT ...)
  (CONST ...)
  (VAR ...)
  (TYPE ...)
  (PROC ...)
  (BIND ...)
  (UNQ ...)
  (BLOCK ...))