TREE-META


The TREE-META Translator Writing System is a compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble augmented Backus–Naur form with embedded tree-building directives. Unparsing rules include extensive tree-scanning and code-generation constructs.

History

TREE-META was instrumental in the development of the On-Line System and was ported to many systems including the Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ, and UCSD p-System.

Example

This is a complete example of a TREE-META program extracted from the more complete example in Appendix 6 of the ICL 1900 TREE-META manual. That document also has a definition of TREE-META in TREE-META in Appendix 3. This program is not just a recognizer, but also outputs the assembly language for the input. It demonstrates one of the key features of TREE-META, which is tree pattern matching. It is used on both the LHS and the RHS.
% This is an ALGOL-style comment delimited by %

% 
= INPUT PARSE RULES 
 %
.META PROG 
% A program defining driving rule is required. %
% This PROG rule is the driver of the complete program. %
PROG = $STMT ;
% $ is the zero or more operator.  %
% PROG is defined as zero or more STMT. %
STMT =.ID ':=' AEXP :STORE*;
% Parse an assignment statement from the source to the tree. % 
% ':=' is a string constant, :STORE creates a STORE node, %
% defines this as having two branches i.e. STORE. %
% * triggers a unparse of the tree, Starting with the last created %
% tree i.e. the STORE which is emitted as output and %
% removed from the tree.  %
AEXP = FACTOR $;
% Here we have the recognizer for arithmetic '+' :ADD and '-' :SUB %
% tree building. Again the creates a 2-branch ADD or SUB tree. %
% Unparsing is deferred until an entire statement has been parsed. %
% ADD or SUB %
FACTOR = '-' PRIME :MINUSS / PRIME ;
PRIME = .ID /.NUM / '' ?3? ;
% ?3? is a hint for error messages. %
 
% 
 OUTPUT UNPARSE RULES 
 %
STORE => GET 'STORE ' *1 ;
% *1 is the left tree branch. *2 is the right %
% GET will generate code to load *2. %
% The 'STORE' string will be output %
% followed by left branch *1 a symbol %
% Whatever *2, it will be loaded by GET. %
GET => 'LOAD ' *1 /
 => ' LOADI ' *1 /
 => *1 ;
% Here an.ID or a.NUM will simply be loaded. A MINUSS node %
% containing a.NUM will have this used, the notation *1:*1 means %
% the first branch of the first branch. %
% Anything else will be passed on for node recognition %
% The unparse rules deconstruct a tree outputing code. %
ADD => SIMP GET 'ADD' VAL / 
 SIMP GET 'ADD' VAL / 
 GET 'STORE T+' < OUT ; A<-A+1 > /
 GET 'ADD T+' < A<-A-1 ; OUT > ;
% Chevrons < > indicate an arithmetic operation, for example to %
% generate an offset A relative to a base address T. %
SUB => SIMP GET 'SUB' VAL / 
 SIMP GET 'NEGATE' % 'ADD' VAL /
 GET 'STORE T+' < OUT ; A<-A+1 > / 
 GET 'SUB T+' < A<-A-1 ; OUT > ;
% A percent character in an unparse rule indicates a newline. %
SIMP =>.EMPTY /
 =>.EMPTY /
 => ' ' *1 /
 => 'I ' *1 /
 => GET 'NEGATE' ;
.END