ÁRBOL-META

El sistema de escritura de traductores 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 sentencias de análisis del metalenguaje se asemejan a la forma Backus-Naur aumentada con directivas de construcción de árboles integradas. Las reglas de desanálisis ^[1] incluyen extensas construcciones de escaneo de árboles y generación de código.

TREE-META fue fundamental en el desarrollo de NLS (oN-Line System) y se adaptó a muchos sistemas, incluidos UNIVAC 1108 , GE 645 , SDS 940 , ICL 1906A , PERQ y UCSD p-System . ^{[2] [3]}

Este es un ejemplo completo de un programa TREE-META extraído (y no probado) del ejemplo más completo (declaraciones, condicionales y bloques) del Apéndice 6 del manual TREE-META de ICL 1900. ^[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 árbol. 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 %

% ====================== REGLAS DE ANÁLISIS DE ENTRADA ======================= %

.METAPROG
% Se requiere un programa que defina la 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 al árbol.
% ':=' es una constante de cadena, :STORE crea un nodo STORE, %
% [2] define esto como tener dos ramas, es decir, STORE[ID,AEXP]. %
% * activa un análisis del árbol, comenzando con el último % creado
% árbol, es decir, el STORE[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 árbol. Nuevamente, [2] crea un árbol ADD o SUB de 2 ramas. %
El análisis se pospone hasta que se haya analizado una declaración completa.
% AGREGAR[FACTOR,FACTOR] o SUB[FACTOR,FACTOR] %

FACTOR = '-' PRIMO :MINUSS[1] / PRIMO ;

PRIME = .ID / .NUM / '(' AEXP ')' ?3? ;
% ?3? es una pista para mensajes de error. %
    
% ====================== REGLAS DE ANÁLISIS DE SALIDA ===================== %

TIENDA[-,-] => OBTENER[*2] 'TIENDA ' *1 ;
% *1 es la rama izquierda del árbol. *2 es la derecha %
% GET[*2] generará código para cargar *2. %
% Se generará la cadena 'STORE'
% seguido de la rama izquierda *1 un símbolo %
% Cualquiera que sea *2, se cargará mediante GET[*2]. %

GET[.ID] => 'CARGAR ' *1 /
   [.NUM] => ' CARGAR ' *1 /
   [MINUSS[.NUM]] => 'CARGAR' *1:*1 /
   [-] => *1 ;
% Aquí simplemente se cargará un .ID o un .NUM. Un nodo MINUSS %
Los % que contienen un .NUM tendrán esto utilizado, la notación *1:*1 significa %
% la primera rama (un .NUM) de la primera rama (MINUSS). %
% Cualquier otra cosa se transmitirá para el reconocimiento de nodos. %
% Las reglas de desanálisis deconstruyen un árbol generando código.

AGREGAR[-,-] => SIMP[*2] OBTENER[*1] 'AGREGAR' VAL[*2] /
             SIMP[*1] OBTENER[*2] 'AGREGAR' VAL[*1] /
             OBTENER[*1] 'ALMACENAR T+' < SALIR[A] ; A<-A+1 > /
             OBTENER[*2] 'AGREGAR T+' < A<-A-1 ; SALIR[A] > ;
Los cheurones < > indican una operación aritmética, por ejemplo, %
% genera un desplazamiento A relativo a una dirección base T. %

SUB[-,-] => SIMP[*2] OBTENER[*1] 'SUB' VAL[*2] /
             SIMP[*1] OBTENER[*2] 'NEGAR' % 'AGREGAR' VAL[*1] /
             GET[*2] 'ALMACENAR T+' < OUT[A] ; A<-A+1 > /
             OBTENER[*1] 'SUB T+' < A<-A-1 ; SALIR[A] > ;
% Un carácter de porcentaje en una regla de desanálisis indica una nueva línea.

SIMP[.ID] => .VACÍO /
    [.NUM] => .VACÍO /
    [MINUSS[.NUM]] => .VACÍO;

VAL[.ID] => ' ' *1 /
   [.NUM] => 'Yo ' *1 /
   [MENOS[.NUM]] => 'N ' *1:*1 ;

MINUSS[-] => GET[*1] 'NEGAR' ;

.FIN

• NLS (sistema informático)
• Meta II

• C. Stephen Carr, David A. Luther, Sherian Erdmann, El sistema compilador-compilador TREE-META: un sistema compilador meta para Univac 1108 y General Electric 645 ^{[ enlace muerto ‍ ]} , Informe técnico RADC-TR-69-83 de la Universidad de Utah.
• [1] ^{[ enlace muerto ‍ ]} , también [2] Informe técnico de 1968 de Englebart, English y Rulifson sobre el uso de Tree Meta en lo que ellos 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 (Working Draft): A Meta Compiler for the SDS 940, Stanford Research Institute, 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 Augmentation Research Center". Borrador preliminar, 25 de marzo de 1971.
• Alan C. Kay Tesis doctoral sobre el motor reactivo 1969 Universidad de Utah. Señala que Henri Gouraud realizó el compilador FLEX en TREE-META en el SRI (Engelbart) SDS-940.
• Informe trimestral del Laboratorio de Computación Atlas (21 de noviembre de 1975), FRA Hopgood documenta el trabajo utilizando TREE-META para crear un compilador que genera salida ensambladora FR80.
• Informe trimestral del Laboratorio de Computación Atlas (12 de octubre de 1973), documentos de CJ Pavelin (sección 4.10) TREE-META que se está trasladando al 1906A .
• TREE-META: un metacompilador para el modelo 4 de Interdata, de WM Newman. Queen Mary College, Londres, noviembre de 1972.

• 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 borrador 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 (basada en la versión de TREE-META para ICL 1900) ^{[ enlace muerto ‍ ]}
• Un renacimiento del compilador-compilador TREE-META.