XPL

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

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

Совместную работу они назвали «генератором компилятора». Но это означает, что для создания компилятора для нового языка или новой цели требуется мало или совсем не требуется программирование, специфичное для языка или цели. Лучшее название для 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-code ).

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= позволил монитору эффективно использовать другие диски с блоками большего размера. ^[4] Размер блока рабочего диска также был константой времени компиляции вХКОМ. ^[5]

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

Преобразование XMON из примитивного использования дисковых операций ПРИМЕЧАНИЕ, POINT и ЧТЕНИЕ/ЗАПИСЬ — ровно с одним блоком на дорожку — в EXCP (т. е. запись/создание новых записей) и XDAP (т. е. чтение/обновление старых записей) — с n блоками на дорожку, где n вычислялось во время выполнения на основе физических характеристик целевого устройства и могло быть значительно больше 1, что позволило значительно повысить производительность приложений и снизить нагрузку на операционную систему.

Хотя изначально XMON был разработан для OS/360 , XMON (либо исходная реализация ПРИМЕЧАНИЕ, 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-х годов с ограниченной памятью. ^{[номер 1]} MSP также недостаточно мощный, чтобы обрабатывать все возможные грамматики. Это применимо только в том случае, если разработчик языка может настроить определение языка в соответствии с ограничениями MSP до того, как язык получит широкое распространение.

Университет Торонто впоследствии изменил XCOM и XA, чтобы вместо этого использовать вариант Кнута . Дональда парсера LR восходящего метода ^{[номер 2]} Вариант 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 использовался для разработки ряда компиляторов для различных языков и систем.

Стоуни Брук Паскаль
HAL/S — язык, используемый в программе «Спейс Шаттл». ^[7]
MALUS — язык системного программирования , используемый General Motors для разработки системы разделения времени с несколькими консолями.
New England Digital использовала вариант XPL, названный «Scientific XPL», для своих компьютеров серии ABLE, используемых для автоматизации лабораторий, компьютерных сетей и управления оборудованием для синтеза музыки, начиная с середины 1970-х годов.

Текущий статус

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

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

Александр, В.Г. и Вортман, Д.Б. «Статические и динамические характеристики программ XPL». Компьютер IEEE, ноябрь 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.

См. также

ПЛ/М

Примечания

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

Ссылки

^ Слимик, Джон (октябрь 1971 г.). «Текущие языки реализации систем: взгляд одного пользователя» (PDF) . Уведомления ACM SIGPLAN . 6 (9): 20–28. дои : 10.1145/942596.807056 .
^ Шустек, Лен (2 августа 2016 г.). «Своими словами: Гэри Килдалл» . Замечательные люди . Музей истории компьютеров .
^ Килдалл, Гэри Арлен (2 августа 2016 г.) [1993]. Килдалл, Скотт ; Килдалл, Кристин (ред.). «Компьютерные соединения: люди, места и события в эволюции индустрии персональных компьютеров» (PDF) (Рукопись, часть 1). Семья Килдалл. Архивировано (PDF) из оригинала 24 июня 2020 г. Проверено 17 ноября 2016 г.
^ Генератор компилятора, стр. 251.
^ Генератор компилятора, страница 372.
^ Генератор компилятора, Приложение A1,7.
^ «Развитие Hal/S» . Кафедра компьютерных наук Университета Торонто .
^ Боденстаб, Дэйв. «Домашняя страница Дэйва Боденстаба» . Проверено 6 февраля 2015 г.
^ Уивер, Дэниел Э. (21 ноября 2017 г.). «Компилятор XPL: транслятор XPL в C» . СоурсФордж . Ла-Хойя , Калифорния: Slashdot Media . Проверено 6 декабря 2017 г.
^ ботинок (Дэниел Э. Уивер) (21 ноября 2017 г.). «Анонсируем первый выпуск компилятора XPL» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 6 декабря 2017 г.

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

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

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

[8] Эта версия НЕ была выпущена для широкого круга пользователей, поэтому она остается собственностью ее авторов или их учреждений. Неоднократные запросы на распространение XPL SLR(1) или LALR(1) были проигнорированы его авторами.

[1] Слимик, Джон (октябрь 1971 г.). «Текущие языки реализации систем: взгляд одного пользователя» (PDF) . Уведомления ACM SIGPLAN . 6 (9): 20–28. дои : 10.1145/942596.807056 .

[Shustek_2016-2] Шустек, Лен (2 августа 2016 г.). «Своими словами: Гэри Килдалл» . Замечательные люди . Музей истории компьютеров .

[Kildall_1993-3] Килдалл, Гэри Арлен (2 августа 2016 г.) [1993]. Килдалл, Скотт ; Килдалл, Кристин (ред.). «Компьютерные соединения: люди, места и события в эволюции индустрии персональных компьютеров» (PDF) (Рукопись, часть 1). Семья Килдалл. Архивировано (PDF) из оригинала 24 июня 2020 г. Проверено 17 ноября 2016 г.

[4] Генератор компилятора, стр. 251.

[5] Генератор компилятора, страница 372.

[6] Генератор компилятора, Приложение A1,7.

[9] «Развитие Hal/S» . Кафедра компьютерных наук Университета Торонто .

[10] Боденстаб, Дэйв. «Домашняя страница Дэйва Боденстаба» . Проверено 6 февраля 2015 г.

[11] Уивер, Дэниел Э. (21 ноября 2017 г.). «Компилятор XPL: транслятор XPL в C» . СоурсФордж . Ла-Хойя , Калифорния: Slashdot Media . Проверено 6 декабря 2017 г.

[12] ботинок (Дэниел Э. Уивер) (21 ноября 2017 г.). «Анонсируем первый выпуск компилятора XPL» . Группа новостей : comp.compilers . Usenet: [электронная почта защищена] . Проверено 6 декабря 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[номер 1]

[номер 2]

[7]

[8]

[9]

[10]