XPL - XPL

Эта статья о диалекте языка программирования PL / I. Значение термина и другие варианты использования см. XPL (значения).

XPL это язык программирования на основе PL / I, портативный однопроходный компилятор написано на своем родном языке, и генератор парсеров инструмент для простой реализации подобных компиляторов для других языков. XPL был разработан в 1967 году как способ обучения принципам проектирования компиляторов и как отправная точка для студентов при создании компиляторов для своих языков.

XPL был разработан и реализован Уильям М. МакКиман[1][2] , Дэвид Б. Вортман , Джеймс Дж. Хорнинг и другие на Стэндфордский Университет. XPL был впервые анонсирован в 1968 г. Осенняя совместная компьютерная конференция. Подробно методы и компилятор описаны в учебнике 1971 г. Генератор компилятора.

Совместную работу они назвали «компилятором-генератором». Но это означает, что для создания компилятора для нового языка или новой цели требуется небольшое программирование, ориентированное на конкретный язык или цель, или оно вовсе не требуется. Лучшая этикетка для XPL - это переводчик система письма. Это помогает писать компилятор с меньшим количеством нового или измененного программного кода.

Язык

Язык XPL - это простой, небольшой, эффективный диалект PL / I, предназначенный в основном для написания компиляторов. После того, как он стал доступен, язык XPL также использовался для других целей. XPL может быть легко скомпилирован для большинства современных машин с помощью простого компилятора. Внутреннее устройство компилятора может быть легко написано на XPL, а код легко читается. Язык PL / I был разработан IBM комитета в 1964 году как всеобъемлющий язык, заменяющий Фортран, КОБОЛ, и АЛГОЛ, и удовлетворение всех потребностей клиентов и внутренних потребностей. Эти амбициозные цели сделали PL / I сложным, трудным для эффективной реализации и иногда неожиданным при использовании. XPL - это небольшой диалект полного языка. В XPL есть одна дополнительная функция, которой нет в PL / I: НИТЬ тип данных с динамической длиной. Строковые значения находятся в отдельном текстовом формате куча объем памяти с автоматическим вывоз мусора устаревших значений. Большая часть того, что делает простой компилятор, манипулирует потоками входного текста и выходных байтов, поэтому эта функция помогает упростить компиляторы на основе XPL.

Составные части

XCOM

Компилятор XPL, называемый XCOM, это однопроходный компилятор, использующий управляемый таблицей парсер и просто генерация кода техники. Версии XCOM существуют для разных машинная архитектура, используя для этих целей различные модули генерации кода, написанные вручную. Первоначальная цель была IBM System / 360, который является собственным подмножеством IBM System / 370, IBM System / 390 и IBM System z.

XCOM компилируется из исходного кода XPL, но поскольку сам XCOM написан на XPL, он может компилироваться сам - это самокомпилирующийся компилятор, не зависящий от других компиляторов. Некоторые известные языки имеют самокомпилируемые компиляторы, в том числе Берроуз B5000 Алгол, PL / I, C, LISP, и Ява. Создание таких компиляторов - это головоломка, состоящая из курицы и яйца. Язык сначала реализуется временным компилятором, написанным на каком-то другом языке, или даже интерпретатором (часто интерпретатором для промежуточного кода, как BCPL может сделать с intcode или же О-код ).

XCOM начинался как программа Algol, работающая на машинах Burroughs, переводящая исходный код XPL в машинный код System / 360. Команда XPL вручную превратила исходный код Algol в исходный код XPL. Затем эта версия XCOM для XPL была скомпилирована на Burroughs, создав самокомпилированный XCOM для машин System / 360. Затем версия Algol была выброшена, и все дальнейшие улучшения произошли только в версии XPL. Это называется самонастройка компилятор. Авторы XPL изобрели схема надгробия или T-диаграмма для документирования процесса начальной загрузки.

Ретаргетинг компилятор для новой машинной архитектуры представляет собой аналогичное упражнение, за исключением того, что необходимо изменить только модули генерации кода.

