XPL 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 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 , [1] [2] David B. Wortman , James J. Horning y otros en la Universidad de Stanford . XPL se anunció por primera vez en la Conferencia de Computación Conjunta 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 un "generador de compiladores". Pero eso implica que se requiere poca o ninguna programación específica de idioma o destino para construir un compilador para un nuevo lenguaje o nuevo destino. Una etiqueta mejor para XPL es un sistema de escritura de traductor . Ayuda escribir un compilador con menos código de programación nuevo o modificado.
Idioma
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 mediante 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 reemplaza a Fortran , COBOL y ALGOL , y que satisface todas las necesidades internas y de los clientes. Estos ambiciosos objetivos hicieron que PL / I fuera complejo, difícil de implementar de manera eficiente y, a veces, sorprendente cuando se usaba. XPL es un pequeño dialecto del idioma 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 pila 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.
Componentes
XCOM
El compilador XPL, llamado XCOM , es un compilador de una sola pasada que utiliza un analizador basado en tablas y técnicas simples de generación de código . Existen versiones de XCOM para diferentes arquitecturas de máquinas , utilizando diferentes módulos de generación de código escrito 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 se compila a partir del código fuente XPL, pero dado que XCOM está escrito en XPL, puede compilarse a sí mismo: es un compilador autocompilable , que no depende de otros compiladores. Varios lenguajes famosos tienen compiladores autocompilables, incluidos Burroughs B5000 Algol, PL / I, C , LISP y Java . La creación de estos compiladores es un enigma del huevo y la gallina. El lenguaje es implementado primero por un compilador temporal escrito en algún otro lenguaje, o incluso por un intérprete (a menudo un intérprete para un código intermedio, como BCPL puede hacer con intcode o O-code ).
XCOM comenzó como un programa Algol que se ejecutaba en máquinas Burroughs, traduciendo el código fuente XPL al código de máquina System / 360. El equipo de XPL convirtió manualmente su código fuente de Algol en código fuente XPL. Esa versión XPL de XCOM luego se compiló en Burroughs, creando un XCOM autocompilable para máquinas System / 360. La versión de Algol se descartó y todas las mejoras adicionales ocurrieron solo en la versión XPL. A esto se le llama arrancar el compilador. Los autores de XPL inventaron el diagrama Tombstone o diagrama T para documentar el proceso de arranque.
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 de código emitido para bifurcaciones, 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 u otras formas de programa intermedias requeridas, y no hay optimizaciones de todo el ciclo 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 resultar en un código ineficiente y un uso ineficaz de los registros de la máquina. Esto se compensa con la eficiencia de la implementación, a saber, el uso de cadenas dinámicas mencionadas anteriormente: en el procesamiento de texto durante la compilación, las operaciones de subcadena se realizan con frecuencia. Son tan rápidos como una asignación a un número 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 idiomas o diferentes máquinas de destino.
ANALIZADOR
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 analizadora de gramática de XPL ANALYZER o XA convierte esto en un conjunto de tablas de datos grandes que describen todas las combinaciones legales de las reglas de sintaxis y cómo discernirlas. Este paso de generación de la tabla se vuelve a realizar solo cuando se cambia el idioma. 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 basado en tablas es generalmente más fácil de escribir que un analizador de descenso recursivo escrito 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 antes, cuando solo ha visto el extremo izquierdo de una frase.
Tiempo de ejecución
XPL incluye una biblioteca de soporte de tiempo de ejecución mínimo para asignar y recolectar valores de cadena XPL de recolección de basura. El código fuente de esta biblioteca debe incluirse en la mayoría de los programas escritos en XPL.
ESQUELETO
La última pieza del sistema de escritura del compilador XPL es un compilador de ejemplo llamado SKELETON . Esto es solo XCOM con tablas de análisis para un ejemplo de gramática de juguete en lugar de la gramática completa de XPL. Es un punto de partida para construir un compilador para algún lenguaje nuevo, si ese lenguaje difiere mucho de XPL.
XMON
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 el propio XCOM o cualquier programa que se desarrolló utilizando XCOM, y también proporciona tres auxiliares dispositivos de almacenamiento para el uso de XCOM, y a los que se accede directamente por número de bloque. El XMON publicado originalmente se optimizó para IBM 2311s . Un parámetro XMON FILE = habilitó al monitor para usar de manera eficiente otros discos con tamaños de bloque más grandes. [3] El tamaño del bloque del disco de trabajo también era una constante en tiempo de compilación en XCOM. [4]
XMON utilizó una estrategia muy simple para el acceso directo al disco. NOTA proporcionó la dirección de una pista de disco. PUNTO establece la ubicación de la siguiente pista del disco para que sea la dirección devuelta previamente por NOTA. Esta estrategia se adoptó para permitir la migración sencilla de XMON a otros sistemas operativos y para evitar las opciones mucho más complicadas de acceso directo al disco disponibles en ese momento. [5]
Conversión de XMON de su uso primitivo de operaciones de disco NOTE, POINT y READ / WRITE (con 1 bloque por pista precisamente) a EXCP (es decir, escribir / crear nuevos registros) y XDAP (es decir, leer / actualizar registros antiguos), con n bloques por pista, donde n se calculó en tiempo de ejecución a partir de las características físicas del dispositivo de destino y podría ser significativamente mayor que 1: se logró un rendimiento de la aplicación significativamente mejorado y una reducción de la sobrecarga del sistema operativo.
Aunque se desarrolló originalmente para OS / 360 , XMON (ya sea la nota original, señalar y leer aplicación / ESCRITURA, o la EXCP y XDAP mejora) se pueden ejecutar en libertad posteriormente IBM sistemas operativos, incluyendo OS / 370, XA, OS / 390 y z / SO , generalmente sin cambios.
Analizando
XCOM usó originalmente un método de tabla de análisis ascendente ahora obsoleto llamado Precedencia de estrategia mixta , inventado por el equipo de XPL (aunque la versión lanzada oficialmente retiene el analizador MSP y no incluye "optimizaciones de mirilla" lanzadas posteriormente y tipos de datos adicionales que fueron desarrollado fuera del equipo de implementación original ). MSP es una generalización del método 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 muy 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 crece a medida que aumenta el tamaño del cubo de la gramática y se vuelve bastante grande para los típicos lenguajes de programación completos. Los compiladores derivados de XPL eran difíciles de encajar en miniordenadores de la década de 1970 con memoria limitada. [nb 1] MSP tampoco es lo suficientemente poderoso para manejar todas las gramáticas probables. Es aplicable solo cuando el diseñador del lenguaje puede modificar la definición del lenguaje para que se ajuste a las restricciones de MSP, antes de que el lenguaje sea ampliamente utilizado.
La Universidad de Toronto cambió posteriormente XCOM y XA en lugar de utilizar una variante de Donald Knuth 's LR analizador método de abajo hacia arriba. [nb 2] La variante de XCOM se llama Simple LR o SLR. Maneja más gramáticas que MSP pero no tantas como LALR o LR completo (1) . Las diferencias con LR (1) se encuentran 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 analizador 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 de IBM SHARE . Otros grupos portaron 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.
Aplicaciones
XPL se ha utilizado para desarrollar una serie de compiladores para varios lenguajes y sistemas.
- Stony Brook Pascal
- HAL / S , el idioma utilizado para el programa del transbordador espacial [6]
- MALUS , un lenguaje de programación del sistema utilizado por General Motors para desarrollar su sistema de tiempo compartido de múltiples consolas
- New England Digital usó una variante de XPL, llamada "Scientific XPL" para sus computadoras de la serie ABLE, que se usa para la automatización de laboratorio, redes de computadoras y control de hardware de síntesis musical, a partir de mediados de la década de 1970
Estado actual
XPL continúa siendo portado a las computadoras actuales. Se realizó un puerto x86 / FreeBSD en 2000, [7] un puerto x86 / Linux en 2015 y un traductor XPL a C en 2017. [8] [9]
Bibliografía
- Alexander, WG y Wortman, DB "Características estáticas y dinámicas de los programas XPL". IEEE Computer noviembre de 1975; 41-46.
- Ancona, Massimo, Dodero, Gabriella y Durante, Ercole Luigi "Desarrollo de software cruzado para microprocesadores utilizando un sistema de escritura traductor" Actas de la 4ª Conferencia Internacional sobre Ingeniería de Software 1979: 399-402.
- Kamnitzer, SH "Bootstrapping XPL de IBM / 360 a UNIVAC 1100". Avisos ACM SIGPLAN mayo de 1975: 14-20.
- Karger, Paul A. "Una implementación de XPL para Multics". Tesis SB. Instituto de Tecnología de Massachusetts, 1972.
- Klumpp, Allan R. "Software de vuelo de la estación espacial: ¿Hal / S o Ada?" Computer March 1985: 20-28.
- Leach, Geoffrey y Golde, Helmut. "Bootstrapping XPL a una computadora XDS Sigma 5". Práctica y experiencia de software 3 (1973): 235-244.
- McKeeman, William M., Horning, James J. y Wortman, David B. Un generador de compiladores. Englewood Cliffs, Nueva Jersey: Prentice-Hall, 1970.
- McKeeman, WM, Horning, James J., Nelson, EC y Wortman, DB "El sistema generador de compiladores XPL". Actas de la conferencia AFIPS: Conferencia conjunta sobre informática de otoño de 1968. Washington DC: The Thompson Book Company. 1968: 617-635.
- Sitton, Gary A., Kendrick, Thomas A. y Carrick, Jr., A. Gil. "El lenguaje PL / EXUS y la máquina virtual" Actas del Simposio ACM-IEEE sobre arquitectura informática de lenguaje de alto nivel, noviembre de 1973: 124-130.
- Slimick, John "Lenguajes de implementación de sistemas actuales: la vista de un usuario" Actas del simposio SIGPLAN sobre lenguajes para la implementación de sistemas, octubre de 1971: 20-28.
- Storm, Mark W., y Polk, Jim A. "Uso de un sistema generador de compiladores basado en XPL" Actas de la 14ª Conferencia Regional Anual del Sudeste de ACM, abril de 1976: 19-26.
- Wortman, DB "Una lista de implementaciones de XPL". Avisos ACM SIGPLAN de enero de 1978: 70-74.
Ver también
- PL / M
Notas
- ^ De hecho, usando un analizador tipo LALR escrito a mano y un procedimiento de "descomposición" particularmente eficiente para las tablas de análisis sintácticas producidas, fue posible generar un analizador para todo el lenguaje XPL en unamicrocomputadora Z80 de 2 MHzque tenía solo 48 kilobytes de memoria interna ( DRAM ) y sólo 100 kilobytes de memoria externa ( disco flexible ) que se ejecuta bajo CP / M . Esta versión se completó en 1980. Posteriormente se completó la migración a MacOS (9, más tarde X).
- ^ Esta versión NO fue lanzada a la comunidad en general, por lo tanto, sigue siendo propiedad de sus autores o de sus instituciones. Sus autores han ignorado las solicitudes repetidas de una distribución SLR (1) o LALR (1) de XPL.
Referencias
- ↑ Shustek, Len (2 de agosto de 2016). "En sus propias palabras: Gary Kildall" . Gente notable . Museo de Historia de la Computación .
- ^ Kildall, Gary Arlen (2 de agosto de 2016) [1993]. Kildall, Scott ; Kildall, Kristin (eds.). "Conexiones informáticas: personas, lugares y eventos en la evolución de la industria de las computadoras personales" (PDF) (Manuscrito, parte 1). Familia Kildall. Archivado (PDF) desde el original el 24 de junio de 2020 . Consultado el 17 de noviembre de 2016 . Cite journal requiere
|journal=
( ayuda ) - ↑ A Compiler Generator, página 251
- ↑ A Compiler Generator, página 372
- ^ Un generador de compiladores Apéndice A1,7
- ^ "El desarrollo de Hal / S" . Departamento de Ciencias de la Computación, Universidad de Toronto .
- ^ Bodenstab, Dave. "Página de inicio de Dave Bodenstab" . Consultado el 6 de febrero de 2015 .
- ^ Weaver, Daniel E. (21 de noviembre de 2017). "Compilador XPL: traductor XPL a C" . SourceForge . La Jolla , CA: Slashdot Media . Consultado el 6 de diciembre de 2017 .
- ^ shoefoot (Daniel E. Weaver) (21 de noviembre de 2017). "Anuncio del lanzamiento inicial de un compilador XPL" . Grupo de noticias : comp.compilers . Usenet: [email protected] . Consultado el 6 de diciembre de 2017 .
- McKeeman, William Marshall; Horning, James J .; y Wortman, David B., A Compiler Generator (1971), ISBN 978-0-13-155077-3 . La referencia definitiva, incluido el código fuente de todos los componentes del sistema XPL.
enlaces externos
- Página de inicio de XPL de la Universidad de Toronto
- El lenguaje de programación XPL
- Una página del Generador de compiladores en Amazon.com
- Scientific XPL para computadoras de la serie ABLE de New England Digital Corporation