Skip to content

AST Specification

Jump to bottom
M2SF Project Administrator edited this page May 18, 2017 · 25 revisions

Abstract Syntax Tree

M2Sharp encodes valid Modula-2 input in memory as an abstract syntax tree (AST).

The AST used by M2Sharp uses three kinds of nodes.

  • an EMPTY sentinel node
  • non-terminal nodes
  • terminal nodes

The Sentinel Node

The sentinel node EMPTY is used to encode the absence of an optional sub-node in non-terminal nodes.

Non-Terminal Nodes

Non-terminal nodes are used to encode non-terminal symbols such as modules, imports, definitions, declarations, statements and expressions.

AST, DEFMOD, IMPLIST, IMPORT, UNQIMP, DEFLIST, CONSTDEF, TYPEDEF, PROCDEF, SUBR, ENUM, SET, ARRAY, RECORD, POINTER, PROCTYPE, EXTREC, VRNTREC, INDEXLIST, FIELDLISTSEQ, FIELDLIST, VFLISTSEQ, VFLIST, VARIANTLIST, VARIANT, CLABELLIST, CLABELS, FTYPELIST, OPENARRAY, CONSTP, VARP, FPARAMLIST, FPARAMS, IMPMOD, BLOCK, DECLLIST, TYPEDECL, VARDECL, PROC, MODDECL, VSREC, VSFIELD, EXPORT, QUALEXP, STMTSEQ, ASSIGN, PCALL, RETURN, WITH, IF, SWITCH, LOOP, WHILE, REPEAT, FORTO, EXIT, ARGS, ELSIFSEQ, ELSIF, CASELIST, CASE, FIELD, INDEX, DESIG, DEREF, NEG, NOT, EQ, NEQ, LT, LTEQ, GT, GTEQ, IN, PLUS, MINUS, OR, ASTERISK, SOLIDUS, DIV, MOD, AND, FCALL, SETVAL.

Terminal Nodes

Terminal nodes are used to encode terminal symbols such as filenames, options, identifiers, integer literals, real number literals, character code and quoted literals.

IDENT, QUALIDENT, IDENTLIST, INTVAL, REALVAL, CHRVAL, QUOTEDVAL, FILENAME, OPTIONS.

Serialised Representation

Any AST node may be represented in a serialised format of the form

( nodetype subnode-0 subnode-1 subnode-2 ... subnode-N )

where the actual number of sub-nodes is dependent on the node type.

This form of tree representation is called an S-expression.

AST Node Reference

The structure of the AST used by M2Sharp is described below in S-expression format.

Empty Node

The EMPTY node encodes the absence of an optional sub-node.

S-Expression

emptyNode :=
  '(' EMPTY ')'
  ;

Root Node

The AST node encodes the root of the syntax tree.

Graph

root

S-Expression

astRootNode :=
  '(' AST filename options compilationUnit ')'
  ;

filename := filenameNode ; /* terminal node */

options := optionsNode ; /* terminal node */

compilationUnit :=
  defModuleNode | impModuleNode
  ;

Definition Module Node

The DEFMOD node encodes a definition module.

Graph

defmod

S-Expression

defModuleNode :=
  '(' DEFMOD moduleIdent importList definitionList ')'
  ;

moduleIdent := identNode ; /* terminal node */

importList :=
  importListNode | emptyNode
  ;

definitionList :=
  definitionListNode | emptyNode
  ;

Import List Node

The IMPLIST node encodes the entirety of import directives in a module.

importListNode :=
  '(' IMPLIST import+ ')'
  ;

import :=
  qImportNode | unqImportNode
  ;

Qualified Import Node

The IMPORT node encodes a qualified import directive.

qImportNode :=
  '(' IMPORT identList ')'
  ;
  
identList := identListNode ; /* terminal node */

Unqualified Import Node

The UNQIMP node encodes an unqualified import directive.

unqImportNode :=
  '(' UNQIMP moduleIdent identList ')'
  ;