XCOM - это однопроходный компилятор (но с процессом исправления испускаемого кода для прямых переходов, циклов и других определенных ситуаций). Он излучает Машинный код для каждого оператора, поскольку распознается каждое правило грамматики внутри оператора, а не ждать, пока он проанализирует всю процедуру или всю программу. Нет деревьев синтаксического анализа или других необходимых промежуточных программных форм, а также нет оптимизаций на уровне цикла или процедуры. Однако XCOM выполняет оптимизация глазка. Ответ генерации кода на каждое правило грамматики прикрепляется к этому правилу. Такой немедленный подход может привести к неэффективному коду и неэффективному использованию машинных регистров. Это компенсируется эффективностью реализации, а именно использованием динамических строк, упомянутых ранее: при обработке текста во время компиляции часто выполняются операции с подстроками. Это так же быстро, как присвоение целому числу; фактическая подстрока не перемещается. Короче говоря, это быстро и легко преподавать в кратком курсе, умещается в памяти небольшого размера и легко менять для разных языков или разных целевых машин.

АНАЛИЗАТОР

Компилятор XCOM имеет рукописный лексический сканер и механически сгенерированный синтаксический анализатор. Синтаксис языка ввода компилятора (в данном случае XPL) описывается упрощенным Грамматика BNF. Инструмент анализатора грамматики XPL АНАЛИЗАТОР или же XA превращает это в набор больших таблиц данных, описывающих все допустимые комбинации синтаксических правил и способы их распознавания. Этот шаг генерации таблицы повторяется только при изменении языка. Когда компилятор запускается, эти таблицы данных используются небольшим, независимым от языка алгоритмом синтаксического анализа для анализа и ответа на язык ввода. Этот стиль синтаксического анализатора, управляемого таблицей, как правило, легче написать, чем полностью написанный вручную рекурсивный спуск парсер. XCOM использует восходящий анализ , в котором компилятор может отложить решение о том, с каким правилом синтаксиса он столкнулся, пока не увидит крайний правый конец этой фразы. Это обрабатывает более широкий спектр языков программирования, чем сверху вниз методы, в которых компилятор должен угадать или зафиксировать конкретное правило синтаксиса раньше, когда он видел только левый конец фразы.

Время выполнения

XPL включает минимальный библиотека поддержки времени выполнения для выделения строковых значений XPL и сбора мусора. Исходный код этой библиотеки должен быть включен почти во все программы, написанные на XPL.

СКЕЛЕТ

Последней частью системы записи компилятора XPL является пример компилятора с именем СКЕЛЕТ. Это просто XCOM с таблицами синтаксического анализа для примера игрушечной грамматики вместо полной грамматики XPL. Это отправная точка для создания компилятора для нового языка, если этот язык сильно отличается от XPL.

XMON

XPL работает под управлением монитора, XMON, который является единственной частью этой системы, зависящей от операционной системы, и которая действует как «загрузчик» для самого XCOM или любых программ, которые были разработаны с использованием XCOM, а также предоставляет три вспомогательных запоминающих устройства для использования XCOM, к которым осуществляется прямой доступ по номеру блока. Первоначально опубликованный XMON был оптимизирован для IBM 2311s. Параметр XMON FILE = позволяет монитору эффективно использовать другие диски с большими размерами блоков. [3] Размер блока рабочего диска также был константой времени компиляции в XCOM. [4]

XMON использовал очень простую стратегию прямого доступа к диску. ПРИМЕЧАНИЕ предоставляет адрес дисковой дорожки. POINT устанавливает место следующего чтения / записи на диск как адрес, возвращаемый NOTE. Эта стратегия была принята, чтобы упростить перенос XMON на другие ОС и избежать гораздо более сложных опций прямого доступа к диску, доступных в то время. [5]

