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.

emptyNode :=
  '(' EMPTY ')'
  ;

Root Node

The AST node encodes the root of the syntax tree.

astRecord :=
  '(' 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.

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.

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 ')'
  ;

(34) IMPMOD -- Program Or Implementation Module Node

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

priority := exprNode | emptyNode ;

(35) BLOCK -- Block Node

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

declarationList := declarationListNode | emptyNode ;

body := statementSeqNode | emptyNode ;

(36) DECLLIST -- Declaration List Node

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

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

(37) TYPEDECL -- Type Declaration Node

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

(38) VARDECL -- Variable Declaration Node

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

(39) PROC -- Procedure Declaration Node

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

(40) MODDECL -- Module Declaration Node

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

exportList := unqualExportNode | qualExportNode | emptyNode ;

(41) VSREC -- Variable Size Record Type Declaration Node

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

(42) VSFIELD -- Variable Size Field Node

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

varSizeField := IdentNode ;

determinantField := IdentNode ;

varSizeFieldType := qualidentNode ;

(43) EXPORT -- Unqualified Export Node

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

(44) QUALEXP -- Qualified Export Node

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

(45) STMTSEQ -- Statement Sequence Node

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

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

(46) ASSIGN -- Assignment Node

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

designator := identNode | qualidentNode | derefNode | designatorNode ;

(47) PCALL -- Procedure Call Node

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

actualParams := actualParamsNode | emptyNode ;

(48) RETURN -- RETURN Statement Node

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

returnValue := exprNode | emptyNode ;

(49) WITH -- WITH Statement Node

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

(50) IF -- IF Statement Node

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

ifBranch := statementSeqNode ;

elsifSeq := elsifSeqNode | emptyNode ;

elseBranch := statementSeqNode | emptyNode ;

(51) SWITCH -- CASE Statement Node

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

(52) LOOP -- LOOP Statement Node

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

(53) WHILE -- WHILE Statement Node

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

(54) REPEAT -- REPEAT Statement Node

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

(55) FORTO -- FOR Statement Node

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

startValue : exprNode ;

endValue := expNode ;

stepValue := exprNode | emptyNode ;

(56) EXIT -- EXIT Statement Node

exitStmtNode := '(' EXIT ')' ;

(57) ARGS -- Actual Parameters Node

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

(58) ELSIFSEQ -- ELSIFSEQ Node

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

(59) ELSIF -- ELSIF Node

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

(60) CASELIST -- CASE List Node

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

(61) CASE -- CASE Branch Node

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

(62) ELEMLIST -- Set Element List Node

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

element := expr | range ;

(63) RANGE -- Expression Range Node

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

lowerValue := expr ;

upperValue := expr ;

(64) FIELD -- Record Field Selector Node

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

selector := identNode | qualidentNode | designatorNode ;

(65) INDEX -- Array Index Node

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 ;

(66) DESIG -- Designator Node

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

head := identNode | qualidentNode | derefNode ;

tail := fieldSelectorNode | arrayIndexNode ;

(67) DEREF -- Pointer Dereference Node

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

(68) NEG -- Arithmetic Negation Sub-Expression Node

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

right : exprNode ;

(69) NOT -- Logical Negation Sub-Expression Node

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

(70) EQ -- Equality Sub-Expression Node

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

left : exprNode ;

(71) NEQ -- Inequality Sub-Expression Node

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

(72) LT -- Less-Than Sub-Expression Node

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

(73) LTEQ -- Less-Than-Or-Equal Sub-Expression Node

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

(74) GT -- Greater-Than Sub-Expression Node

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

(75) GTEQ -- Greater-Than-Or-Equal Sub-Expression Node

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

(76) IN -- Set Membership Sub-Expression Node

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

(77) PLUS -- Plus Sub-Expression Node

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

(78) MINUS -- Minus Sub-Expression Node

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

(79) OR -- Logical Disjunction Sub-Expression Node

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

(80) ASTERISK -- Asterisk Sub-Expression Node

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

(81) SOLIDUS -- Solidus Sub-Expression Node

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

(82) DIV -- Euclidean Division Sub-Expression Node

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

(83) MOD -- Remainder of Euclidean Division Sub-Expression Node

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

(84) AND -- Logical Conjunction Sub-Expression Node

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

(85) FCALL -- Function Call Sub-Expression Node

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

(86) SETVAL -- Set Value Sub-Expression Node

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 '"' ')' ;

(90) IDENTLIST -- Identifier List Node

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

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

(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