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ý 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.
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; 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*; % 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[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 / '-' 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[FACTOR,FACTOR] or SUB[FACTOR,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[*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
Odkazy
Poznámky
Reference
Literatura
Související články On-Line System META II
Externí odkazy 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) A revival of the TREE-META compiler-compiler. Semantic Scholar page for Donald Andrews.
Kategorie:Generátory syntaktických analyzátorů Kategorie:Programovací jazyky Kategorie:Doménově specifické jazyky