Преобразование XMON из его примитивного использования дисковых операций NOTE, POINT и READ / WRITE - с ровно 1 блоком на дорожку - в EXCP (т.е. писать / создавать новые записи) и XDAP (т. е. чтение / обновление старых записей) - с n блоками на дорожку, где n вычисляется во время выполнения на основе физических характеристик целевого устройства и может быть значительно больше 1 - позволяет значительно повысить производительность приложения и снизить накладные расходы системы.

Хотя изначально был разработан для OS / 360, XMON (либо исходная реализация NOTE, POINT и READ / WRITE; либо расширение EXCP и XDAP) будет работать на выпущенных впоследствии операционных системах IBM, включая OS / 370, XA, OS / 390 и z / OS, вообще без изменений.

Парсинг

Первоначально XCOM использовал устаревший метод восходящей таблицы синтаксического анализа под названием Приоритет смешанной стратегии, изобретенный командой XPL (хотя официально выпущенная версия сохраняет парсер MSP и не включать в себя выпущенные позже "оптимизации на глазок" и дополнительные типы данных, которые были разработаны вне оригинал группа реализации.) MSP - это обобщение простой парсер приоритета метод, изобретенный Никлаус Вирт за PL360. Простой приоритет сам по себе является обобщением тривиально простых приоритет оператора методы, которые хорошо работают с выражениями типа A + B * (C + D) -E. Таблицы MSP включают список ожидаемых троек языковых символов. Этот список увеличивается по мере роста куба грамматики и становится довольно большим для типичных полноценных языков программирования. Компиляторы на основе XPL было трудно уместить на миникомпьютерах 1970-х годов с ограниченной памятью.[nb 1] MSP также недостаточно мощен, чтобы обрабатывать все возможные грамматики. Это применимо только тогда, когда разработчик языка может настроить определение языка в соответствии с ограничениями MSP до того, как язык будет широко использоваться.

В Университет Торонто впоследствии изменили XCOM и XA, чтобы вместо этого использовать вариант Дональд Кнут с Парсер LR восходящий метод.[nb 2] Вариант XCOM называется Простой LR или SLR. Он обрабатывает больше грамматик, чем MSP, но не так много грамматик, как LALR или полный LR (1). Отличия от LR (1) в основном заключаются в алгоритмах генератора таблиц, а не в методе синтаксического анализатора времени компиляции. XCOM и XA предшествовали широкому распространению Unix и его yacc инструмент генератора парсеров. XA и yacc имеют схожие цели.

XPL имеет открытый исходный код. Версия XPL для System / 360 распространялась через IBM ПОДЕЛИТЬСЯ организация пользователей. Другие группы перенесли XPL на многие более крупные машины 1970-х годов. Различные группы расширили XPL или использовали XPL для реализации других языков среднего размера.

Приложения

XPL использовался для разработки ряда компиляторов для различных языков и систем.

Текущее состояние

XPL продолжает переноситься на современные компьютеры. X86 /FreeBSD порт был сделан в 2000 году,[7] x86 /Linux порт в 2015 году и переводчик XPL в C в 2017 году.[8][9]

