| Number | Character | Number | Character |
|---|---|---|---|
| 0 | 0 | 32 | @ |
| 1 | 1 | 33 | A |
| 2 | 2 | 34 | B |
| 3 | 3 | 35 | C |
| 4 | 4 | 36 | D |
| 5 | 5 | 37 | E |
| 6 | 6 | 38 | F |
| 7 | 7 | 39 | G |
| 8 | 8 | 40 | H |
| 9 | 9 | 41 | I |
| 10 | : | 42 | J |
| 11 | ; | 43 | K |
| 12 | < | 44 | L |
| 13 | = | 45 | M |
| 14 | > | 46 | N |
| 15 | ? | 47 | O |
| 16 | Space | 48 | P |
| 17 | ! | 49 | R |
| 19 | # | 51 | S |
| 20 | £ | 52 | T |
| 21 | % | 53 | U |
| 22 | & | 54 | V |
| 23 | ' | 55 | W |
| 24 | ( | 56 | X |
| 25 | ) | 57 | Y |
| 26 | * | 58 | @Z |
| 27 | + | 59 | [ |
| 28 | , | 60 | $ |
| 29 | - | 61 | ] |
| 30 | . | 62 | ↑ |
| 31 | / | 63 | ← (Newline) |
The character numbered 63 is used to indicate a newline character in the input to a TREE-META translator.
First column indicates the Section where the definition appears.
2.1 alternative ::= test qtestlist? | <- testlist
2.1 alternativelist ::= alternative | alternativelist / alternative
4.1 arglist ::= argmnt | arglist , argmnt
4.1 argmnt ::= nodename |label |string
6.1 arith ::= assignment | call | relation | function
6.1 arithlist ::= arith | arithlist ; arith
6.1 arithmetic ::= < arithlist >
6.1 assignment ::= identifier <- expression
4.1 basictype ::= .NUM | .ID | .OCT | .HEX | .SR | .CHR | .DIG | .LET
6.1 call ::= identifier subarg
4.1 coderule ::= identifier outrulelist ; | simplecoderule ;
1.4 digit ::= 0|1|2|3|4|5|6|7|8|9
6.1 expression ::= function | primary | expression op primary |
6.1 expression ↑ integer | expression ↑ - integer
6.1 function ::= identifier subarg
1.4 identifier ::= letter| identifier letter | identifier digit
1.4 integer ::= digit | integer digit
2.1 integerorstring ::= integer | string
4.1 item ::= - | identifier [ nodetest? ] | string | nodename | label | basictype
4.1 label ::= #1 | #2 | #3 | #4
1.4 letter ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
4.1 nodename ::= * integer | nodename : * integer
4.1 nodetest ::= item | nodetest , item
3.1 ntest ::= : identifier | : identifier [ integer ] | [ integer ] | + string | *
6.1 op ::= + | - | & | ! | :
4.1 outalternative ::= outitem | outalternative outitem
4.1 outexpression ::= outalternative | outexpression / outalternative
4.1 outitem ::= outputtext | nodename | identifier [ arglist? ] |
4.1 arithmetic | (outexpression) | .EMPTY | label
4.1 outputtext ::= % | string | !string | @ integer
4.1 outrule ::= [ nodetest? ] => outexpression
4.1 outrulelist ::= outrule | outrulelist outrule
1.4 prefix ::= .LIST | .DELIM (integer, integer, integer)
1.4 prefixlist ::= prefix | prefixlist prefix
6.1 primary ::= identifier | - integer | integer
1.4 program ::= .META identifier prefixlist rulelist .END
2.1 qtest ::= ntest | stest ? integerorstring?
2.1 qtestlist ::= qtest | qtestlist qtest
6.1 relation ::= identifier rop expression
6.1 rop ::= = | # | > | <
1.4 rule ::= syntaxrule | coderule | symbolrule
1.4 rulelist ::= rule | rulelist rule
4.1 simplecoderule ::= identifier / => simpleoutexpression | identifier / => .EMPTY
4.1 simpleoutexpression ::= outputtext | simpleoutexpression outputtext
2.4 stest ::= string | identifier | . string | @ integer | .EMPTY |
( alternativelist ) | $ stest | basictype
2.1 string ::= Any string of characters between a pair of the current
string delimiter characters
6.1 subarg ::= [ nodename ] | [ expression ]
7,1 symbolrule ::= identifier := outexpression
2.1 syntaxrule ::= identifier = alternativelist ;
2.1 test ::= ntest | stest
2.1 testlist ::= test | testlist test
.META PROGM
OUTPT[-,-] => % *1 ':' % '%PUSHJ;' % *2 '%POPJ;' % ;
AC[-,-,-] => *1 *3 ACX [*2,#1] #1 ':' % ;
ACX[AC[-,-,-],#1] => #1 ');' % *1:*1 *1:*3 ACX[*1:*2,#1]
[-,#1] => #1 ');' % *1 ;
T/ => '%BT;DATA(@' ;
F/ => '%BF;DATA(@' ;
BALTER[-] => '%SAV;' % *1 '%RSTR;' % ;
OER[-,-] => *1 '%OER;' % *2 ;
OUTAB[-] => <TN <- CONV[*1]; OUT[TN] > ');' % ;
ERCODE [-,NUM] => *1 '%ERCHK;DATA(' OUTAB[*2]
[-.-] => *1 '%ERSTR;DATA(' OPSTR[*2] ;
ERR[-] => *1 '%ERCHK;DATA(0);' % ;
DOO[-,-] => *1 *2 ;
NDMK[-,-] => '%MKND;DATA(@' *1 ',' *2 ');' % ;
NDLB => '%NDLBL;DATA(@' *1 ');' % ;
MKNODE [-] => '%NDMK;DATA(' *1 ');' % ;
GOO/ => '%OUTRE;'% ;
SET/ => '%SET;' % ;
PRIM[.ID] => '%' *1 ';' %
[.SR] => '%SRP;DATA(' OPSTR[*1] ;
CALL[-] => '%CALL;DATA(@' *1 ');' % ;
STST[-] => '%TST;DATA(' OPSTR[*1] ;
SCODE[-] => '%CHRCK;DATA(' OUTAB[*1] ;
ARB[-] => #1 ':' % *1 '%BT;DATA(@' #1 ');' % '%SET;' % ;
BEGINN[-.-] => <B <- 0 > *2 'ENTRY 0;%INIT;%CALL;DATA(@' *1 ');' %
'%FIN;' % ;
NOTAB/ => '%NOTAB;' % ;
LIST/ => '%LIST;' % ;
DELIM[-,-,-] => '%DELIM;DATA(' *1 ');' %
'%BEGCM;DATA(' *2 ');' %
'%ENDCM;DATA(' *3 ');' % ;
ENDN{} => % 'END' % '**' '**' % ;
DOIT[-] => *1 '%OUTS;' % ;
LCHASE[-] => '%LCH;DATA(' *1 ');' % ;
GNLB[-] => '%GNLB;DATA(' *1 ');' % ;
OUTCR/ => '%OCR;' % ;
OUTSR[-] => '%OUTSR;DATA(' OPSTR[*1] ;
IMED[-] => *1 % ;
OCODE[-] => '%OCODE;DATA(' OUTAB[*1] ;
ITNUM[SET[]] => *1
[-] => *1 <Q <- Q - 1 > ;
OUTA[] => '%LOAD;DATA(1,' <OUT[A] > ');' % ;
LITEM[-] => <A<- 0; Q <-0 > NCOUNT[*1]
( <Q = 0 > '%CNTCK;DATA(' < OUT[A] > ');' % /
<A <-1> *1 '%BF;DATA(@' #1 ');'%
'%CNTCK;DATA(' < OUT[A] > ');' % #1 ':' % ) ;
ZITEM[] => '%CNTCK;DATA(0);' % ;
NCOUNT[ITMSTR[-,-]] => NCOUNT [*1:*1] NCOUNT[*1:*2]
[ITNUM[SET[]] => <A <- A+1>
[-] => <A <- A+1; Q <-Q+1 > ;
ITMSTR[ITNUM[SET[]],-] => <A<-A+1 > *2
[-,-] => *1 <A<-A+1> ( <Q = 0> .EMPTY /
'%BF;DATA(@' #1 ');' % *2 #1 ':' %) ;
RITEM[-,-] => '%RITEM;DATA(@' *1 ',' < OUT(A)> ');' %
'%BF;DTA(@' #1 ');' %
<PUSH[Q] ; PUSH[A] > '%SAV1;' % *2
'XRSTR1;' %
< A <-POP(0);Q<-POP(0) > #1 ':' % ;
FITEM[-] => OUTA[] '%' *1 'G;' % ;
TTST[-] => OUTA[] '%TTST;DATA(' OPSTR[*1] ;
NITEM[-] => '%SNITM;DATA(' <OUT[A] > ');' % *1 '%NITEM;' % ;
GNITEM[-] => '%GNITEM;DATA(' *1 ',' <OUT[A] > ');' % ;
CHASE[-,-] => *1 '%CHASE;DATA(' *2 ');' % ;
ARG[.SR] => <A<-+1> '%SRARG;DATA(' OPSTR[*1]
[-] => <A<-+1> *1 '%PUSHK;' % ;
GENARG[-] => '%GNARG;DATA(' *1 ');' % ;
OUTCLL[-,-] => <A<-0> *2 NDLB[*1] '%OUTCL;DATA(' <OUT[A]> ');' % ;
STOR[-,-] => GET[*2] '%STORE;DATA(@' ADR[*1] ');' % ;
EQ[-,-] => '%COMPE;DATA(' VAL[*1] ');' % ;
NEQ[-,-] => '%COMPNE;DATA(' VAL[*1] ');' % ;
GT[-,-] => '%COMPGT;DATA(' VAL[*1] ');' % ;
LT[-,-] => '%COMPLT;DATA(' VAL[*1] ');' % ;
MTEST[-] => GET[*1:*2] *1 ;
CALLP[-,-] => GET[*2] '%' *1 ';' % ;
GET[.ID] => '%LOAD;DATA(0,@' ADR[*1] ');' %
[.NUM] => '%LOAD;DATA(0,' VAL[*1] ');' %
[MINUSS[-]] => '%LOAD;DATA(' VAL[*1] ');' %
[-] => *1 ;
VAL[.ID] => '0,@' ADR[*1]
[MINUSS[-]]=> '1,-' *1:*1
[.NUM] => '1,' *1 ;
BINOP[-,-,-] => GET[*1] OPCODE[*2] VAL[*3] ');' %;
OPCODE['+'] => '%ADD;DATA('
['-'] => '%SUB;DATA('
['&'] => '%AND;DATA('
['|'] => '%OR;DATA('
[':'] => '%EX;DATA(' ;
RSH[-,-] => GET[*1] '%SHIFTR;DATA(' *2 ');' % ;
LSH[-,-] => GET[*1] '%SHIFTL;DATA(' *2 ');' % ;
ADDR['TYPE'] => '%' *1
['LEVEL'] => '%' *1
['VALUE'] => '%' *1
[-] => <LOOK[*1]> '%A+' <OUT[VALUE] > /
'%A+' <B <-B+1;VALUE <-B;ENTER[*1];OUT[VALUE] > ;
SETMFG[STOR[-,-}} => *1 '%SET;' %
[DOO[-,-]] =>*1:*1 SETMFG[*1:*2]
[-] => *1 ;
SCAN[-,-] => % *1 ':' '%BEGIN;' % '%SCSET;' % #1 ':' %
*2 '%SCHEK;' % '%BR;DATA(@' #1 ');' % ;
OPSTR[-] => <OUTL[*1]> ',' STRNG[*1] ');' % ;
STRNG[-] => @18 *1 @18 ;
OUTRL[-,-] => % 'DATA(' STRNG[*1] ',' <OUTL[*1] ');' % *1 ':' %
'%BEGN;' % *2 '%END;' % ;
SIMP[-,-] => % 'DATA(' STRNG[*1] ',' <OUTL[*1] > ');' % *1 ':' %
'%SBEGN;' % *2 '%SEND;' % ;
NUL/ => .EMPTY ;
MINUSS/ => .EMPTY ;
PROGM = '.META' .ID ?1? :NUL[0]
$( PREFIX :DOO[2] ) :BEGINN[2] *
$( RULE *) '.END' ?2? :ENDN[0] * ;
PREFIX = '.NOTAB' :NOTAB[0] / '.LIST' :LIST[0] /
'.DELIM '(' .NUM ',' .NUM ',' .NUM')' :DELIM[3] ;
RULE = .ID ( '=', EXP ?3? :OUTPT[2] /
'/' '=>' ?3? GEN1 ?4? :SIMP[2] /
':' '=' OUTEXP :SCAN[2] /
OUTRUL :OUTRL[2] ) ?5? ';' ?6? ;
EXP = ('<-' SUBACK ?7? :BALTER[1] / SUBEXP )
( '/' EXP ?9? :T[0] :AC[3]/.EMPTY );
SUBACK = NTEST (SUBACK :DOO[2] / .EMPTY ) /
STEST (SUBACK :F[0] :AC[3] / .EMPTY) ;
SUBEXP = (NTEST / STEST ) (NOBACK :F[0] :AC[3] / .EMPTY);
NOBACK = (NTEST / STEST ( '?' (.NUM / .SR) ?10? '?' ?11?
:ERCODE[2] / .EMPTY :ERR[1] ) ) (NOBACK :DOO[2] / .EMPTY ) ;
NTEST = ':' .ID ?12? ( '[' .NUM ?60? ']' ?14? :NDMK[2] /
.EMPTY :NDLB[1] ) /
'[' .NUM ?60? ']' ?14? :MKNODE[1] /
'↑' .SR :ARG[1] /
'$' :GOO[0] / COMM;
STEST = '.' ( .ID / .SR ) ?19? :PRIM[1] / .ID :CALL[1] /
'@' .NUM ?93? :SCODE[1] /
.SR :STST[1] /
'(' EXP ?20? ')' ?21? /
'$' STEST ?24? :ARB[1] ;
COMM = .EMPTY :SET[0] ;
OUTRUL = '[' OUTR ?27? ( OUTRUL :T[0] :AC[3] / .EMPTY ) ;
OUTR = OUTEST '=>' ?29? OUTEXP ?30? :F[0] :AC[3] ;
OUTEST = ']' :ZITEM[0] / ITEMS ']' ?78? :LITEM[1] ;
OUTEXP = SUBOUT ( '/' OUTEXP :T[0] :AC[3] / .EMPTY ) ;
SUBOUT = OUTT (REST :F[0] :AC[3] / .EMPTY ) / REST ;
REST = OUTT ( REST :OER[2] / .EMPTY ) / GEN ( REST :DOO[2] / .EMPTY ) ;
OUTT = .ID '[' ?39? ( ARGLST / .EMPTY ) :NUL[0] ) ']' ?40? :OUTCLL[2]
/ STMTS / '(' OUTEXP ?84? ')' ?41? / NSIMP :DOIT[1] ;
ARGLST = ARGMNT :ARG[1] $ ( ',' ARGMNT ?85? :ARG[1] :DOO[2] ) ;
ARGMNT = NSIMP / '#' .NUM ?86? :GENARG[1] / .SR ;
NSIMP = '*' .NUM ?67? :LCHASE[1] $ ( ':' '*' ?87? .NUM ?88? :CHASE[2] ) ;
GEN1 = ( OUT / COMM ) ( GEN1 :DOO[2] / .EMPTY ) ;
GEN = '.EMPTY' :SET[0] / GENU ;
GENU = OUT / '#' .NUM ?69? :GNLB[1] ;
OUT = '%' :OUTCR[0] / .SR :OUTSR[1] /
'|' .SR ?91? :IMED[1] / '@' .NUM ?70? :OCODE[1] ;
ITEMS = ITEM :ITNUM[1] $ ( ',' ITEM ?79? :ITNUM[1] :ITMSTR[2] ) ;
ITEM = '-' :SET[0] / .ID '(' ?80? OUTEST ?81? :RITEM[2] /
'.' ( .ID :FITEM[1] / .SR :TTST[1] ) ?82? /
.SR :TTST[1] /
NSIMP :NITEM[1] / '#' .NUM ?83? :GNITEM[1] ;
STMTS = '<' STMT ?71? $ ( ';' STMT ?71? :DOO[2] '>' ?72? :SETMFG[1] ;
STMT = <- .ID '<-' EXPR :STOR[2] / UNION ;
UNION = INTSEC ( 'OR' INTSEC :T[0] :AC[3] / .EMPTY ) ;
INTSEC = RELAT ( 'AND' RELAT :F[0] :AC[3] / .EMPTY ) ;
RELAT = .ID ( ( '=' EXPR ?90? :EQ[2] / '#' EXPR ?90? :NEG[2] /
'>' EXPR ?90? :GT[2] / '<' EXPR ?90? :LT[2] ) :MTEST[1] /
SUBARG :CALLP[2] ) ;
SUBARG = '[' ( NSIMP / EXPR ) ?74? ']' ?75? ;
EXPR = PRIMX $ ( ( .'+' / .'-' / .'&' / .'|' / .':' ) PRIME :BINOP[3] /
'↑' ( '-' .NUM :RSH[2] / .NUM :LSH[2] ) ) ;
PRIMX = <- .ID SUBARG :CALLP[2] / PRIME ;
PRIME = .ID / '-' .NUM :MINUSS[1] / .NUM ;
.END
These routines check the input for a particular item. In most cases, the item found is either placed in the String Table and a pointer to it placed on the stack or the item itself is placed on the stack. Only %TST and %CHRCK do not stack the item found. The items checked for on the input are:
This Appendix defines a compiler for an Algol-like language. The object code generated is for a pseudo-machine. The reader is urged to spend some time examining this compiler in detail.
The TREE-META program is defined in the file DEF as follows:
.META PROG
£ THIS RULE DEFINES SYNTAX OF COMPLETE PROGRAM £
PROG = 'BEGIN' :BEG[0] * DECLN * STMT *
$ ( ';' STMT ?1? * ) 'END' : ENDS[0] * ;
DECLN = 'NEW' DEC $ ( ',' DEC :DOO[2] ) ?2? ;' ?5? :DECS[1] ;
DEC = .ID :DECID[1] ;
£ DEFINE STATEMENT TYPES £
STMT = BLOCK / IFST / .ID ':=' AEXP :STORE[2] ;
BLOCK = 'BEGIN' STMT $ ( ';' STMT :DOO[2] ) 'END' ;
IFST = 'IF' LEXP 'THEN' STMT ('ELSE' STMT :IFF[3] / .EMPTY :IFF[2] ) ;
LEXP = AEXP ( '=' AEXP :EQQ / '#' AEXP :NEQ ) [2] ;
AEXP = FACTOR $ ( '+' FACTOR :ADD[2] / '-' FACTOR :SUB[2] );
FACTOR = '-' PRIME :MINUSS[1] / PRIME ;
PRIME = .ID / .NUM / '(' AEXP ')' ?3? ;
£ OUTPUT RULES £
BEG[] => % < A<-0 > ;
ENDS[] => % 'END' % ;
DECS[-] => 'GOTO #1' % *1 #1 ':' % ;
DOO[-,-] => *1 *2 ;
DECID[-] => *1 ':DATA(0)' % ;
STORE[-,-] => GET[*2] 'STORE ' *1 % ;
GET[.ID] => 'LOAD ' *1 %
[.NUM] => ' LOADI ' *1 %
[MINUSS[.NUM]] => 'LOADN ' *1:*1 %
[-] => *1 ;
ADD[-,-] => SIMP[*2] GET[*1] 'ADD' VAL[*2] % /
SIMP[*1] GET[*2] 'ADD' VAL[*1] % /
GET[*1] 'STORE T+' < OUT[A] ; A<-A+1 >%
GET[*2] 'ADD T+' < A<-A-1 ; OUT[A] > % ;
SUB[-,-] => SIMP[*2] GET[*1] 'SUB' VAL[*2] % /
SIMP[*1] GET[*2] 'NEGATE' % 'ADD' VAL[*1] % /
GET[*2] 'STORE T+' < OUT[A] ; A<-A+1 > %
GET[*1] 'SUB T+' < A<-A-1 ; OUT[A] > % ;
SIMP[.ID] => .EMPTY
[.NUM] => .EMPTY
[MINUSS[.NUM]] => .EMPTY;
VAL[.ID] => ' ' *1
[.NUM] => 'I ' *1
[MINUSS[.NUM]] => 'N ' *1:*1 ;
IFF[-,-] => BF[*1,#1] *2 #1 ':' %
[-,-,-] => BF[*1,#1] *2 'GOTO ' #2 % #1 ':' %
*3 #2 ':' % ;
BF[EQQ[-,-],#1] => SIMP[*1:*1] GET[*1:*2] 'COMPEQ' VAL[*1:*1] %
'BRANCHF ' #1 % /
SIMP[*1:*2] GET[*1:*1] 'COMPEQ' VAL[*1:*2] %
'BRANCHF ' #1 % /
SUB[*1:*1 ,*1:*2] 'COMPEQ 0' %
'BRANCHF ' #1 % ;
[NEQ[-,-],#1] => SUB[*1:*1,*1:*2] 'COMPNEI 0' %
'BRANCHF ' #1 % ;
EQQ[-,-] => .EMPTY;
NEQ[-,-] => .EMPTY;
MINUSS[-] => GET[*1] 'NEGATE' %;
.END
****
This program could be used to generate a compiler in the file COMP by:
TASK PLASYD,*CR :SUBLIB.TREEMETA, #CR1 DEF, #CP0 COMP
A typical program for compilation could be stored in file PROG as:
BEGIN NEW ALPHA,BETA,GAMMA,D,E,F ; D:=1 ; ALPHA:= -D+3 ; IF ALPHA+2 # -D THEN BEGIN BETA:=4 ; E:=7 ; F:=0 END ELSE GAMMA :=-ALPHA ; BETA:= -(BETA+4) + ALPHA END ****
This program could be compiled and the object code placed in file BIN by:
TASK PLASYD,*CR :SUBLIB.TREELIB,*CR COMP,#CR1 PROG,#CP0 BIN
The contents of the file BIN would be:
GOTO%L1 ALPHA:DATA(0) BETA:DATA(0) GAMMA:DATA(0) D:DATA(0) E:DATA(0) F:DATA(0) %L1: LOADI 1 STORE D LOAD D NEGATE ADDI 3 STORE ALPHA LOAD D NEGATE STORE T+0 LOAD ALPHA ADDI 2 SUB T+0 COMPNEI 0 BRANCHF %L2 LOADI 4 STORE BETA LOADI 7 STORE E LOADI 0 STORE F GOTO %L3 %L2: LOAD ALPHA NEGATE STORE GAMMA %L3: LOAD BETA ADDI 4 NEGATE ADD ALPHA STORE BETA END
1. TREE-META: a meta-compiler for the lnterdata Model 4 by W M Newman. Queen Mary College, London. November 1972.
2. PLASYD Manual by J D Thewlis, D C Toll and F R A Hopgood. Atlas Computer Laboratory. December 1973.
3. The 1906A TASK System by G W Robinson. Atlas Computer Laboratory. October 1973.