TREE-META

Key takeaways

TREE-META belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect TREE-META to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of TREE-META from memory before moving on to harder problems.

Reference excerpt

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[2]*;

% Parse an assignment statement from the source to the tree. % % ':=' is a string constant, :STORE creates a STORE node, % % [2] defines this as having two branches i.e. STORE[ID,AEXP]. % % * triggers a unparse of the tree, Starting with the last created % % tree i.e. the STORE[ID,AEXP] which is emitted as output and % % removed from the tree. %

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. % % Unparsing is deferred until an entire statement has been parsed. % % ADD[FACTOR,FACTOR] or SUB[FACTOR,FACTOR] %

FACTOR = '-' PRIME :MINUSS[1] / 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[*2] 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[*2]. %

GET[.ID] => 'LOAD ' *1 / [.NUM] => ' LOADI ' *1 / [MINUSS[.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[*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] > ;

% Chevrons < > indicate an arithmetic operation, for example to % % generate an offset A relative to a base address T. %

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] > ;

% A percent character in an unparse rule indicates a newline. %

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 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. Englebart, D. C .; English, W. K.; Rulifson, J . F. (April 1968). Development of a Multidisplay, Time-shared Computer Facility and Computer-augmented Management-system Research (PDF). Menlo Park, California: Stanford Research Institute. Prepared for Rome Air Development Center, Griffiss Air Force Base, New York, New York. And 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. Kay The Reactive Engine Ph.D. thesis 1969 University of Utah. Notes that Henri Gouraud did the FLEX compiler in TREE-META on the SRI (Engelbart) SDS-940. Atlas Computer Laboratory quarterly report (21 November 1975), F. R. A. Hopgood documents work using TREE-META to create a compiler generating FR80 assembler output. Atlas Computer Laboratory quarterly report (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 TREE-META on GitHub, coded in C, based on ICL 1900 version TREE-META compiler-compiler revival on GitHub Manual for ICL 1900 version of TREE-META by F R A Hopgood. Wiki for collecting information about TREE-META TREE META Draft Document December, 1967 at bitsavers.org TREE META Release Document April, 1968 at bitsavers.org Study for the Development of Human Intellect Augmentation Techniques, by D. C. Engelbart

Worked examples

Example 1 — a first encounter with TREE-META

Start with the simplest possible case. Write down what TREE-META claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to TREE-META before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about TREE-META ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of TREE-META

In research: TREE-META appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses TREE-META in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: TREE-META is common in secondary-school and first-year university syllabi. It links to neighbouring topics 1960s software, Domain-specific programming languages, Parser generators, so understanding it makes those chapters shorter.
In everyday life: Look for TREE-META outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study TREE-META in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what TREE-META means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain TREE-META out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is TREE-META in simple terms?

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.

Why does TREE-META matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study TREE-META?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on TREE-META.