Библиография

  • Александр, В. Г. и Вортман, Д. Б. "Статические и динамические характеристики программ XPL". IEEE Computer, ноябрь 1975 г .; 41-46.
  • Анкона, Массимо, Додеро, Габриэлла и Дуранте, Эрколе Луиджи «Перекрестная разработка программного обеспечения для микропроцессоров с использованием системы письменного переводчика» Труды 4-й Международной конференции по разработке программного обеспечения 1979: 399-402.
  • Камнитцер, С. Х. «Начальная загрузка XPL с IBM / 360 на UNIVAC 1100». Уведомления ACM SIGPLAN, май 1975: 14-20.
  • Каргер, Пол А. "Реализация XPL для Multics". Дипломная работа. Массачусетский технологический институт, 1972 год.
  • Клумпп, Аллан Р. "Программное обеспечение для полета космической станции: Hal / S или Ada?" Компьютер, март 1985: 20-28.
  • Лич, Джеффри и Голд, Гельмут. «Загрузка XPL на компьютер XDS Sigma 5». Программная практика и опыт 3 (1973): 235-244.
  • МакКиман, Уильям М., Хорнинг, Джеймс Дж. И Вортман, Дэвид Б. Генератор компилятора. Энглвудские скалы, Нью-Джерси: Прентис-Холл, 1970.
  • МакКиман, У. М., Хорнинг, Джеймс Дж., Нельсон, Э. К. и Уортман, Д. Б. "Генераторная система компилятора XPL". Материалы конференции AFIPS: Осенняя компьютерная конференция 1968 года. Вашингтон, округ Колумбия: Книжная компания Томпсона. 1968: 617-635.
  • Ситтон, Гэри А., Кендрик, Томас А. и Керрик, младший, А. Гил. "Язык PL / EXUS и виртуальная машина" Труды симпозиума ACM-IEEE по компьютерной архитектуре на языках высокого уровня, ноябрь 1973: 124-130.
  • Слимик, Джон «Текущие языки реализации систем: взгляд одного пользователя» Труды симпозиума SIGPLAN по языкам для реализации системы, октябрь 1971: 20-28.
  • Сторм, Марк В., и Полк, Джим А. «Использование системы генерации компилятора на основе XPL» Труды 14-й ежегодной Юго-Восточной региональной конференции ACM, апрель 1976: 19–26.
  • Вортман, Д. Б. «Список реализаций XPL». Уведомления ACM SIGPLAN, январь 1978: 70-74.

Смотрите также

Примечания

  1. ^ Действительно, используя написанный вручную LALR-подобный анализатор и особенно эффективную процедуру «декомпозиции» для созданных таблиц синтаксического анализа, можно было сгенерировать синтаксический анализатор для всего языка XPL на частоте 2 МГц. Z80 микрокомпьютер, у которого было всего 48 килобайт внутренней памяти (DRAM ) и всего 100 килобайт внешней памяти (дискета ) работает под CP / M. Эта версия была завершена в 1980 году. Впоследствии был завершен перенос на MacOS (9, позже X).
  2. ^ Эта версия НЕ была выпущена для широкого сообщества, поэтому она остается собственностью ее авторов или их организаций. Неоднократные запросы на SLR (1) или LALR (1) дистрибутив XPL были проигнорированы его авторами.

Рекомендации

  1. ^ Шустек, Лен (02.08.2016). «Его собственными словами: Гэри Килдалл». Замечательные люди. Музей истории компьютеров.
  2. ^ Килдалл, Гэри Арлен (2016-08-02) [1993]. Килдалл, Скотт; Килдалл, Кристин (ред.). «Компьютерные связи: люди, места и события в развитии индустрии персональных компьютеров» (PDF) (Рукопись, часть 1). Семья Килдалл. В архиве (PDF) из оригинала на 2020-06-24. Получено 2016-11-17. Цитировать журнал требует | журнал = (помощь)
  3. ^ Генератор компилятора стр. 251
  4. ^ Генератор компилятора, страница 372
  5. ^ Приложение-генератор компилятора A1,7
  6. ^ «Развитие Hal / S». Департамент компьютерных наук, Университет Торонто.
  7. ^ Боденштаб, Дэйв. "Домашняя страница Дэйва Боденстаба". Получено 6 февраля, 2015.
  8. ^ Уивер, Дэниел Э. (21 ноября 2017 г.). "Компилятор XPL: переводчик XPL в C". SourceForge. La Jolla, Калифорния: Slashdot Средства массовой информации. Получено 6 декабря, 2017.
  9. ^ shoefoot (Дэниел Уивер) (21 ноября 2017 г.). «Объявление о первом выпуске компилятора XPL». Группа новостей: comp.compilers. Usenet:  [email protected]. Получено 6 декабря, 2017.
  • МакКиман, Уильям Маршалл; Хорнинг, Джеймс Дж .; и Уортман, Дэвид Б., Генератор компилятора (1971), ISBN  978-0-13-155077-3. Полный справочник, включая исходный код всех компонентов системы XPL.

внешняя ссылка