TREE-META

TREE-META (nebo Tree Meta, TREEMETA) Translator Writing System je generátor překladačů pro bezkontextové jazyky vytvořený v 60. letech 20. století. Příkazy metajazyka pro syntaktickou analýzu se podobají rozšířené Backusově–Naurově formě s vloženými direktivami pro vytváření stromu. Pravidla pro tak zvaný unparsing^[1] obsahují množství konstruktů pro práci se stromovými strukturami a pro generování kódu.

Historie

TREE-META byl použit při vývoji systému NLS (oN-Line System) a byl portován na počítače Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ a na operační systém UCSD p-System.^[2][3]

Příklad

Následující příklad (netestovaného) TREE-META programu ukazuje jednu z klíčových vlastností systému TREE-META – vyhledávání vzorků stromů – které se používá jak na levé straně (např. GET a VAL), tak na pravé straně pravidel (ADD a SUB). Příklad je převzatý z přílohy 6 manuálu TREE-META pro ICL 1900;^[4] v příloze 3 tohoto dokumentu je definice TREE-META napsaná přímo v TREE-META. Uvedený program není pouze rozpoznávač, ale generuje i kód v jazyce symbolických adres. Řádky, které začínají a končí znakem procento jsou algolské komentáře.

% ====================== 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