Definition List Node

The DEFLIST node encodes one or more definitions.

Graph

definition

S-Expression

definitionListNode :=
  '(' DEFLIST definition+ ')'
  ;
  
definition :=
  constDefNode | typeDefNode | varDeclNode | ProcDefNode
  ;

Constant Definition Node

The CONSTDEF node encodes a constant definition.

constDefNode :=
  '(' CONSTDEF identNode exprNode ')'
  ;

Type Definition Node

The TYPEDEF node encodes a type definition.

typeDefNode :=
  '(' TYPEDEF identNode ( typeNode | emptyNode ) ')'
  ;

typeNode :=
  identNode | qualidentNode |
  subrTypeNode | enumTypeNode | setTypeNode | arrayTypeNode | recTypeNode |
  extRecTypeNode | vrntRecTypeNode | pointerTypeNode | procTypeNode
  ;

Procedure Definition Node

The PROCDEF node encodes a procedure definition.

procDefNode :=
  '(' PROCDEF identNode formalParamList returnType ')'
  ;

formalParamList :=
  formalParamListNode | emptyNode
  ;

Subrange Type Definition Node

The SUBR node encodes a subrange type definition.

subrTypeNode :=
  '(' SUBR lowerBound upperBound subrBaseType ')'
  ;

lowerBound := exprNode ;

upperBound := exprNode ;

subrBaseType :=
  identNode | qualidentNode | emptyNode
  ;

Enumeration Type Definition Node

The ENUM node encodes an enumeration type definition.

enumTypeNode :=
  '(' ENUM identListNode ')'
  ;

Set Type Definition Node

The SET node encodes a set type definition.

setTypeNode :=
  '(' SET countableType ')'
  ;

countableType :=
  identNode | qualidentNode | subrTypeNode | enumTypeNode
  ;

Array Type Definition Node

The ARRAY node encodes an array type definition.

arrayTypeNode :=
  '(' ARRAY indexTypeListNode arrayBaseType ')'
  ;

arrayBaseType := fieldType ;

Simple Record Type Definition Node

The RECORD node encodes a non-variant non-extensible record type definition.

recTypeNode :=
  '(' RECORD fieldListSeqNode ')'
  ;

Pointer Type Definition Node

The POINTER node encodes a pointer type definition.

pointerTypeNode :=
  '(' POINTER typeNode ')'
  ;

Procedure Type Definition Node

The PROCTYPE node encodes a procedure type definition.

procTypeNode :=
  '(' PROCTYPE formalTypeList returnedType ')'
  ;

formalTypeList :=
  formalTypeListNode | emptyNode
  ;

returnedType :=
   identNode | qualidentNode | emptyNode
   ;

Extensible Record Type Definition Node

The EXTREC node encodes an extensible record type definition.

extRecTypeNode :=
  '(' EXTREC recBaseType fieldListSeqNode ')'
  ;

recBaseType :=
  identNode | qualidentNode
  ;

Variant Record Type Definition Node

The VRNTREC node encodes a variant record type definition.

variantRecTypeNode :=
  '(' VRNTREC variantFieldListSeqNode ')'
  ;

Array Index Type List Node

The INDEXLIST node encodes one or more index types within an array type definition.

indexTypeListNode :=
  '(' INDEXLIST indexType+ ')'
  ;

indexType := countableType ;

Simple FieldList Sequence Node

The FIELDLISTSEQ node encodes a non-variant field list sequence within a record type definition.

fieldListSeqNode :=
  '(' FIELDLISTSEQ fieldListNode+ ')'
  ;

Simple FieldList Node

The FIELDLIST node encodes a non-variant field list within a field list sequence

fieldListNode :=
  '(' FIELDLIST identListNode fieldType ')'
  ;

fieldType :=
  identNode | qualidentNode | subrTypeNode | enumTypeNode | setTypeNode |
  arrayTypeNode | recTypeNode | pointerTypeNode | procTypeNode
  ;

