XPL , lenguaje de programación para expertos [1], es un lenguaje de programación basado en PL/I , un compilador portátil de una sola pasada escrito en su propio lenguaje y una herramienta generadora de analizadores sintácticos para implementar fácilmente compiladores similares para otros lenguajes. XPL fue diseñado en 1967 como una forma de enseñar los principios de diseño de compiladores y como punto de partida para que los estudiantes construyan compiladores para sus propios lenguajes.
XPL fue diseñado e implementado por William M. McKeeman, [2] [3] David B. Wortman, James J. Horning y otros en la Universidad de Stanford . XPL se anunció por primera vez en la Conferencia Conjunta de Computadoras de Otoño de 1968. Los métodos y el compilador se describen en detalle en el libro de texto de 1971 A Compiler Generator .
Llamaron al trabajo combinado "generador de compiladores", pero eso implica que se requiere poca o ninguna programación específica del lenguaje o del objetivo para construir un compilador para un nuevo lenguaje o un nuevo objetivo. Una mejor etiqueta para XPL es " sistema de escritura de traductores" . Ayuda a escribir un compilador con menos código de programación nuevo o modificado.
El lenguaje XPL es un dialecto simple, pequeño y eficiente de PL/I destinado principalmente a la tarea de escribir compiladores. El lenguaje XPL también se utilizó para otros fines una vez que estuvo disponible. XPL se puede compilar fácilmente en la mayoría de las máquinas modernas con un compilador simple. Los componentes internos del compilador se pueden escribir fácilmente en XPL y el código es fácil de leer. El lenguaje PL/I fue diseñado por un comité de IBM en 1964 como un lenguaje integral que reemplazara a Fortran , COBOL y ALGOL y satisficiera todas las necesidades internas y de los clientes. Estos objetivos ambiciosos hicieron que PL/I fuera complejo, difícil de implementar de manera eficiente y, a veces, sorprendente cuando se usa. XPL es un dialecto pequeño del lenguaje completo. XPL tiene una característica adicional que no se encuentra en PL/I: un tipo de datos STRING con longitudes dinámicas. Los valores de cadena viven en un espacio de memoria de montón de solo texto separado con recolección automática de basura de valores obsoletos. Gran parte de lo que hace un compilador simple es manipular el texto de entrada y los flujos de bytes de salida, por lo que esta característica ayuda a simplificar los compiladores basados en XPL.
El compilador XPL, llamado XCOM , es un compilador de una sola pasada que utiliza un analizador controlado por tablas y técnicas de generación de código simples. Existen versiones de XCOM para diferentes arquitecturas de máquinas , que utilizan diferentes módulos de generación de código escritos a mano para esos objetivos. El objetivo original era IBM System/360 , que es un subconjunto adecuado de IBM System/370 , IBM System/390 e IBM System z .
XCOM compila a partir del código fuente XPL, pero como XCOM está escrito en XPL, puede compilarse a sí mismo: es un compilador autocompilador que no depende de otros compiladores. Varios lenguajes famosos tienen compiladores autocompiladores, incluidos Burroughs B5000 Algol, PL/I, C , LISP y Java . Crear estos compiladores es un dilema del tipo del huevo y la gallina. El lenguaje se implementa primero mediante un compilador temporal escrito en otro lenguaje, o incluso mediante un intérprete (a menudo un intérprete para un código intermedio, como BCPL puede hacer con intcode u O-code ).
XCOM comenzó como un programa Algol que se ejecutaba en máquinas Burroughs y que traducía el código fuente XPL al código de máquina System/360. El equipo de XPL convertía manualmente su código fuente Algol en código fuente XPL. Esa versión XPL de XCOM se compilaba entonces en Burroughs, creando un XCOM autocompilado para máquinas System/360. La versión Algol se descartó y todas las mejoras posteriores se realizaron únicamente en la versión XPL. Esto se denomina "bootstrapping" del compilador. Los autores de XPL inventaron el diagrama de lápida o diagrama T para documentar el proceso de "bootstrapping".
Reorientar el compilador para una nueva arquitectura de máquina es un ejercicio similar, excepto que solo es necesario cambiar los módulos de generación de código.
XCOM es un compilador de una sola pasada (pero con un proceso de corrección del código emitido para ramificaciones hacia adelante, bucles y otras situaciones definidas). Emite código de máquina para cada declaración a medida que se reconoce cada regla gramatical dentro de una declaración, en lugar de esperar hasta que haya analizado todo el procedimiento o el programa completo. No hay árboles de análisis ni otras formas intermedias de programa requeridas, ni optimizaciones a nivel de bucle o de procedimiento. Sin embargo, XCOM realiza una optimización de mirilla . La respuesta de generación de código a cada regla gramatical se adjunta a esa regla. Este enfoque inmediato puede dar como resultado un código ineficiente y un uso ineficiente de los registros de la máquina. Esto se compensa con la eficiencia de la implementación, es decir, el uso de cadenas dinámicas mencionado anteriormente: al procesar texto durante la compilación, se realizan con frecuencia operaciones de subcadena. Estas son tan rápidas como una asignación a un entero; la subcadena real no se mueve. En resumen, es rápido, fácil de enseñar en un curso corto, cabe en memorias de tamaño modesto y es fácil de cambiar para diferentes lenguajes o diferentes máquinas de destino.
El compilador XCOM tiene un escáner léxico escrito a mano y un analizador generado mecánicamente. La sintaxis del lenguaje de entrada del compilador (en este caso, XPL) se describe mediante una gramática BNF simplificada . La herramienta de análisis gramatical de XPL, ANALYZER o XA, convierte esto en un conjunto de grandes tablas de datos que describen todas las combinaciones legales de las reglas de sintaxis y cómo discernirlas. Este paso de generación de tablas se vuelve a realizar solo cuando se cambia el lenguaje. Cuando se ejecuta el compilador, esas tablas de datos son utilizadas por un pequeño algoritmo de análisis independiente del lenguaje para analizar y responder al lenguaje de entrada. Este estilo de analizador controlado por tablas es generalmente más fácil de escribir que un analizador descendente recursivo escrito completamente a mano . XCOM utiliza un método de análisis de abajo hacia arriba , en el que el compilador puede retrasar su decisión sobre qué regla de sintaxis ha encontrado hasta que haya visto el extremo más a la derecha de esa frase. Esto maneja una gama más amplia de lenguajes de programación que los métodos de arriba hacia abajo , en los que el compilador debe adivinar o comprometerse con una regla de sintaxis específica de manera temprana, cuando solo ha visto el final izquierdo de una frase.
XPL incluye una biblioteca de soporte de tiempo de ejecución mínima para asignar y recolectar elementos no utilizados de valores de cadena XPL. El código fuente de esta biblioteca debe incluirse en casi todos los programas escritos en XPL.
La última parte del sistema de escritura del compilador XPL es un compilador de ejemplo llamado SKELETON . Se trata simplemente de XCOM con tablas de análisis para una gramática de ejemplo en lugar de la gramática completa de XPL. Es un punto de partida para crear un compilador para algún lenguaje nuevo, si ese lenguaje difiere mucho de XPL.
XPL se ejecuta bajo el control de un monitor, XMON , que es la única parte específica del sistema operativo de este sistema, y que actúa como un "cargador" para XCOM en sí mismo o cualquier programa que se haya desarrollado utilizando XCOM, y también proporciona tres dispositivos de almacenamiento auxiliares para el uso de XCOM, y a los que se accede directamente por número de bloque. El XMON publicado originalmente fue optimizado para IBM 2311s . Un parámetro XMON FILE= permitió que el monitor usara de manera eficiente otros discos con tamaños de bloque más grandes. [4] El tamaño de bloque del disco de trabajo también era una constante de tiempo de compilación en XCOM. [5]
XMON utilizó una estrategia muy simple para el acceso directo al disco. NOTE proporcionaba la dirección de una pista del disco. POINT establecía que la ubicación de la siguiente pista del disco sería la dirección devuelta previamente por NOTE. Esta estrategia se adoptó para permitir una fácil portabilidad de XMON a otros sistemas operativos y para evitar las opciones de acceso directo al disco mucho más complicadas disponibles en ese momento. [6]
La conversión de XMON de su uso primitivo de operaciones de disco NOTE, POINT y READ/WRITE (con exactamente 1 bloque por pista) a EXCP (es decir, escribir/crear nuevos registros) y XDAP (es decir, leer/actualizar registros antiguos) (con n bloques por pista, donde n se calculaba en tiempo de ejecución a partir de las características físicas del dispositivo de destino y podía ser significativamente mayor que 1) logró un rendimiento de la aplicación significativamente mejorado y una disminución de la sobrecarga del sistema operativo.
Aunque originalmente fue desarrollado para OS/360 , XMON (ya sea la implementación original de NOTE, POINT y READ/WRITE; o la mejora de EXCP y XDAP) se ejecutará en sistemas operativos IBM lanzados posteriormente, incluidos OS/370, XA, OS/390 y z/OS , generalmente sin ningún cambio.
XCOM originalmente usaba un método de tabla de análisis ascendente ahora obsoleto llamado Mixed Strategy Precedence , inventado por el equipo XPL (aunque la versión lanzada oficialmente conserva el analizador MSP y no incluye "optimizaciones de mirilla" lanzadas posteriormente y tipos de datos adicionales que fueron desarrollados fuera del equipo de implementación original ). MSP es una generalización del método de analizador de precedencia simple inventado por Niklaus Wirth para PL360 . La precedencia simple es en sí misma una generalización de los métodos de precedencia de operadores trivialmente simples que funcionan bien para expresiones como A+B*(C+D)-E. Las tablas MSP incluyen una lista de tripletes esperados de símbolos de lenguaje. Esta lista se hace más grande como el cubo del tamaño de la gramática y se vuelve bastante grande para los lenguajes de programación completos típicos. Los compiladores derivados de XPL eran difíciles de adaptar a las minicomputadoras de la década de 1970 con memorias limitadas. [nb 1] MSP tampoco es lo suficientemente potente como para manejar todas las gramáticas probables. Solo es aplicable cuando el diseñador del lenguaje puede modificar la definición del lenguaje para adaptarla a las restricciones de MSP, antes de que el lenguaje sea ampliamente utilizado.
La Universidad de Toronto posteriormente cambió XCOM y XA para utilizar en su lugar una variante del método ascendente del analizador LR de Donald Knuth . [nb 2] La variante de XCOM se llama Simple LR o SLR. Maneja más gramáticas que MSP pero no tantas gramáticas como LALR o LR(1) completo . Las diferencias con LR(1) están principalmente en los algoritmos del generador de tablas, no en el método del analizador en tiempo de compilación. XCOM y XA son anteriores a la disponibilidad generalizada de Unix y su herramienta generadora de analizadores yacc . XA y yacc tienen propósitos similares.
XPL es de código abierto. La versión System/360 de XPL se distribuyó a través de la organización de usuarios IBM SHARE . Otros grupos trasladaron XPL a muchas de las máquinas más grandes de la década de 1970. Varios grupos ampliaron XPL o utilizaron XPL para implementar otros lenguajes de tamaño moderado.
XPL se ha utilizado para desarrollar numerosos compiladores para distintos lenguajes y sistemas.
XPL sigue siendo adaptado a las computadoras actuales. En 2000 se realizó un puerto x86/ FreeBSD , [8] en 2015 un puerto x86/ Linux y en 2017 un traductor de XPL a C. [9] [10]