El sistema de escritura del traductor TREE-META (o Tree Meta , TREEMETA ) es un sistema compilador-compilador para lenguajes libres de contexto desarrollado originalmente en la década de 1960. Las declaraciones de análisis del metalenguaje se asemejan a la forma aumentada de Backus-Naur con directivas de construcción de árboles incrustadas. Las reglas de desemparejamiento [1] incluyen construcciones extensivas de exploración de árboles y generación de código.
Autor (es) original (es) | Donald Andrews, Jeff Rulifson |
---|---|
Versión inicial | 1968? |
Historia
TREE-META fue fundamental en el desarrollo del sistema en línea y se adaptó a muchos sistemas, incluidos Univac 1108, GE 645, SDS-940, ICL 1906A, PERQ y UCSD p-System . [2] [3]
Ejemplo
Este es un ejemplo completo de un programa TREE-META extraído (y no probado) del ejemplo más completo (declaraciones, condicionales y bloques) en el Apéndice 6 del manual ICL 1900 TREE-META. [4] Ese documento también tiene una definición de TREE-META en TREE-META en el Apéndice 3. Este programa no es solo un reconocedor, sino que también genera el lenguaje ensamblador para la entrada. Demuestra una de las características clave de TREE-META, que es la coincidencia de patrones de árboles. Se utiliza tanto en el LHS (GET y VAL por ejemplo) como en el RHS (ADD y SUB).
% Este es un comentario de estilo ALGOL delimitado por%
% ====================== INPUT PARSE REGLAS =======================%.META PROG % Se requiere un programa que defina una regla de conducción. %% Esta regla PROG es el controlador del programa completo. %PROG = $ STMT;% $ es el operador cero o más. %% PROG (el programa) se define como cero o más STMT (declaraciones). %STMT = .ID ': =' AEXP: STORE [2] *;% Analizar una declaración de asignación desde la fuente hasta el árbol. %% ': =' es una constante de cadena,: STORE crea un nodo STORE,%% [2] define esto como tener dos sucursales, es decir, TIENDA [ID, AEXP]. %% * desencadena un análisis del árbol, comenzando con el último% creado% árbol, es decir, la TIENDA [ID, AEXP] que se emite como salida y%% eliminado del árbol. %AEXP = FACTOR $ ('+' FACTOR: ADD [2] / '-' FACTOR: SUB [2]);% Aquí tenemos el reconocedor para aritmética '+': ADD y '-': SUB%% construcción de árboles. De nuevo, [2] crea un árbol ADD o SUB de 2 ramas. %% La anulación del análisis se aplaza hasta que se haya analizado una declaración completa. %% AÑADIR [FACTOR, FACTOR] o SUB [FACTOR, FACTOR]%FACTOR = '-' PRIME: MENOS [1] / PRIME;PRIME = .ID / .NUM / '(' AEXP ')'? 3? ;%? 3? es una pista para los mensajes de error. % % ===================== SALIR REGLAS NO PARAS =====================%ALMACENAR [-, -] => OBTENER [* 2] 'ALMACENAR' * 1;% * 1 es la rama del árbol de la izquierda. * 2 es el% correcto% GET [* 2] generará código para cargar * 2. %% La cadena 'STORE' se enviará%% seguido de la rama izquierda * 1 un símbolo%% Sea lo que sea * 2, GET [* 2] lo cargará. %OBTENER [.ID] => 'CARGAR' * 1 / [.NUM] => 'LOADI' * 1 / [MENOS [.NUM]] => 'CARGAR' * 1: * 1 / [-] => * 1;% Aquí simplemente se cargará un .ID o un .NUM. Un nodo MENOS%% que contiene un .NUM tendrá esto utilizado, la notación * 1: * 1 significa%% la primera rama (a .NUM) de la primera rama (MENOS). %% Cualquier otra cosa se transferirá para el reconocimiento de nodos%% Las reglas de unparse deconstruyen un código de salida de árbol. %AGREGAR [-, -] => SIMP [* 2] OBTENER [* 1] 'AGREGAR' VAL [* 2] / SIMP [* 1] OBTENER [* 2] 'AGREGAR' VAL [* 1] / OBTENER [* 1] 'ALMACENAR T +'A <-A + 1> / OBTENER [* 2] 'AÑADIR T +' FUERA [A]>;% Chevrones <> indican una operación aritmética, por ejemplo a%% genera un desplazamiento A relativo a una dirección base T.%SUB [-, -] => SIMP [* 2] GET [* 1] 'SUB' VAL [* 2] / SIMP [* 1] OBTENER [* 2] 'NEGATE'% 'AGREGAR' VAL [* 1] / OBTENER [* 2] 'ALMACENAR T +'A <-A + 1> / OBTENER [* 1] 'SUB T +' FUERA [A]>;% Un carácter de porcentaje en una regla no analizar indica una nueva línea. %SIMP [.ID] => .VACÍO / [.NUM] => .VACÍO / [MENOS [.NUM]] => .VACÍO;VAL [.ID] => '' * 1 / [.NUM] => 'Yo' * 1 / [MENOS [.NUM]] => 'N' * 1: * 1;MENOS [-] => OBTENER [* 1] 'NEGAR';.FINAL
Ver también
Referencias
- ^ Donald I. Andrews, JF Rulifson (1967). Tree Meta (Borrador de trabajo): Un metacompilador para el SDS 940 , Instituto de Investigación de Stanford, Menlo Park, CA. Colección Engelbart, Archivo de la Universidad de Stanford, M 638, Caja 16, Carpeta 3.
- ^ Bowles, KL, 1978. Un sistema de software (casi) independiente de la máquina para micro y mini computadoras. SIGMINI Newsl., 4 (1), 3–7. [1] doi : 10.1145 / 1041256.1041257
- ^ Bowles, KL, 1978. Un sistema de software (casi) independiente de la máquina para micro y mini computadoras. Revista Byte, mayo de 1978, Volumen 03 Número 05 p46, p170-173. análisis de archive.org
- ^ Hopgood, FRA 1974, "Manual de TREE-META", Atlas Computer Laboratory.
- C. Stephen Carr, David A. Luther, Sherian Erdmann, The TREE-META Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and General Electric 645 , University of Utah Technical Report RADC-TR-69-83.
- [2] , también [3] Informe técnico de 1968 de Englebart, English y Rulifson sobre el uso de Tree Meta en lo que llamaron lenguajes de propósito especial (SPL), que ahora llamamos lenguajes específicos de dominio (DSL), en el NLS.
- Donald I. Andrews, JF Rulifson (1967). Tree Meta (Borrador de trabajo): Un metacompilador para el SDS 940 , Instituto de Investigación de Stanford, Menlo Park, CA. Colección Engelbart, Archivo de la Universidad de Stanford, M 638, Caja 16, Carpeta 3.
- ANDREWS, LEHTMAN y WHP. "Tree Meta - un metacompilador para el Centro de Investigación de Aumento". Anteproyecto, 25 de marzo de 1971.
- Alan C. Kay El motor reactivo Ph.D. tesis 1969 Universidad de Utah. Señala que Henri Gouraud hizo el compilador FLEX en TREE-META en el SRI (Engelbart) SDS-940.
- Informe trimestral del Atlas Computer Laboratory (21 de noviembre de 1975), los documentos de FRA Hopgood funcionan utilizando TREE-META para crear un compilador que genera la salida del ensamblador FR80.
- Informe trimestral del Atlas Computer Laboratory (12 de octubre de 1973), documentos de CJ Pavelin (sección 4.10) TREE-META siendo portado al 1906A .
- TREE-META: un metacompilador para Interdata Model 4 de WM Newman. Queen Mary College, Londres. Noviembre de 1972.
enlaces externos
- Manual para la versión ICL 1900 de TREE-META de FRA Hopgood.
- Página de inicio para recopilar información sobre TREE-META
- Documento preliminar de TREE META de diciembre de 1967 en bitsavers.org
- Documento de lanzamiento de TREE META de abril de 1968 en bitsavers.org
- ESTUDIO PARA EL DESARROLLO DE TÉCNICAS DE AUMENTO DEL INTELECTO HUMANO por DC Engelbart
- Implementación de TREE-META en C (basado en la versión de TREE-META para ICL 1900) [ enlace muerto ]
- Un renacimiento del compilador-compilador TREE-META.
- Página de Semantic Scholar para Donald Andrews.