Variant Record FieldList Sequence Node

The VFLISTSEQ node encodes a variant field list sequence within a variant record type definition.

variantFieldListSeqNode :=
  '(' VFLISTSEQ ( fieldListNode | variantFieldListNode )+ ')'
  ;

Variant FieldList Node

The VFLIST node encodes a variant field list within a variant field list sequence.

variantFieldListNode :=
  '(' VFLIST caseIdent caseType variantList defaultFieldListSeq ')'
  ;

caseIdent :=
  identNode | emptyNode
  ;

caseType :=
  identNode | qualidentNode
  ;

defaultFieldListSeq :=
  fieldListSeqNode | emptyNode
  ;

Variant List Node

The VARIANTLIST node encodes a variant list within a variant field list.

variantList :=
  '(' VARIANTLIST variantNode+ ')'
  ;

Variant Node

The VARIANT node encodes a variant within a variant list.

variantNode :=
  '(' VARIANT caseLabelListNode fieldListSeqNode ')'
  ;

Case Label List Node

The CLABELLIST node encodes a case label list within a variant record definition or case statement.

caseLabelListNode :=
  '(' CLABELLIST caseLabelsNode+ ')
  ;

Case Labels Node

The CLABELS node encodes start and end labels within a case label list.

caseLabelsNode :=
  '(' CLABELS startLabel endLabel ')'
  ;

startLabel := exprNode ;

endLabel :=  exprNode | emptyNode ;

Formal Type List Node

The FTYPELIST node encodes a formal type list within a procedure type definition.

formalTypeListNode :
  '(' FTYPELIST formalType+ ')'
  ;

formalType :=
  simpleFormalType | attrFormalType
  ;

simpleFormalType :=
  typeIdent | openArrayTypeNode
  ;

attrFormalType :=
  constAttrFormalTypeNode | varAttrFormalTypeNode
  ;

Open Array Parameter Node

The OPENARRAY node encodes an open array parameter within a formal type list.

openArrayTypeNode :=
  '(' OPENARRAY typeIdent ')'
  ;

typeIdent :=
  identNode | qualidentNode
  ;

CONST Parameter Node

The CONSTP node encodes a CONST parameter within a formal type list.

constAttrFormalTypeNode :=
  '(' CONSTP simpleFormalType ')'
  ;

VAR Parameter Node

The VARP node encodes a VAR parameter within a formal type list.

varAttrFormalTypeNode :=
  '(' VARP simpleFormalType ')'
  ;

Formal Parameter List Node

The FPARAMLIST node encodes a formal parameter list within a procedure type definition or procedure signature.

formalParamListNode :=
  '(' FPARAMLIST formalParamsNode+ ')'
  ;

Formal Parameters Node

The PARAMS node encodes formal parameters within a formal parameter list.

formalParamsNode :=
  '(' FPARAMS identListNode formalTypeNode ')'
  ;

Program Or Implementation Module Node

The IMPMOD node encodes an implementation module.

impModuleNode :=
  '(' IMPMOD moduleIdent priority importListNode blockNode ')'
  ;

priority :=
  exprNode | emptyNode
  ;

Block Node

The BLOCK node encodes a block within a module or procedure.

blockNode :=
  '(' BLOCK declarationList body ')'
  ;

declarationList :=
  declarationListNode | emptyNode
  ;

body :=
  statementSeqNode | emptyNode
  ;

Declaration List Node

The DECLLIST node encodes one or more declarations within a block.

declarationListNode :=
  '(' DECLLIST declarationNode+ ')'
  ;

declarationNode :=
  constDefNode | typeDeclNode | varDeclNode | procDeclNode | modDeclNode
  ;

Type Declaration Node

The TYPEDECL node encodes a type declaration.

typeDeclNode :=
  '(' TYPEDECL identNode ( typeNode | vsrTypeNode ) ')'
  ;

Variable Declaration Node

