TREE-META

The TREE-META (or Tree Meta, TREEMETA) 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 NLS (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 (and untested) from the more complete (declarations, conditionals, and blocks) 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 only 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 (GET and VAL for example) and the RHS (ADD and SUB).

% 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 (the program) is defined as zero or more STMT (statements). %
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 D,AEXP     %
% * triggers a unparse of the tree, Starting with the last created %
% tree i.e. the STORE D,AEXPwhich is emitted as output and      %
% removed from the tree.                                           %
AEXP = FACTOR $('+' FACTOR :ADD / '-' FACTOR :SUB ;
% 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 ACTOR,FACTORor SUB ACTOR,FACTOR                        %
FACTOR = '-' PRIME :MINUSS / PRIME ;
PRIME =  .ID / .NUM / '(' AEXP ')' ?3? ;
% ?3? is a hint for error messages.                                %
% 
= OUTPUT UNPARSE RULES 
= %
STORE ,-=> GET 2'STORE ' *1 ;
% *1 is the left tree branch. *2 is the right                      %
% GET 2will 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 2                       %
GET ID=> 'LOAD ' *1 /
    NUM=> ' LOADI ' *1 /
    INUSS[.NUM => 'LOADN ' *1:*1 /
   [-">NUM.html" ;"title="INUSS[.NUM">INUSS[.NUM => 'LOADN ' *1:*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 (a .NUM) of the first branch (MINUSS).          %
% Anything else will be passed on for node recognition             %
% The unparse rules deconstruct a tree outputing code.             %
ADD ,-=>  SIMP 2GET 1'ADD' VAL 2 / 
             SIMP 1GET 2'ADD' VAL 1/ 
             GET 1'STORE T+' < OUT ; A<-A+1 > /
             GET 2'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 2GET 1'SUB' VAL 2/ 
             SIMP 1GET 2'NEGATE' % 'ADD' VAL 1/
             GET 2'STORE T+' < OUT ; A<-A+1 > / 
             GET 1'SUB T+' < A<-A-1 ; OUT > ;
% A percent character in an unparse rule indicates a newline.      %
SIMP ID          => .EMPTY /
     NUM         => .EMPTY /
     INUSS[.NUM  => .EMPTY;
VAL ID            => ' ' *1 /
    NUM           => 'I ' *1 /
    INUSS[.NUM    => 'N ' *1:*1 ;
MINUSS[-]            => GET 1'NEGATE' ;
.END

See also

*NLS (computer system)
*META II
* Basic/Four

References

* C. Stephen Carr, David A. Luther, Sherian Erdmann
The TREE-META Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and General Electric 645
University of Utah Technical Report RADC-TR-69-83.
* Prepared for Rome Air Development Center, Griffiss Air Force Base, New York, New York. An
alternate website
A report on Tree Meta's use in what they called Special-Purpose Languages (SPL), which are now called Domain Specific Languages (DSL), in the oN-Line System
* Donald I. Andrews, J. F. Rulifson (1967)
Tree Meta (Working Draft): A Meta Compiler for the SDS 940
Stanford Research Institute, Menlo Park, CA. Engelbart Collection, Stanford University Archive, M 638, Box 16, Folder 3.
* Andrews, Lehtman, and WHP. "Tree Meta – a metacompiler for the Augmentation Research Center". Preliminary draft, 25 March 1971.
* Alan C. Ka

Ph.D. thesis 1969 University of Utah. Notes that Henri Gouraud did the FLEX compiler in TREE-META on the SRI (Engelbart) SDS-940.


(21 November 1975), F. R. A. Hopgood documents work using TREE-META to create a compiler generating FR80 assembler output.


(12 October 1973), C. J. Pavelin documents (section 4.10) TREE-META being ported to the 1906A.
* TREE-META: a meta-compiler for the Interdata Model 4 by W. M. Newman. Queen Mary College, London. November 1972.

External links

* , coded in C, based on ICL 1900 version
*

Manual for ICL 1900 version of TREE-META by F R A Hopgood.



TREE META Draft Document December, 1967 at bitsavers.org

TREE META Release Document April, 1968 at bitsavers.org



{{DEFAULTSORT:Tree-Meta
1960s software
Parser generators
Programming languages
Domain-specific programming languages
SRI International software

Articles with example code