Введение

Диалект языка программирования PL/I, 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 — это небольшой диалект полного языка PL/I. 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. Эта версия XCOM на XPL была затем скомпилирована на Burroughs, создав самокомпилирующийся XCOM для машин System/360. Версия Algol была затем отброшена, и все дальнейшие улучшения происходили только в версии XPL. Этот процесс называется загрузкой компилятора. Авторы XPL изобрели диаграмму «надгробия» или T-диаграмму для документирования процесса загрузки. Перенацеливание компилятора на новую машинную архитектуру – аналогичная задача, за исключением того, что необходимо изменить только модули генерации кода. XCOM – однопроходный компилятор (но с последующей корректировкой сгенерированного кода для прямых переходов, циклов и других определенных ситуаций). Он генерирует машинный код для каждого оператора по мере распознавания каждого грамматического правила в этом операторе, а не дожидаясь разбора всей процедуры или всей программы. Нет деревьев разбора или других необходимых промежуточных форм программы, а также нет оптимизаций, охватывающих весь цикл или всю процедуру. Однако XCOM выполняет оптимизацию «заглядывания». Ответ на генерацию кода для каждого грамматического правила прикреплен к этому правилу. Такой непосредственный подход может привести к неэффективному коду и неэффективному использованию машинных регистров. Эти недостатки компенсируются эффективностью реализации, а именно использованием динамических строк, упомянутых ранее: при обработке текста во время компиляции часто выполняются операции с подстроками. Они так же быстры, как присваивание целому числу; фактическая подстрока не перемещается. Вкратце, он быстр, легко преподается в кратком курсе, помещается в память небольшого размера и легко изменяется для разных языков или разных целевых машин.

Анализатор

Компилятор XCOM имеет написанный вручную лексический сканер и механически генерируемый парсер. Синтаксис входного языка компилятора (в данном случае, XPL) описывается упрощенной грамматикой БНФ. Инструмент анализа грамматики 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 использовал очень простую стратегию прямого доступа к диску: команда NOTE указывала адрес дорожки диска, а команда POINT устанавливала местоположение следующей дорожки диска как адрес, ранее возвращенный командой NOTE. Эта стратегия была выбрана для облегчения переноса XMON на другие операционные системы и избежания гораздо более сложных возможностей прямого доступа к диску, доступных в то время. Переход от примитивного использования XMON команд NOTE, POINT и операций READ/WRITE на диске – с точностью один блок на дорожку – к EXCP (т.е. запись/создание новых записей) и XDAP (т.е. чтение/обновление существующих записей) – с n блоками на дорожку, где n вычислялось во время выполнения на основе физических характеристик целевого устройства и могло быть значительно больше 1 – значительно повысил производительность приложений и снизил нагрузку на операционную систему. Хотя XMON был первоначально разработан для OS/360, он (как оригинальная реализация NOTE, POINT и READ/WRITE, так и усовершенствование EXCP и XDAP) будет работать на последующих версиях операционных систем IBM, включая OS/370, XA, OS/390 и z/OS, как правило, без изменений.

Анализ

XCOM изначально использовал устаревший метод анализа снизу вверх, известный как Mixed Strategy Precedence (MSP), разработанный командой XPL (хотя официально выпущенная версия сохраняет MSP-парсер и не включает в себя более поздние "оптимизации смотрового окна" и дополнительные типы данных, которые были разработаны за пределами первоначальной команды разработчиков). MSP является обобщением простого метода анализа по приоритетам, изобретенного Никлаусом Виртом для PL360. Простой приоритет, в свою очередь, является обобщением тривиально простых методов определения приоритета операторов, хорошо подходящих для выражений вроде A+B*(C+D)E. Таблицы MSP содержат список ожидаемых троек языковых символов. Этот список растет как куб размера грамматики и становится весьма большим для типичных полноценных языков программирования. Компиляторы, производные от XPL, было сложно разместить на миникомпьютерах 1970-х годов из-за ограниченной памяти. MSP также недостаточно мощный для обработки всех возможных грамматик. Он применим только в том случае, если разработчик языка может изменить определение языка, чтобы оно соответствовало ограничениям MSP, до того, как язык получит широкое распространение. Впоследствии Университет Торонто перешел от использования XCOM и XA к варианту метода анализа снизу вверх 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 продолжает портироваться на современные компьютеры. Порт для x86/FreeBSD был выполнен в 2000 году, порт для x86/Linux — в 2015 году, а в 2017 году был создан транслятор XPL в C.