The VARDECL node encodes a variable declaration.

varDeclNode :=
  '(' VARDECL identListNode fieldType ')'
  ;

Procedure Declaration Node

The PROC node encodes a procedure declaration.

procDeclNode :=
  '(' PROC procDefNode blockNode ')'
  ;

Module Declaration Node

The MODDECL node encodes a local module declaration.

modDeclNode :=
  '(' MODDECL moduleIdent priority importListNode exportList blockNode ')'
  ;

exportList :=
  unqualExportNode | qualExportNode | emptyNode
  ;

Variable Size Record Type Declaration Node

The VSREC node encodes a variable size record type declaration.

vsrTypeNode :=
  '(' VSREC fieldListSeqNode varSizeFieldNode ')'
  ;

Variable Size Field Node

The VSFIELD node encodes the indeterminate field of a variable size record type.

varSizeFieldNode :=
  '(' VSFIELD varSizeField determinantField varSizeFieldType ')'
  ;

varSizeField := IdentNode ;

determinantField := IdentNode ;

varSizeFieldType := qualidentNode ;

Unqualified Export Node

The EXPORT node encodes an unqualified export directive within a local module declaration.

unqualExportNode :=
  '(' EXPORT identListNode ')'
  ;

Qualified Export Node

The QUALEXP node encodes a qualified export directive within a local module declaration.

qualExportNode :=
  '(' QUALEXP identListNode ')'
  ;

Statement Sequence Node

The STMTSEQ node encodes a statement sequence.

statementSeqNode :=
  '(' STMTSEQ statementNode+ ')'
  ;

statementNode :=
  assignmentNode | procCallNode | returnStmtNode | withStmtNode | ifStmtNode |
  caseStmtNode | loopStmtNode | whileStmtNode | repeatStmtNode | forStmtNode |
  exitStmtNode
  ;

Assignment Node

The ASSIGN node encodes an assignment statement.

assignmentNode :=
  '(' ASSIGN designator exprNode ')'
  ;

designator :=
  identNode | qualidentNode | derefNode | designatorNode
  ;

Procedure Call Node

The PCALL node encodes a procedure call statement.

procCallNode :=
  '( PCALL designator actualParams ')'
  ;

actualParams :=
  actualParamsNode | emptyNode
  ;

RETURN Statement Node

The RETURN node encodes a RETURN statement.

returnStmtNode :=
  '(' RETURN returnValue ')'
  ;

returnValue :=
  exprNode | emptyNode
  ;

WITH Statement Node

The WITH node encodes a WITH statement.

withStmtNode :=
  '(' WITH designator statementSeqNode ')'
  ;

IF Statement Node

The IF node encodes an IF statement.

ifStmtNode :=
  '(' IF exprNode ifBranch elsifSeq elseBranch ')'
  ;

ifBranch := statementSeqNode ;

elsifSeq :=
  elsifSeqNode | emptyNode
  ;

elseBranch :=
  statementSeqNode | emptyNode
  ;

CASE Statement Node

The SWITCH statement encodes a CASE statement.

caseStmtNode :=
  '(' SWITCH exprNode caseListNode elseBranch ')'
  ;

LOOP Statement Node

The LOOP node encodes a LOOP statement.

loopStmtNode :=
  '(' LOOP statementSeqNode ')'
  ;

WHILE Statement Node

The WHILE node encodes a WHILE statement.

whileStmtNode :=
  '(' WHILE exprNode statementSeqNode ')'
  ;

REPEAT Statement Node

The REPEAT node encodes a REPEAT statement.

repeatStmtNode :=
  '(' REPEAT statementSeqNode exprNode ')'
  ;

FOR Statement Node

The FORTO node encodes a FOR statement.

forStmtNode :=
  '(' FORTO identNode startValue endValue stepValue statementSeqNode ')'
  ;

startValue : exprNode ;

endValue := expNode ;

stepValue :=
  exprNode | emptyNode
  ;

