META II es un lenguaje de programación específico para escribir compiladores . Fue creado en 1963-1964 por Dewey Val Schorre en la UCLA . META II utiliza lo que Schorre llamó ecuaciones sintácticas . Su funcionamiento se explica de forma sencilla como:
Cada ecuación de sintaxis se traduce en una subrutina recursiva que prueba la cadena de entrada en busca de una estructura de frase particular y la elimina si la 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 se escribieron 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 .
META II se escribió por primera vez en META I, [3] una versión compilada a mano de META II. No está claro si META I fue una implementación completa de META II o un subconjunto requerido del lenguaje META II para compilar el compilador META II completo.
En su documentación, se describe a META II como similar 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 describían como gramáticas reductivas.
Por ejemplo, en BNF, una expresión aritmética puede definirse 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 sintáctico hace lo opuesto, desarmando las construcciones de lenguaje. META II es un lenguaje de programación de analizador sintáctico funcional basado en pila que incluye una directiva de salida. En META II, el orden de prueba se especifica mediante la ecuación. META II, como otros lenguajes de programación, desbordaría su pila al intentar la recursión hacia la izquierda. META II usa 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 que se evalúa de izquierda a derecha:
expr = término $ ( '+' término . OUT ( ' ADD ') / '-' término . OUT ( ' SUB '));La ecuación expr anterior se define con la expresión a la derecha del '='. Al evaluar de izquierda a derecha a partir del '=', el término es lo primero que se debe probar. Si el término devuelve un error, expr falla. Si se reconoce un término con éxito, ingresamos al bucle indefinido de $ cero o más donde primero probamos si hay un '+', si eso falla, se intenta la alternativa '-' y, finalmente, si no se reconoce un '-', el bucle termina con expr devolviendo éxito al haber reconocido un solo término. Si un '+' o '-' tienen éxito, se llama a term. Y si tiene éxito, el bucle se repite. La ecuación expr también se puede expresar utilizando agrupamiento anidado como:
expr = término $ (( '+' / '-' ) término );Los elementos de producción de código se omitieron para simplificar el ejemplo. Debido al conjunto de caracteres limitado de las primeras computadoras, /se utilizó el carácter como operador alternativo, o,. El $operador de bucle , se utiliza para hacer coincidir cero o más de algo:
expr = término $ ( '+' término . OUT ( ' ADD ') / '-' término . OUT ( ' SUB ') );Lo anterior se puede expresar en inglés: una expresión es un término seguido de cero o más de (término positivo o término negativo). Schorre describe esto como una ayuda para la eficiencia, pero a diferencia de un compilador de descenso recursivo ingenuo , también garantizará que la asociatividad de las operaciones aritméticas sea correcta:
expr = término $ ( '+' término . OUT ( ' ADD ') / '-' término . OUT ( ' SUB ') ); término = factor $ ( '*' factor . OUT ( ' MPY ') / '/' factor . OUT ( ' DIV ') ); factor = ( . ID / . NÚMERO / '(' expr ')') ( '^' factor . OUT ( ' EXP ') / . VACÍO );Con la capacidad de expresar una secuencia con un bucle o recursión de ("cola") hacia la derecha, se puede controlar el orden de evaluación.
Las reglas de sintaxis parecen declarativas, pero en realidad se vuelven imperativas por sus especificaciones semánticas.
META II genera código ensamblador para una máquina de pila. Evaluarlo es como usar una calculadora RPN .
expr = término $ ( '+' término . OUT ( ' ADD ') / '-' término . OUT ( ' SUB ')); término = factor $ ( '*' factor . OUT ( ' MPY ') / '/' factor . OUT ( ' DIV ')); factor = (. ID . OUT ( ' LD ' *) / . NUM . OUT ( ' LDL ' *) / '(' expr ')') ( '^' factor . OUT ( ' XPN '/. EMPTY );En el ejemplo anterior, .ID y .NUM son 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 literal de carga seguida del número. Una expresión:
generará:
LDL 3 LD a LDL 2 XPN MPY LDL 5 AGREGAR LD b DIV META II es la primera versión documentada de un metacompilador , [notas 1] ya que compila en código máquina para una de las primeras instancias de una máquina virtual .
"El artículo en sí es una joya maravillosa que incluye una serie de ejemplos excelentes, incluido el arranque de Meta II en sí mismo (¡todo esto se hizo en un 1401 de 8K (bytes de seis bits)!)."—Alan Kay
El artículo original no está disponible de forma gratuita, pero se reimprimió en Doctor Dobb's Journal (abril de 1980). El código fuente transcrito se ha puesto a disposición en varias ocasiones (posiblemente por el grupo de usuarios de CP/M). El artículo incluía una lista de la descripción de Meta II; en principio, esto podría procesarse manualmente para producir un programa interpretable en códigos de operación de máquina virtual; si se ejecutaba y producía un resultado idéntico, entonces la implementación era correcta.
META II fue básicamente una prueba de concepto, una base desde la cual 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]
A continuación surgieron muchos "lenguajes" META. Schorre empezó a trabajar para System Development Corporation , donde fue miembro del proyecto Compiler for Writing and Implementing Compilers (CWIC). El lenguaje SYNTAX de CWIC se basó en META II, añadiendo un operador alternativo de retroceso, operadores de anticipación positivos y negativos y ecuaciones de token programadas. Se eliminaron las .OUToperaciones y y se añadieron .LABELlas operaciones de transformación de pila . El lenguaje GENERATOR, basado en LISP 2, procesaba los árboles producidos por el lenguaje de análisis SYNTAX. Para generar código, se colocaba una llamada a una función generadora en una ecuación SYNTAX. Estos lenguajes fueron desarrollados por miembros del subgrupo SIGPLAN de LA ACM sobre compiladores dirigidos por sintaxis. Es notable cómo Schorre pensó en el lenguaje META II::<node>!<number>
El término META "lenguaje", con META en mayúsculas, se utiliza para designar cualquier lenguaje de escritura de compiladores desarrollado de esa manera. [1]
Schorre explica META II como una base a partir de la cual se pueden desarrollar otros "lenguajes" META.