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ý 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). +more 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[2]*; % Parse an assignment statement from the source to the tree. +more % % ':=' 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. +more % % 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. +more % % 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 / [. +moreNUM] => ' 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+' / GET[*2] 'ADD T+' ; % 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+' / GET[*1] 'SUB T+' ; % 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

[url=http://www. chilton-computing. +moreorg. uk/acl/literature/manuals/tree-meta/contents. htm]Manual for ICL 1900 version of TREE-META by F R A Hopgood. [/url] * [url=http://www. ifcx. org/wiki/TREEMETA. html]Home page for collecting information about TREE-META[/url] * [url=http://bitsavers. org/pdf/sri/arc/rulifson/Tree_Meta_A_Meta_Compiler_System_For_The_SDS_940_Dec67. pdf]TREE META Draft Document December, 1967 at bitsavers. org[/url] * [url=http://bitsavers. org/pdf/sri/arc/rulifson/A_Tree_Meta_For_The_XDS_940_Appendix_D_Apr68. pdf]TREE META Release Document April, 1968 at bitsavers. org[/url] * [url=http://web. stanford. edu/dept/SUL/library/extra4/sloan/mousesite/EngelbartPapers/B2_F8_ARNAS4. html]STUDY FOR THE DEVELOPMENT OF HUMAN INTELLECT AUGMENTATION TECHNIQUES by D. C. Engelbart[/url] * [url=https://github. com/lugon/TREE-META]Implementation of TREE-META in C (based on the version of TREE-META for the ICL 1900)[/url] * [url=https://github. com/jimwhite/treemeta]A revival of the TREE-META compiler-compiler. [/url] * [url=https://www. semanticscholar. org/author/Donald-I. -Andrews/31588506]Semantic Scholar page for Donald Andrews. [/url].

Kategorie:Generátory syntaktických analyzátorů Kategorie:Programovací jazyky Kategorie:Doménově specifické jazyky