META II es un lenguaje de programación de dominio específico para escribir compiladores . Fue creado en 1963-1964 por Dewey Val Schorre en UCLA . META II usa lo que Schorre llamó ecuaciones de sintaxis . Su funcionamiento se explica simplemente como:
Cada ecuación de sintaxis se traduce en una subrutina recursiva que prueba la cadena de entrada para una estructura de frase en particular y la elimina si se encuentra. [1]
Los programas Meta II se compilan en un lenguaje de código de bytes interpretado. Los compiladores VALGOL y SMALGOL que ilustran sus capacidades fueron escritos en el lenguaje META II, [1] [2] VALGOL es un lenguaje algebraico simple diseñado con el propósito de ilustrar META II. SMALGOL era un subconjunto bastante grande de ALGOL 60 .
Notación
META II se escribió por primera vez en META I, [3] una versión compilada a mano de META II. La historia no está clara en cuanto a si META I fue una implementación completa de META II o un subconjunto requerido del lenguaje META II requerido para compilar el compilador completo de META II.
En su documentación, META II se describe como parecido a BNF , que hoy se explica como una gramática de producción. META II es una gramática analítica. En el documento TREE-META , estos lenguajes se describieron como gramáticas reductivas.
Por ejemplo, en BNF, una expresión aritmética se puede definir como:
< expr > : = < término > | < expr > < addop > < término >
Las reglas BNF son hoy reglas de producción que describen cómo se pueden ensamblar las partes constituyentes para formar solo construcciones de lenguaje válidas. Un analizador hace lo contrario al separar las construcciones del lenguaje. META II es un lenguaje de programación de analizador funcional basado en pila que incluye una directiva de salida. En META II, el orden de las pruebas se especifica mediante la ecuación. META II, al igual que otros lenguajes de programación, desbordaría su pila al intentar la recursividad izquierda. META II utiliza un operador de secuencia $ (cero o más). La ecuación de análisis sintáctico expr escrita en META II es una expresión condicional evaluada de izquierda a derecha:
expr = término $ ( '+' término . SALIDA (' AÑADIR ') / '-' término . SALIDA (' SUB '));
Por encima de la ecuación expr se define la expresión a la derecha del '='. Evaluar de izquierda a derecha desde el término '=' es lo primero que debe probarse. Si el término devuelve error, expr falla. Si se reconoció un término con éxito, ingresamos el bucle indefinido de $ cero o más en el que primero probamos un '+' si falla, se intenta la alternativa '-' y finalmente si no se reconoció un '-', el bucle termina con expr devolviendo el éxito habiendo reconocido un solo término. Si un '+' o '-' tuvieron éxito, se llamaría el término. Y si tiene éxito, el ciclo se repetirá. La ecuación expr también se puede expresar usando agrupaciones anidadas como:
expr = término $ (( '+' / '-' ) término );
Los elementos de producción de código se omitieron para simplificar el ejemplo. Debido al conjunto limitado de caracteres de las primeras computadoras, el personaje /
se usó como la alternativa o como operador. El $
operador de bucle se usa para hacer coincidir cero o más de algo:
expr = término $ ( '+' término . SALIDA (' AÑADIR ') / '-' término . SALIDA (' SUB ') );
Lo anterior se puede expresar en inglés: Una expr es un término seguido de cero o más de (término más o término menos). Schorre describe esto como una ayuda para la eficiencia, pero a diferencia de un compilador de descenso recursivo ingenuo , también asegurará que la asociatividad de las operaciones aritméticas sea correcta:
expr = término $ ( '+' término . SALIDA (' AÑADIR ') / '-' término . SALIDA (' SUB ') ); término = factor $ ( '*' factor . OUT (' MPY ') / '/' factor . OUT (' DIV ') ); factor = ( . ID / . NUMBER / '(' expr ')') ( '^' factor . OUT (' EXP ') / . EMPTY );
Con la capacidad de expresar una secuencia con un bucle o recursividad derecha ("cola"), se puede controlar el orden de evaluación.
Las reglas de sintaxis parecen declarativas, pero en realidad se hacen imperativas por sus especificaciones semánticas.
Operación
META II genera código de ensamblaje para una máquina apiladora. Evaluar esto es como usar una calculadora RPN .
expr = término $ ( '+' término . SALIDA (' AÑADIR ') / '-' término . SALIDA (' SUB ')); término = factor $ ( '*' factor . OUT (' MPY ') / '/' factor . OUT (' DIV ')); factor = (. ID . OUT (' LD ' *) / . NUM . OUT (' LDL ' *) / '(' expr ')') ( '^' factor . OUT (' XPN ' /. EMPTY );
En el .ID y .NUM anteriores hay reconocedores de tokens integrados. * en el código .OUT, la producción hace referencia al último token reconocido. Al reconocer un número con .NUM .OUT ('LDL' *) genera la instrucción de carga literal seguida del número. Una expresión:
- (3 * a ^ 2 + 5) / b
Generará:
LDL 3 LD a LDL 2 XPN MPY LDL 5 AÑADIR LD b DIV
META II es la primera versión documentada de un metacompilador , [notas 1], ya que compila en código de máquina para una de las primeras instancias de una máquina virtual .
El documento en sí es una joya maravillosa que incluye varios ejemplos excelentes, incluido el bootstrapping de Meta II en sí mismo (¡todo esto se hizo en un 8K (bytes de seis bits) 1401!) ". - Alan Kay
El artículo original no está disponible gratuitamente, pero se reimprimió en Doctor Dobb's Journal (abril de 1980). El código fuente transcrito ha estado disponible en varias ocasiones (posiblemente por el Grupo de usuarios CP / M). El documento incluía una lista de la descripción de Meta II, que en principio podría procesarse manualmente para producir un programa interpretable en códigos de operación de máquinas virtuales; si esto se ejecutó y produjo una salida idéntica, entonces la implementación fue correcta.
META II fue básicamente una prueba de concepto. Una base desde la que trabajar.
META II no se presenta como un lenguaje estándar , sino como un punto de partida desde el cual un usuario puede desarrollar su propio " lenguaje " META . [1]
Siguieron muchos "lenguajes" META. Schorre comenzó a trabajar para System Development Corporation, donde fue miembro del proyecto Compiler for Writing and Implementing Compilers (CWIC). El lenguaje SYNTAX de CWIC se basa en META II y agrega un operador alternativo de retroceso, operadores de anticipación positivos y negativos y ecuaciones de token programadas. Las operaciones .OUT
y .LABEL
eliminaron y apilaron operaciones de transformación :
y !
agregaron. El lenguaje GENERATOR basado en LISP 2 procesó los árboles producidos por el lenguaje de análisis SYNTAX. Para generar código, se colocó una llamada a una función generadora en una ecuación SYNTAX. Estos lenguajes fueron desarrollados por miembros del subgrupo LA ACM SIGPLAN sobre compiladores dirigidos por sintaxis. Es notable cómo Schorre pensó en el lenguaje META II:
El término META "lenguaje" con META en mayúsculas se utiliza para denotar cualquier compilador-escritura lenguaje tan desarrollado. [1]
Schorre explica META II como una base a partir de la cual se pueden desarrollar otros "lenguajes" de META.
Ver también
Notas
- ^ Ignorando META I, que solo se menciona de pasada en el documento META II.
Referencias
- ^ a b c d META II UN LENGUAJE DE ESCRITURA DE COMPILADORES ORIENTADOS A SINTAXIS (Dewey Val Schorre UCLA Computing Facility 1964)
- ^ Dewey, Val Schorre (1963). "Un SMALGOL dirigido por sintaxis para el 1401". ACM Natl. Conf., Denver, Colo .
- ^ Dewey, Val Schorre (1963). META II: un lenguaje de escritura de compiladores orientado a la sintaxis (PDF) . UCLA: Centro de Computación de UCLA.