Edge Rewrite
restyle Source code View original
// HTMLRewriter · presentation

This page was redesigned at the edge.

Cloudflare fetched the original article and streamed it through HTMLRewriter to apply an entirely new visual system without rebuilding the source page.

Jump to content

TREE-META

Edit links
From Wikipedia, the free encyclopedia
(Redirected from Tree Meta)
TREE-META
Original authorsDonald Andrews,
Jeff Rulifson
Release1968; 58 years ago (1968)
PlatformUNIVAC 1108, GE 645, SDS 940, ICL 1906A, PERQ, UCSD p-System
Typecompiler-compiler

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

[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.
  4. ↑ Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=TREE-META&oldid=1303178916"