TREE-META
Encyclopedia
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 Backus-Naur Form with embedded tree-building directives. Output producing rules include extensive tree-scanning and code-generation constructs.
TREE-META was the last of a line of metacompiler
s, starting with META II
, right before subsequent versions were designated classified technology by the U.S. military and government agencies.
Compiler-compiler
A compiler-compiler or compiler generator is a tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine...
system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble Backus-Naur Form with embedded tree-building directives. Output producing 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.TREE-META was the last of a line of metacompiler
Metacompiler
Metacompilers are a subset of a specialized class of compiler writing toolscalled compiler-compilers.The feature that sets a metacompiler apart from a standard compiler-compileris that a metacompiler is written in its own language and translates itself....
s, starting with META II
META II
META II is a compiler writing language first released in 1962 by D. V. Schorre. It consists of syntax equations resembling Backus normal form and into which instructions to output assembly language commands are inserted. Compilers have been written in this language for VALGOL I and VALGOL II...
, right before subsequent versions were designated classified technology by the U.S. military and government agencies.
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 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 example doesn't show the other key feature (and what distinguishes TREE-META from the other META II based languages) which is tree transforming rules.
.META PROG
$ THIS RULE DEFINES SYNTAX OF COMPLETE PROGRAM $
PROG = STMT * ;
STMT = .ID ':=' AEXP :STORE[2] ;
AEXP = FACTOR $ ( '+' FACTOR :ADD[2] / '-' FACTOR :SUB[2] );
FACTOR = '-' PRIME :MINUSS[1] / PRIME ;
PRIME = .ID / .NUM / '(' AEXP ')' ?3? ;
$ OUTPUT RULES $
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 ;
MINUSS[-] => GET[*1] 'NEGATE' %;
.END