META II - Enciclopedia

META II es un lenguaje de programación específico del dominio para escribir compiladores. Fue creado en 1963-1964 por Dewey Val Schorre en la Universidad de California, Los Ángeles (UCLA). META II utiliza lo que Schorre llamó ecuaciones de sintaxis. Su operación 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 particular, y la elimina si se encuentra.

Los programas de 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, VALGOL es un lenguaje algebraico simple diseñado con el propósito de ilustrar META II. SMALGOL fue un subconjunto bastante grande de ALGOL 60.


Notación
META II se escribió por primera vez en META I, una versión compilada a mano de META II. La historia es incierta en cuanto a si META I era una implementación completa de META II o un subconjunto requerido del lenguaje META II necesario para compilar el compilador completo de META II.
En su documentación, META II se describe como similar a la forma de Backus-Naur (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 describen como gramáticas reductoras.
Por ejemplo, en BNF, una expresión aritmética puede definirse como:

Las reglas BNF son hoy reglas de producción que describen cómo se pueden ensamblar partes constituyentes para formar solo constructos válidos del lenguaje. Un analizador sintáctico hace lo contrario, desmontando los constructos del lenguaje. META II es un lenguaje de programación de analizador sintáctico basado en pilas que incluye directiva de salida. En META II, el orden de prueba se especifica por la ecuación. Como otros lenguajes de programación, META II se sobrecarga su pila al intentar recursión izquierda. META II utiliza un operador de secuencia $ (cero o más). La ecuación de análisis de expr escrita en META II es una expresión condicional evaluada de izquierda a derecha:

La ecuación de expr se define por la expresión a la derecha del '='. Evaluando de izquierda a derecha desde el '=', el término es lo primero que debe probarse. Si el término devuelve fracaso, expr fracasa. Si tiene éxito, se reconoce un término y luego entramos en un bucle indeterminado $ cero o más donde primero probamos por un '+'; si ese fallo, se intenta la alternativa '-'; y finalmente, si no se reconoce un '-', el bucle termina con expr devolviendo éxito después de reconocer un solo término. Si un '+' o '-' tiene éxito, se llama al término. Y si tiene éxito, el bucle se repetirá. La ecuación de expr también se puede expresar utilizando agrupación anidada como:

Se han omitido los elementos de producción del código para simplificar el ejemplo. Debido al conjunto de caracteres limitado de las computadoras tempranas, el carácter / se utilizó como operador alternativo, o, operador. El operador de bucle $, se utiliza para coincidir cero o más de algo:

Se puede expresar lo anterior en inglés: Un expr es un término seguido por cero o más de (suma término o resta término). Schorre describe esto como una ayuda para la eficiencia, pero a diferencia de un compilador de recursión descendente simplista, también asegurará que la asociatividad de las operaciones aritméticas sea correcta:

Con la capacidad de expresar una secuencia con un bucle o recursión 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 ensamblador para una máquina de pila. Evaluarlo es como usar una calculadora de notación polaca inversa (RPN).

En el código .OUT, .ID y .NUM son reconocedores de tokens integrados. * en la producción de código .OUT 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á:

META II es la primera versión documentada de un metacompilador, ya que compila a código maquina para uno de los primeros ejemplos de una máquina virtual.

El propio documento es una joya maravillosa que incluye una serie de excelentes ejemplos, incluyendo el autoarranque de Meta II en sí mismo (todo esto se hizo en un 1401 de 8K (byte de seis bits)!) – Alan Kay
El documento original no está disponible gratuitamente, pero fue reimpreso en el Journal de Dr. Dobb, abril de 1980. El código fuente transcrito ha sido puesto a disposición en diversas ocasiones (posiblemente por el Grupo de Usuarios CP/M). El documento incluía una lista de la descripción de Meta II, lo que en principio podría procesarse manualmente para generar un programa interpretable en códigos de operaciones de máquina virtual; si esto funcionaba y producía la salida idéntica, entonces la implementación era 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.
Muchos "lenguajes" META siguieron. Schorre fue a trabajar para la System Development Corporation donde fue miembro del proyecto Compiler for Writing and Implementing Compilers (CWIC). El lenguaje SYNTAX de CWIC se construyó sobre META II, añadiendo un operador de alternativa de retroceso, operadores de anticipación positiva y negativa y ecuaciones de token programadas. Se eliminaron las operaciones .OUT y .LABEL y se añadieron operaciones de transformación de pila :<nodo> y !<número>. El lenguaje GENERATOR basado en LISP 2 procesaba los árboles producidos por el lenguaje de análisis de sintaxis SYNTAX. Para generar código, se colocó una llamada a una función generadora en una ecuación de SYNTAX. Estos lenguajes fueron desarrollados por miembros del subgrupo de ACM SIGPLAN de LA sobre Compiladores Dirigidos por Sintaxis. Schorre veía al lenguaje META II de manera general:

El término "lenguaje META" con META en mayúsculas se utiliza para denotar cualquier lenguaje de escritura de compiladores desarrollado de esta manera.
Schorre explica META II como una base desde la que se pueden desarrollar otros "lenguajes" META.


Ver también
OMeta
TREE-META


Notas


Referencias


Enlaces externos
ACM - Artículo sobre META II
Tutorial: Metacompiladores Parte 1
Metacompilador Meta II