请输入您要查询的百科知识:

 

词条 TREE-META
释义

  1. History

  2. Example

  3. See also

  4. References

  5. External links

{{Infobox Software
| name = TREE-META
| logo =
| screenshot =
| caption =
| author = Donald Andrews, Jeff Rulifson
| developer =
| released = 1968?
| latest release version =
| latest release date =
| programming language =
| operating system =
| platform =
| language =
| status = unknown
| genre =
| 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 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[3].

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.[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. The STORE[ID,AEXP].                                        %% 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

  • On-Line System
  • META II

References

1. ^Bowles, K. L., 1978. A (nearly) machine independent software system for micro and mini computers. Byte Magazine, May 1978, Volume 03 Number 05 p46,p170-173. [https://archive.org/stream/byte-magazine-1978-05-rescan/1978_05_BYTE_03-05_Graphics_in_Depth#page/n47/mode/1up archive.org scan]
2. ^Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory.
[1]

[2]}}

  • 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.
  •  , also   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). [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.
  • 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 bitsavers.org
  • TREE META Release Document April, 1968 at bitsavers.org
  • STUDY FOR THE DEVELOPMENT OF HUMAN INTELLECT AUGMENTATION TECHNIQUES by D. C. Engelbart
  • [https://github.com/lugon/TREE-META Implementation of TREE-META in C (based on the version of TREE-META for the ICL 1900)]
  • [https://www.semanticscholar.org/author/Donald-I.-Andrews/31588506 Semantic Scholar page for Donald Andrews.]
{{DEFAULTSORT:Tree-Meta}}

5 : 1960s software|Parser generators|Tree programming languages|Domain-specific programming languages|SRI International software

随便看

 

开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。

 

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间:2024/11/11 7:20:01