fbpx
Wikipedia

TREE-META

April 14, 2024

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.

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

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.
  • 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[dead link], University of Utah Technical Report RADC-TR-69-83.
  • [1][dead link], also [2] 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 edit

  • 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 bitsavers.org
  • TREE META Release Document April, 1968 at bitsavers.org
  • STUDY FOR THE DEVELOPMENT OF HUMAN INTELLECT AUGMENTATION TECHNIQUES by D. C. Engelbart
  • Implementation of TREE-META in C (based on the version of TREE-META for the ICL 1900) [dead link]
  • A revival of the TREE-META compiler-compiler.

April 14, 2024
tree, meta, tree, meta, treemeta, translator, writing, system, compiler, compiler, system, context, free, languages, originally, developed, 1960s, parsing, statements, metalanguage, resemble, augmented, backus, naur, form, with, embedded, tree, building, direc. 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 TREE METAOriginal author s Donald Andrews Jeff RulifsonInitial release1968 Contents 1 History 2 Example 3 See also 4 References 5 External linksHistory editTREE 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 editThis 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 gt 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 gt LOAD 1 NUM gt LOADI 1 MINUSS NUM gt LOADN 1 1 gt 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 gt SIMP 2 GET 1 ADD VAL 2 SIMP 1 GET 2 ADD VAL 1 GET 1 STORE T lt OUT A A lt A 1 gt GET 2 ADD T lt A lt A 1 OUT A gt Chevrons lt gt indicate an arithmetic operation for example to generate an offset A relative to a base address T SUB gt SIMP 2 GET 1 SUB VAL 2 SIMP 1 GET 2 NEGATE ADD VAL 1 GET 2 STORE T lt OUT A A lt A 1 gt GET 1 SUB T lt A lt A 1 OUT A gt A percent character in an unparse rule indicates a newline SIMP ID gt EMPTY NUM gt EMPTY MINUSS NUM gt EMPTY VAL ID gt 1 NUM gt I 1 MINUSS NUM gt N 1 1 MINUSS gt GET 1 NEGATE ENDSee also editNLS computer system META IIReferences edit 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 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 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 a href Template Cite magazine html title Template Cite magazine cite magazine a CS1 maint date and year link 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 dead link University of Utah Technical Report RADC TR 69 83 1 dead link also 2 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 editManual 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 bitsavers org TREE META Release Document April 1968 at bitsavers org STUDY FOR THE DEVELOPMENT OF HUMAN INTELLECT AUGMENTATION TECHNIQUES by D C Engelbart Implementation of TREE META in C based on the version of TREE META for the ICL 1900 dead link A revival of the TREE META compiler compiler Retrieved from https en wikipedia org w index php title TREE META amp oldid 1143069657, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.