TREE-META

TREE-META
Original author(s) D. V. Shorre?, Donald Andrews, and Jeff Rulifson
Initial release 1968?
Development status unknown

The TREE-META (aka Tree Meta and 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[1] 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.[2]

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.[3] 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 (GET and VAL for example) and the RHS (ADD and SUB).

% This is a comment delimited by %

.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 %
STMT = .ID ':=' AEXP :STORE[2]*; 
% ':=' is a string constant. :STORE creates a STORE  node %
% [2] makes a 2 branch tree STORE [ID,AEXP] %
% * calls the STORE unparse rule. %
AEXP = FACTOR $('+' FACTOR :ADD[2] /'-' FACTOR :SUB[2]);
% here we have the recognizer for arithmetic '+' :ADD and '-':SUB %
% tree building. Again the [2] creates a 2 branch ADD or SUB tree %
% ADD[FACTOR,FACTOR] or SUB[FACTOR, FACTOR] %
FACTOR = '-' PRIME :MINUSS[1] / PRIME ;
PRIME =  .ID / .NUM / '(' AEXP ')' ?3? ;
    
% OUTPUT UNPARSE RULES %

STORE[-,-] => GET[*2] 'STORE ' *1 ;
% *1 is the left tree branch. *2 is the right %
% GET[*2] will generate code to load *2. %
% The 'STORE' string will be output %
% followed  by left branch *1 a synbol %
% What ever *2, it will be loaded by GET[*2]%

GET[.ID] => 'LOAD ' *1 /
   [.NUM] => ' LOADI ' *1 /
   [MINUSS[.NUM]] => 'LOADN ' *1:*1 /
   [-]  => *1 ;
% Here an .ID or a .NUM will simply be loaded. %
% Any thing else will be passed on for node recognition %
% The unparse rules deconstructs a tree outputing code. %

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 ;

MINUSS[-]            => GET[*1] 'NEGATE' ;

.END

See also

References

  1. ↑ 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.
  2. ↑ Bowles, K.L., 1978. A (nearly) machine independent software system for micro and mini computers. SIGMINI Newsl., 4(1), 3-7. doi:10.1145/1041256.1041257
  3. ↑ Hopgood, F R A 1974, "TREE-META Manual", Atlas Computer Laboratory.

    External links