TREE-META

Quality 0.50 · 0 views · Updated 2 months ago

title: "TREE-META" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["1960s-software", "parser-generators", "programming-languages", "domain-specific-programming-languages", "sri-international-software", "articles-with-example-code"] topic_path: "technology/programming-languages" source: "https://en.wikipedia.org/wiki/TREE-META" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::data[format=table title="Infobox software"]

FieldValue
nameTREE-META
authorDonald Andrews,
Jeff Rulifson
released
platformUNIVAC 1108, GE 645, SDS 940, ICL 1906A, PERQ, UCSD p-System
genrecompiler-compiler
::

| name = TREE-META | logo = | screenshot = | caption = | author = Donald Andrews, Jeff Rulifson | developer = | released = | latest release version = | latest release date = | programming language = | operating system = | platform = UNIVAC 1108, GE 645, SDS 940, ICL 1906A, PERQ, UCSD p-System | language = | genre = compiler-compiler | license = | website =

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+' / GET[*2] 'ADD T+' ;

% 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+' / GET[*1] 'SUB T+' ;

% 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

References

References

  1. Donald I. Andrews, [[Jeff Rulifson. J. F. Rulifson]] (1967). [https://archive.org/details/bitsavers_sriarcrulimpilerSystemForTheSDS940Dec67_3967472 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. Bowles, K. L.. (May 1978). "UCSD Pascal: A (nearly) machine independent software system for micro and mini computers".
  4. Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

1960s-softwareparser-generatorsprogramming-languagesdomain-specific-programming-languagessri-international-softwarearticles-with-example-code