EXIT Statement Node

The EXIT encodes an EXIT statement.

exitStmtNode :=
  '(' EXIT ')'
  ;

Actual Parameters Node

The ARGS node encodes actual parameters in a procedure or function call.

actualParamsNode :=
  '(' ARGS exprNode+ ')'
  ;

ELSIFSEQ Node

The ELSIFSEQ node encodes an ELSIF sequence within an IF statement.

elsifSeqNode :=
  '(' ELSIFSEQ elsifNode+ ')'
  ;

ELSIF Node

The ELSIF node encodes a single ELSIF branch within an IF statement.

elsifNode :=
  '(' ELSIF exprNode statementSeqNode ')'
  ;

CASE List Node

The CASELIST node encodes a case list within a CASE statement.

caseListNode :=
  '(' CASELIST caseBranchNode+ ')'
  ;

CASE Branch Node

The CASE node encodes a case branch within a CASE statement.

caseBranchNode :=
  '(' CASE caseLabelListNode statementSeqNode ')'
  ;

Set Element List Node

The ELEMLIST node encodes the element list within a set value.

elementListNode :=
  '(' ELEMLIST element+ ')'
  ;

element :=
  expr | range
  ;

Expression Range Node

The RANGE node encodes a value range.

range :=
  '(' RANGE lowerValue upperValue ')'
  ;

lowerValue := expr ;

upperValue := expr ;

Record Field Selector Node

The FIELD node encodes a record field selector.

fieldSelectorNode :=
  '(' FIELD selector ')'
  ;

selector :=
  identNode | qualidentNode | designatorNode
  ;

Array Index Node

The INDEX node encodes an array subscript selector.

arrayIndexNode :=
  '(' INDEX subscript+ ')'
  ;

subscript := exprNode ;

exprNode :=
  negNode |  notNode | eqNode | neqNode | ltNode | ltEqNode | gtNode |
  gtEqNode | inNode | plusNode | minusNode | orNode | asteriskNode |
  solidusNode | divNode | modulusNode | andNode | designator |
  intValNode | realValNode | chrValNode | quotedValNode |
  funcCallNode | setValNode
  ;

Designator Node

The DESIG node encodes a designator.

designatorNode :=
  '(' DESIG head tail ')'
  ;

head :=
  identNode | qualidentNode | derefNode
  ;

tail :=
  fieldSelectorNode | arrayIndexNode
  ;

Pointer Dereference Node

The DEREF node encodes a pointer dereference.

derefNode :=
  '(' DEREF designator ')'
  ;

Arithmetic Negation Sub-Expression Node

The NEQ node encodes a sub-expression of the form - expr.

negNode :=
  '(' NEG right ')'
  ;

right : exprNode ;

Logical Negation Sub-Expression Node

The NOT node encodes a sub-expression of the form NOT expr.

notNode :=
  '(' NOT right ')'
  ;

Equality Sub-Expression Node

The EQ node encodes a sub-expression of the form expr1 = expr2.

eqNode :=
  '(' EQ left right ')'
  ;

left : exprNode ;

Inequality Sub-Expression Node

The NEQ node encodes a sub-expression of the form expr1 # expr2.

neqNode :=
  '(' NEQ left right ')'
  ;

Less-Than Sub-Expression Node

The LT node encodes a sub-expression of the form expr1 < expr2.

ltNode :=
  '(' LT left right ')'
  ;

Less-Than-Or-Equal Sub-Expression Node

The LTEQ node encodes a sub-expression of the form expr1 <= expr2.

ltEqNode :=
  '(' LTEQ left right ')'
  ;

Greater-Than Sub-Expression Node

The LT node encodes a sub-expression of the form expr1 > expr2.

gtNode :=
  '(' GT left right ')'
  ;

Greater-Than-Or-Equal Sub-Expression Node

The GTEQ node encodes a sub-expression of the form expr1 >= expr2.

