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
[editovat | editovat zdroj]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
[editovat | editovat zdroj]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
Odkazy
[editovat | editovat zdroj]Poznámky
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]V tomto článku byl použit překlad textu z článku TREE-META na anglické Wikipedii.
Literatura
[editovat | editovat zdroj]- ANDREWS, Donald I.; RULIFSON, Jeff. Tree Meta (Working Draft): A Meta Compiler for the SDS 940. Menlo Park, CA: Stanford Research Institute, 1967. Dostupné online.
- BOWLES, K. L., 1978. A (nearly) machine independent software system for micro and mini computers. SIGMINI Newsleller. Roč. 4, čís. 1. Dostupné online. DOI 10.1145/1041256.1041257.
- BOWLES, K. L. A (nearly) machine independent software system for micro and mini computers. Byte Magazine. Květen 1978, roč. 3, čís. 5. Dostupné online.
- HOPGOOD, F. R. A., 1974. TREE-META Manual. [s.l.]: Atlas Computer Laboratory.
- CARR, C. Stephen; LUTHER, David A.; ERDMANN, Sherian. The TREE-META Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and General Electric 645. [s.l.]: University of Utah
- , 1968. Tech Report by Englebart, English, and Rulifson on Tree Meta's use in what they called Special-Purpose Languages (SPL's), which we now call Domain Specific Languages (DSL's), in the NLS. [s.l.]: [s.n.]. Dostupné online. Dostupné také na: [1].[nedostupný zdroj]
- ANDREWS, Donald I.; RULIFSON, Jeff, 1967. Menlo Park, CA: Stanford Research Institute. Dostupné online.
- ANDREWS, Lehtman; WHP. Tree Meta – a metacompiler for the Augmentation Research Center. Preliminary draft. [s.l.]: [s.n.], 1971-03-25.
- KAY, Alan C.. reactive Engine. , 1969. . University of Utah. . Henri Gouraud vytvořil překladač pro FLEX v TREE-META na SRI (Engelbart) SDS-940.. Dostupné online.
- HOPGOOD, F. R. A. F. R. A. Hopgood documents work using TREE-META to create a compiler generating FR80 assembler output. Atlas Computer Laboratory quarterly report. 1975-11-21.
- PAVELIN, C. J. C. J. Pavelin documents (section 4.10) TREE-META being ported to the 1906A. Atlas Computer Laboratory quarterly report. 1973-10-12.
- NEWMAN, W. M. TREE-META: a meta-compiler for the Interdata Model 4. London: Queen Mary College, listopad 1972.
Související články
[editovat | editovat zdroj]Externí odkazy
[editovat | editovat zdroj]- 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 Archivováno 4. 3. 2021 na Wayback Machine.
- Implementation of TREE-META in C (based on the version of TREE-META for the ICL 1900) [nedostupný zdroj]
- A revival of the TREE-META compiler-compiler.
- Semantic Scholar page for Donald Andrews. Archivováno 25. 6. 2018 na Wayback Machine.