词条 | TREE-META |
释义 |
| 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. HistoryTREE-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]. ExampleThis 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
References1. ^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] [1]2. ^1 Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory. [2]}}
External links
5 : 1960s software|Parser generators|Tree programming languages|Domain-specific programming languages|SRI International software |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。