gtEqNode :=
  '(' GTEQ left right ')'
  ;

Set Membership Sub-Expression Node

The IN node encodes a sub-expression of the form expr1 IN expr2.

inNode :=
  '(' IN left right ')'
  ;

Plus Sub-Expression Node

The PLUS node encodes a sub-expression of the form expr1 + expr2.

plusNode :=
  '(' PLUS left right ')'
  ;

Minus Sub-Expression Node

The MINUS node encodes a sub-expression of the form expr1 - expr2.

minusNode :=
  '(' '-' left right ')'
  ;

Logical Disjunction Sub-Expression Node

The OR node encodes a sub-expression of the form expr1 OR expr2.

orNode :=
  '(' OR left right ')'
  ;

Asterisk Sub-Expression Node

The ASTERISK node encodes a sub-expression of the form expr1 * expr2.

asteriskNode :=
  '(' ASTERISK left right ')'
  ;

Solidus Sub-Expression Node

The SOLIDUS node encodes a sub-expression of the form expr1 / expr2.

solidusNode :=
  '(' SOLIDUS left right ')'
  ;

Euclidean Division Sub-Expression Node

The DIV node encodes a sub-expression of the form expr1 DIV expr2.

divNode :=
  '(' DIV left right ')'
  ;

Remainder of Euclidean Division Sub-Expression Node

The MOD node encodes a sub-expression of the form expr1 MOD expr2.

modulusNode :=
  '(' MOD left right ')'
  ;

Logical Conjunction Sub-Expression Node

The AND node encodes a sub-expression of the form expr1 AND expr2.

andNode :=
  '(' AND left right ')'
  ;

Function Call Sub-Expression Node

The FCALL node encodes a function call sub-expression.

funcCallNode :=
  '( FCALL designator actualParams ')'
  ;

Set Value Sub-Expression Node

The SETVAL node encodes a set value sub-expression.

setValNode :=
  '( SETVAL setTypeIdent elementList ')'
  ;

setTypeIdent :=
  ident | qualident | emptyNode
  ;

elementList :=
  actualParams | emptyNode
  ;

(87) FILENAME -- File Node

Signature: (FILENAME "filename")

filenameNode := '(' FILENAME '"' filename '"' ')' ;

(88) OPTIONS -- Compiler Options Node

Signature: (OPTIONS "foo" "bar" "baz" ...)

optionsNode := '(' OPTIONS ( '"' option-name '"' )+ ')' ;

(89) IDENT -- Identifier Node

Signature: (IDENT "identifier")

identNode := '(' IDENT '"' Ident '"' ')' ;

Identifier List Node

The IDENTLIST node encodes an identifier list.

Graph

root

S-Expression

identListNode :=
  '(' IDENTLIST ( '"' Ident '"' )+ ')'
  ;

Example

(IDENTLIST "foo" "bar" "baz" ...)

(91) QUALIDENT -- Qualified Identifier Node

Signature: (QUALIDENT "foo" "bar" ...)

qualidentNode := '(' QUALIDENT ( '"' Ident '"' ) ( '"' Ident '"' )+ ')' ;

(92) INTVAL -- Whole Number Value Node

Signature: (INTVAL 12345) | (INTVAL #0x7FFF)

intValNode := '(' INTVAL ( lexeme | '#' lexeme ) ')' ;

(93) REALVAL -- Real Number Value Node

Signature: (REALVAL 1.23e45)

realValNode := '(' REALVAL lexeme ')' ;

(94) CHRVAL -- Character Code Value Node

Signature: (CHRVAL #0u7F)

chrValNode := '(' CHRVAL '#' lexeme ')' ;

(95) QUOTEDVAL -- Quoted Character or String Value Node

Signature: (QUOTEDVAL "quoted character or string")

quotedValNode := '(' QUOTEDVAL '"' lexeme '"' ')' ;

+++

Copyright (C) 2017 Modula-2 Software Foundation

Clone this wiki locally