XPL - XPL

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

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

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

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

Язык

Язык XPL - это простой, небольшой и эффективный диалект PL / I, предназначенный в основном для написания компиляторов. Язык XPL также использовался для других целей, когда он был доступен. XPL можно легко скомпилировать для большинства современных машин с помощью простого компилятора. Внутреннее устройство компилятора может быть легко написано на XPL, а код легко читается. Язык PL / I был разработан комитетом IBM в 1964 году как всеобъемлющий язык, заменяющий Fortran , COBOL и ALGOL и отвечающий всем потребностям клиентов и внутренним потребностям. Эти амбициозные цели сделали PL / I сложным, трудным для эффективной реализации и иногда неожиданным при использовании. XPL - это небольшой диалект полного языка. В XPL есть одна дополнительная функция, которой нет в PL / I: тип данных STRING с динамической длиной. Строковые значения хранятся в отдельном пространстве кучи только для текста с автоматической сборкой устаревших значений. Большая часть того, что делает простой компилятор, - это управление потоками входного текста и выходных байтов, поэтому эта функция помогает упростить компиляторы на основе XPL.

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

XCOM

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

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

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

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

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

АНАЛИЗАТОР

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

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

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

СКЕЛЕТ

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

XMON

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

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

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

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

Парсинг

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

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

XPL имеет открытый исходный код. Версия XPL для System / 360 распространялась через организацию пользователей IBM SHARE . Другие группы перенесли XPL на многие более крупные машины 1970-х годов. Различные группы расширили XPL или использовали XPL для реализации других языков среднего размера.

Приложения

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

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

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

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

  • Александр, WG и Wortman, DB "Статические и динамические характеристики программ 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.
  • МакКиман, WM, Хорнинг, Джеймс Дж., Нельсон, EC, и Уортман, DB "Система генератора компилятора XPL". Материалы конференции AFIPS: Осенняя компьютерная конференция 1968 года. Вашингтон, округ Колумбия: Книжная компания Томпсона. 1968: 617-635.
  • Ситтон, Гэри А., Кендрик, Томас А. и Кэррик, младший, А. Гил. "Язык PL / EXUS и виртуальная машина" Труды симпозиума ACM-IEEE по компьютерной архитектуре на языках высокого уровня, ноябрь 1973: 124-130.
  • Слимик, Джон «Текущие языки реализации систем: взгляд одного пользователя» Труды симпозиума SIGPLAN по языкам для реализации системы, октябрь 1971: 20-28.
  • Сторм, Марк В., и Полк, Джим А. «Использование системы генерации компиляторов на основе XPL» Труды 14-й ежегодной Юго-Восточной региональной конференции ACM, апрель 1976: 19–26.
  • Wortman, DB "Список реализаций XPL". Уведомления ACM SIGPLAN, январь 1978: 70-74.

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

Заметки

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

  • МакКиман, Уильям Маршалл; Хорнинг, Джеймс Дж .; и Уортман, Дэвид Б., Генератор компилятора (1971), ISBN  978-0-13-155077-3 . Исчерпывающий справочник, включая исходный код всех компонентов системы XPL.

Внешние ссылки