Á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 sintáctico del metalenguaje se asemejan a la forma Backus-Naur aumentada con directivas de construcción de árboles integradas. Las reglas de desanálisis sintáctico ^{[ 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 sin probar) del ejemplo más completo (declaraciones, condicionales y bloques) del Apéndice 6 del manual ICL 1900 TREE-META. ^{[ 4 ]} Dicho documento también incluye una definición de TREE-META en el Apéndice 3. Este programa no solo reconoce, sino que también genera el lenguaje ensamblador para la entrada. Demuestra una de las características clave de TREE-META: la coincidencia de patrones de árbol. Se utiliza tanto en el lado izquierdo (GET y VAL, por ejemplo) como en el lado derecho (ADD y SUB).

% Este es un comentario al estilo ALGOL delimitado por  %

% ====================== REGLAS DE ANÁLISIS DE ENTRADA ======================= % .META PROG % Se requiere un programa que defina la regla de conducción. % % Esta regla PROG es la que controla todo el programa. % PROG = $STMT ; % $ es el operador de cero o más. % % PROG (el programa) se define como cero o más STMT (instrucciones). % STMT = .ID ':=' AEXP :STORE[2]*; % Analiza una instrucción de asignación desde el origen hasta el á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, 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 las operaciones aritméticas '+' :ADD y '-' :SUB % % construcción de árbol. Nuevamente, el [2] crea un árbol ADD o SUB de 2 ramas. % % El análisis sintáctico se pospone hasta que se haya analizado la instrucción completa. % % AÑADIR[FACTOR,FACTOR] o SUB[FACTOR,FACTOR] % FACTOR = '-' PRIMO :MENOS[1] / PRIMO ; PRIME = .ID / .NUM / '(' AEXP ')' ?3? ; % ?3? es una pista para mensajes de error. % % ===================== REGLAS DE ANALIZACIÓN DE SALIDA ===================== % ALMACENAMIENTO[-,-] => OBTENER[*2] 'ALMACENAMIENTO ' *1 ; % *1 es la rama izquierda del árbol. *2 es la rama derecha % % GET[*2] generará código para cargar *2. % % Se mostrará la cadena 'STORE' % % seguido de rama izquierda *1 un símbolo % % Cualquier valor *2, se cargará mediante GET[*2]. % GET[.ID] => 'CARGAR ' *1 / [.NUM] => ' CARGAR ' *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 usado, la notación *1:*1 significa % % la primera rama (un .NUM) de la primera rama (MENOS). % % Todo lo demás se transmitirá para el reconocimiento del nodo % % Las reglas de análisis descomponen un árbol generando código. % ADD[-,-] => SIMP[*2] GET[*1] 'ADD' VAL[*2] / SIMP[*1] GET[*2] 'ADD' VAL[*1] / OBTENER[*1] 'ALMACENAR T+' < SALIDA[A] ; A<-A+1 > / OBTENER[*2] 'AÑADIR T+' < A<-A-1 ; SALIDA[A] > ; % Los símbolos de flecha < > indican una operación aritmética, por ejemplo, para % % Genera un desplazamiento A relativo a una dirección base T. % SUB[-,-] => SIMP[*2] GET[*1] 'SUB' VAL[*2] / SIMP[*1] GET[*2] 'NEGATE' % 'ADD' VAL[*1] / OBTENER[*2] 'ALMACENAR T+' < SALIDA[A] ; A<-A+1 > / OBTENER[*1] 'SUB T+' < A<-A-1 ; SALIDA[A] > ; % Un carácter de porcentaje en una regla sin analizar indica un salto de 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' ; .FIN 

• NLS (sistema informático)
• META II
• Básico/Cuatro

• C. Stephen Carr, David A. Luther, Sherian Erdmann, El sistema compilador-compilador TREE-META: un sistema meta compilador para Univac 1108 y General Electric 645 , Informe técnico de la Universidad de Utah RADC-TR-69-83.
• Englebart, D. C.; English, W. K.; Rulifson, J. F. (abril de 1968). Desarrollo de una instalación informática de tiempo compartido con múltiples pantallas e investigación de sistemas de gestión aumentados por computadora (PDF) . Menlo Park, California: Stanford Research Institute .Preparado para el Centro de Desarrollo Aéreo de Roma , Base de la Fuerza Aérea Griffiss , Nueva York, Nueva York. Y sitio web alternativo . Un informe sobre el uso de Tree Meta en lo que ellos llamaban Lenguajes de Propósito Especial (SPL), que ahora se llaman Lenguajes Específicos de Dominio (DSL), en el Sistema en Línea.
• Donald I. Andrews, JF Rulifson (1967). Tree Meta (borrador de trabajo): un compilador meta para el 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 Centro de Investigación de Aumento». Borrador preliminar, 25 de marzo de 1971.
• Alan C. Kay, The Reactive Engine, tesis doctoral de 1969, Universidad de Utah. Señala que Henri Gouraud desarrolló el compilador FLEX en TREE-META para el SRI (Engelbart) SDS-940.
• En el informe trimestral del Laboratorio de Computación Atlas (21 de noviembre de 1975), FRA Hopgood documenta el trabajo realizado utilizando TREE-META para crear un compilador que generara código ensamblador FR80.
• Informe trimestral del Laboratorio de Computación Atlas (12 de octubre de 1973), documentos de CJ Pavelin (sección 4.10) TREE-META siendo portado al 1906A .
• TREE-META: un metacompilador para el modelo Interdata 4 de WM Newman. Queen Mary College, Londres. Noviembre de 1972.

• TREE-META en GitHub , codificado en C, basado en la versión ICL 1900.
• El compilador-compilador TREE-META resurge en GitHub.
• Manual de la versión ICL 1900 de TREE-META de FRA Hopgood.
• Wiki para recopilar información sobre TREE-META
• Borrador del documento TREE META, diciembre de 1967 en bitsavers.org
• Documento de lanzamiento de TREE META, abril de 1968 en bitsavers.org
• Estudio para el desarrollo de técnicas de aumento de la inteligencia humana, por DC Engelbart