TREE-META is a translator writing system - a program which can produce translators. The input to TREE-META is in two parts. The first part is a definition of the syntax for the source language, L, for which a translator is required. The second part defines the object code to be produced for programs written in language L. Communication between the two parts is achieved by the syntax analyser producing a tree which is processed by the code generation rules. The tree itself is quite flexible in format and is defined by the TREE-META user as he defines the syntax analyser for the language. The code generator can take note of any peculiarities in the form of the tree, if that will lead to better code being produced.
TREE-META is a simple system to use. Compilers for high level languages can be produced quickly - however, the quality of the compiler is unlikely to be high. A major use of the system is as a sophisticated symbol manipulator. The flexibility of the intermediate tree form ensures that most transformations can be produced without too much difficulty.
A translator produced by TREE-META for the language L consists of four distinct parts:
The purpose of the syntax tree is to store the relevant information contained in the source statements, and to permit the desired form of object code to be generated from this information. It is a flexible intermediate structure that forms a bridge between the source and object code.
A TREE-META program consists of two different types of statements. The first type defines the syntax of the language L and the form of the trees to be generated for particular statements of the language. The complete set of statements of this type is compiled to produce SYPROG. The second type defines the code to be generated for particular syntax trees. This set of statements is compiled to produce CDPROG.
The form of the translator for language L is:
This manual defines the syntax of the TREE-META language using an extended form of BNF. The standard meanings are adopted for:
Terminal symbols are represented by upper case letters and other symbols in the 1900 character set. Syntactic classes are represented by lower case alphabetic strings which do not include spaces. For example, a statement might be:
identifier ::= letter| identifier letter | identifier digit
This defines an identifier as an alphanumeric string of characters starting with a letter.
The only extension to standard BNF is to use the ? symbol to indicate that the preceding syntactic class is optional. For example:
abc ::= def gh? jkl
is equivalent to:
abc ::= def jkl | def gh jkl
program ::= .META identifier prefixlist rulelist .END identifier ::= letter| identifier letter | identifier digit 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 digit ::= 0|1|2|3|4|5|6|7|8|9 prefixlist ::= prefix | prefixlist prefix rulelist ::= rule | rulelist rule prefix ::= .LIST | .DELIM (integer, integer, integer) rule ::= syntaxrule | coderule | symbolrule
A TREE-META program is enclosed between the symbols .META and .END. The latter should be followed by a newline in the 1900 version. The identifier following .META defines the Syntax Rule for recognising the complete program. The program must have a Syntax Rule with this name on the left-hand side. Although TREE-META is not a space-dependent language, it is usual for TREE-META statements to be placed on separate lines.
Immediately following the heading, the user may insert one or two prefix statements which indicate whether a listing is required and define the symbols to be used for string and comment delimiters. The prefix, .LIST, will ensure that a listing of the input is produced as it is read in. It will be sent to the same output stream as the code and diagnostics produced by TREE-META. If this prefix does not appear, no listing will be produced.
Comments in TREE-META consist of any set of characters enclosed between the current comment delimiters. Initially, these are both set to the £ symbol. The head of a TREE-META program might be:
.META ALGOL .LIST £THIS IS A COMMENT£
Comments may appear anywhere in the program.
Strings in TREE-META statements are delimited by the current string quote symbol. This is initially set to the ' symbol. A typical TREE-META statement involving strings is:
ALGOL = '.BEGIN' STATEMENTS '.END'
This statement indicates that a program of syntactic class ALGOL consists of a set of statements enclosed between the strings .BEGIN and .END.
If a user finds that the current comment delimiters and string quote are inappropriate for his particular program, they may be changed by the .DELIM prefix. For example, the £ symbol may have some meaning in the language under consideration so that it will appear in the TREE-META program other than as a comment delimiter. The .DELIM prefix defines the 1900 internal code values of the symbols to replace the string quote, open comment and close comment delimiters respectively. The 1900 internal code is given in Appendix 1. For example:
.DELIM (23,20,20)
defines the standard settings. The following program has replaced the string quote by : and the comment delimiters by ! and & symbols:
.META ALGOL .LIST £RESET DELIMITERS £ .DELIM (10,17,22) ! THIS IS A COMMENT & ALGOL = :.BEGIN: STATEMENTS :.END; . . . . . . . . . .END
The TREE-META system on the 1900 generates compilers in the PLASYD language. This means that none of the PLASYD reserved words may be used as rule names in a TREE-META program. The complete set of reserved words is:
ACC AND Al A12 BASE BEGIN CARRY CASE CASEND CH CHAR CNT DATA DEFINE DO ELSE END ENTRY ER EX EXTERNAL FIX FLOAT FOR FOVERFLOW FROM FUNCTION GLABEL GLOBAL GLOBEND GO GOTO IF INCLUDE INTEGER LA LOGICAL LONG LOWEND LOWER MINUS NEG NONPLASYD NULL OBEY OF OR OVERFLOW PROCEDURE PURE PUREND REAL RETURN SA SLA SLC SLL SRA SRAV SRC SRL STEP SYN THEN TO TOPGLOBAL UNDER UNTIL WHILE XO X1 X2 X3 X4 X5 X6 X7 X01 X12 X23 X45 X56 X67 X70
For example, a statement:
BASE = ELSE NEG ;
would not be allowed in TREE-META in the 1900 implementation.