The TREE-META (or Tree Meta, TREEMETA) Translator Writing System is a
compiler-compiler
In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.
The most common type of compiler- ...
system for
context-free languages
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
originally developed in the 1960s. Parsing statements of the metalanguage resemble
augmented Backus–Naur form In computer science, augmented Backus–Naur form (ABNF) is a metalanguage based on Backus–Naur form (BNF), but consisting of its own syntax and derivation rules. The motive principle for ABNF is to describe a formal system of a language to be use ...
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
NLS, or the "oN-Line System", was a revolutionary computer collaboration system developed in the 1960s. Designed by Douglas Engelbart and implemented by researchers at the Augmentation Research Center (ARC) at the Stanford Research Institute ...
and was ported to many systems including the Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ, and UCSD p-System
UCSD Pascal is a Pascal programming language system that runs on the UCSD p-System, a portable, highly machine-independent operating system. UCSD Pascal was first released in 1977. It was developed at the University of California, San Diego (UCS ...
.[
]
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
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
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_/
___[-.html" ;"title="NUM.html" ;"title="INUSS[.NUM">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
*oN-Line System
NLS, or the "oN-Line System", was a revolutionary computer collaboration system developed in the 1960s. Designed by Douglas Engelbart and implemented by researchers at the Augmentation Research Center (ARC) at the Stanford Research Institute ...
*META II
META II is a domain-specific programming language for writing compilers. It was created in 1963–1964 by Dewey Val Schorre at UCLA. META II uses what Schorre called syntax equations. Its operation is simply explained as:
Each ''syntax equation'' ...
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.
als
1968 Tech Report by Englebart, English, and Rulifson on Tree Meta's use in what they called Special-Purpose Languages (SPL's), which we now call Domain Specific Languages (DSL's), in the NLS.
* Donald I. Andrews, Jeff Rulifson, 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
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
* ttps://github.com/lugon/TREE-META Implementation of TREE-META in C (based on the version of TREE-META for the ICL 1900)
A revival of the TREE-META compiler-compiler.
{{DEFAULTSORT:Tree-Meta
1960s software
Parser generators
Programming languages
Domain-specific programming languages
SRI International software