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, andExample
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. 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 ; % Parse an assignment statement from the source to the tree. % % ':=' is a string constant, :STORE creates a STORE node, % % defines this as having two branches i.e. STORE D,AEXP % % * triggers a unparse of the tree, Starting with the last created % % tree i.e. the STORE D,AEXPwhich is emitted as output and % % removed from the tree. % AEXP = FACTOR $('+' FACTOR :ADD / '-' FACTOR :SUB ; % Here we have the recognizer for arithmetic '+' :ADD and '-' :SUB % % tree building. Again the creates a 2-branch ADD or SUB tree. % % Unparsing is deferred until an entire statement has been parsed. % % ADD ACTOR,FACTORor SUB ACTOR,FACTOR % FACTOR = '-' PRIME :MINUSS / 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 2will 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 / INUSS[.NUM_=>_'LOADN_'_*1:*1_/ ___[-.html" ;"title="NUM.html" ;"title="INUSS[.NUM">INUSS[.NUM => 'LOADN ' *1:*1 / [-">NUM.html" ;"title="INUSS[.NUM">INUSS[.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 2GET 1'ADD' VAL 2 / SIMP 1GET 2'ADD' VAL 1/ GET 1'STORE T+' < OUT ; A<-A+1 > / GET 2'ADD T+' < A<-A-1 ; OUT > ; % Chevrons < > indicate an arithmetic operation, for example to % % generate an offset A relative to a base address T. % SUB ,- => SIMP 2GET 1'SUB' VAL 2/ SIMP 1GET 2'NEGATE' % 'ADD' VAL 1/ GET 2'STORE T+' < OUT ; A<-A+1 > / GET 1'SUB T+' < A<-A-1 ; OUT > ; % A percent character in an unparse rule indicates a newline. % SIMP ID => .EMPTY / NUM => .EMPTY / INUSS[.NUM => .EMPTY; VAL ID => ' ' *1 / NUM => 'I ' *1 / INUSS[.NUM => 'N ' *1:*1 ; MINUSS[-] => GET 1'NEGATE' ; .END
See also
* oN-Line System * META IIReferences
* C. Stephen Carr, David A. Luther, Sherian ErdmannExternal links