World Library  
Flag as Inappropriate
Email this Article

Tree Meta

Article Id: WHEBN0020619029
Reproduction Date:

Title: Tree Meta  
Author: World Heritage Encyclopedia
Language: English
Subject: META II, Scannerless parsing, Metacompiler, Compiler construction, Domain-specific language
Publisher: World Heritage Encyclopedia

Tree Meta

Original author(s) D. V. Shorre?, Donald Andrews, and Jeff Rulifson
Initial release 1968?
Development status unknown

The TREE-META (aka Tree Meta and TREEMETA) Translator Writing System is a Compiler-compiler system for context-free languages originally developed in the 1960s. Parsing statements of the metalanguage resemble Backus-Naur Form with embedded tree-building directives. Unparsing[1] rules include extensive tree-scanning and code-generation constructs.


TREE-META was instrumental in the development of the 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]


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.[3] 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 example doesn't show the other key feature (and what distinguishes TREE-META from the other META II based languages) which is tree transforming rules.


STMT = .ID ':=' AEXP :STORE[2] STORE[*1]; 
AEXP = FACTOR $('+' FACTOR :ADD[2] /'-' FACTOR :SUB[2]);
PRIME =  .ID / .NUM / '(' AEXP ')' ?3? ;

STORE[-,-] => GET[*2] 'STORE ' *1 % ;

GET[.ID] => 'LOAD ' *1 % 
   [.NUM] => ' LOADI ' *1 % 
   [MINUSS[.NUM]] => 'LOADN ' *1:*1 %
   [-]  => *1 ;

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

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

SIMP[.ID]           => .EMPTY
    [.NUM]          => .EMPTY
    [MINUSS[.NUM]]  => .EMPTY;

VAL[.ID]             => ' ' *1
   [.NUM]            => 'I ' *1
   [MINUSS[.NUM]]    => 'N ' *1:*1 ;

MINUSS[-]            => GET[*1] 'NEGATE' %;


See also


  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. [1] doi:10.1145/1041256.1041257
  3. ^ Hopgood, F R A 1974, "TREE-META Manual", Atlas Computer Laboratory.
  • 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.
  • [2], also [3] 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, 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

  • Manual for ICL 1900 version of TREE-META by F R A Hopgood.
  • Home page for collecting information about TREE-META
  • TREE META Draft Document December, 1967 at
  • TREE META Release Document April, 1968 at
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.