TREE-META

From Wikipedia the free encyclopedia

TREE-META
Original author(s)Donald Andrews, Jeff Rulifson
Initial release1968?

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[1] rules include extensive tree-scanning and code-generation constructs.

History[edit]

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.[2][3]

Example[edit]

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.[4] 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 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[edit]

References[edit]

  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. ^ Bowles, K. L. (May 1978). "UCSD Pascal: A (nearly) machine independent software system for micro and mini computers". Byte. Vol. 3, no. 5. pp. 46, 170–173 – via Internet Archive.{{cite magazine}}: CS1 maint: date and year (link)
  4. ^ Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory.

External links[edit]

Retrieved from "https://en.wikipedia.org/w/index.php?title=TREE-META&oldid=1143069657"