Язык описания компилятора

Язык описания компилятора (CDL) — это язык программирования, основанный на аффиксных грамматиках . Это очень похоже на в форме Бэкуса – Наура нотацию (БНФ). Он был разработан для разработки компиляторов . Он очень ограничен в своих возможностях и потоке управления, и это сделано намеренно. Преимущества этих ограничений двояки.

С одной стороны, они делают возможным сложный анализ данных и потоков управления, используемый оптимизаторами CDL2, что приводит к чрезвычайно эффективному коду. Другое преимущество заключается в том, что они способствуют очень подробному соглашению об именах. Это, в свою очередь, приводит к появлению программ, которые в значительной степени самодокументируются .

Язык немного похож на Пролог (это неудивительно, поскольку оба языка возникли примерно в одно и то же время из работ над аффиксными грамматиками ). Однако, в отличие от Пролога, поток управления в CDL детерминированно основан на успехе/неуспехе, т.е. никакие другие альтернативы не опробуются в случае успеха текущей. Эта идея также используется при анализе грамматик выражений .

CDL3 — третья версия языка CDL, существенно отличающаяся от двух предыдущих версий.

Дизайн

Первоначальная версия, разработанная Корнелисом Х.А. Костером в Университете Неймегена и появившаяся в 1971 году, имела довольно необычную концепцию: у нее не было ядра. Типичный исходный код языка программирования преобразуется в машинные инструкции или в стандартные последовательности этих инструкций. Они представляют собой ядро, самые основные абстракции , которые поддерживает данный язык. Такими примитивами могут быть сложение чисел, копирование переменных друг в друга и так далее. У CDL1 такого ядра нет. Ответственность программиста заключается в том, чтобы предоставить примитивные операции в форме, которую затем можно будет превратить в машинные инструкции с помощью ассемблера или компилятора традиционного языка. В самом языке CDL1 нет концепции примитивов, нет концепции типов данных, кроме машинного слова (абстрактная единица хранения - не обязательно настоящее машинное слово как таковое). Правила вычисления очень похожи на описания синтаксиса форм Бэкуса – Наура ; на самом деле, написать синтаксический анализатор для языка, описанного в BNF, в CDL1 довольно просто.

По сути, язык состоит из правил. Правило может либо работать успешно, либо не выполняться. Правило состоит из альтернатив, которые являются последовательностями вызовов других правил. Правило считается успешным, если любая из его альтернатив успешна; они пробуются последовательно. Альтернатива успешна, если все ее вызовы правил успешны. Язык предоставляет операторам возможность создавать циклы вычислений без рекурсии (хотя в CDL2 это не является строго необходимым, поскольку оптимизатор достигает того же эффекта) и некоторые упрощения для повышения эффективности рекурсивных вычислений, но основная концепция такая же, как указано выше. Помимо очевидного применения в бесконтекстном анализе грамматики, CDL также хорошо подходит для управления приложениями, поскольку многие управляющие приложения по сути представляют собой глубоко вложенные правила «если-то».

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

Поскольку оценка правил основана на вызове все более и более простых правил, внизу должны быть некоторые примитивные правила, которые выполняют реальную работу. Вот тут CDL1 очень удивляет: у него нет этих примитивов. Вы должны сами установить эти правила. Если вам нужно сложение в вашей программе, вам нужно создать правило с двумя входными параметрами и одним выходным параметром, а выходной параметр будет установлен как сумма двух входных параметров в вашем коде. Компилятор CDL использует ваш код в виде строк (существуют соглашения о том, как обращаться к входным и выходным переменным) и просто генерирует его по мере необходимости. Если вы описываете правило добавления с помощью ассемблера, вам понадобится ассемблер для перевода вывода компилятора CDL в машинный код. Если вы описываете все примитивные правила (макросы в терминологии CDL) на языке Pascal или C, то вам понадобится компилятор Pascal или C, который будет запускаться после компилятора CDL. Отсутствие основных примитивов может быть очень болезненным, когда вам нужно написать фрагмент кода, даже для самой простой операции машинной инструкции. Однако, с другой стороны, это дает вам большую гибкость в реализации эзотерических, абстрактных примитивов, действующих на экзотические цели. абстрактные объекты («машинное слово» в CDL больше похоже на «единицу хранения данных, без ссылки на тип хранящихся там данных»). Кроме того, в крупных проектах использовались тщательно созданные библиотеки примитивов. Затем они были реплицированы для каждой целевой архитектуры и ОС, что позволило создать высокоэффективный код для всех.

Чтобы получить представление о языке, вот небольшой фрагмент кода, адаптированный из руководства CDL2:

ACTION quicksort + >from + >to -p -q:
  less+from+to, split+from+to+p+q,
    quicksort+from+q, quicksort+p+to;
  +.

ACTION split + >i + >j + p> + q> -m:
  make+p+i, make+q+j, add+i+j+m, halve+m,
    (again: move up+j+p+m, move down+i+q+m,
       (less+p+q, swap item+p+q, incr+p, decr+q, *again;
        less+p+m, swap item+p+m, incr+p;
        less+m+q, swap item+q+m, decr+q;
        +)).

FUNCTION move up + >j + >p> + >m:
  less+j+p;
  smaller item+m+p;
  incr+p, *.

FUNCTION move down + >i + >q> + >m:
  less+q+j;
  smaller item+q+m;
  decr+q, *.

TEST less+>a+>b:=a"<"b.
FUNCTION make+a>+>b:=a"="b.
FUNCTION add+>a+>b+sum>:=sum"="a"+"b.
FUNCTION halve+>a>:=a"/=2".
FUNCTION incr+>a>:=a"++".
FUNCTION decr+>a>:=a"--".

TEST smaller item+>i+>j:="items["i"]<items["j"]".
ACTION swap items+>i+>j-t:=t"=items["i"];items["i"]=items["j"];items["j"]="t.

Примитивные операции здесь определены в терминах Java (или C). Это не полная программа; массива Java мы должны определить элементы в другом месте.

CDL2, появившийся в 1976 году, сохранил принципы CDL1, но сделал язык пригодным для крупных проектов. Он представил модули, ввел возможность изменения данных только в случае успеха и несколько расширил возможности языка. Оптимизаторы в компиляторе CDL2 и особенно в Лаборатории CDL2 (IDE для CDL2) были мирового уровня, и не только для своего времени. Одна особенность оптимизатора CDL2 Laboratory почти уникальна: он может выполнять оптимизацию для всех модулей компиляции, т. е. рассматривать всю программу как одну компиляцию.

CDL3 — более новый язык. Он отказался от открытой функции предыдущих версий CDL и предоставляет примитивы для базовой арифметики и доступа к памяти. Чрезвычайно пуританский синтаксис более ранних версий CDL (количество ключевых слов и символов, состоящих из одной цифры) также был смягчен. Некоторые основные понятия теперь выражаются в синтаксисе, а не в явной семантике. Кроме того, в язык были введены типы данных.

Использовать

Коммерческий mbp Cobol (компилятор Cobol для ПК), а также система MProlog (промышленная реализация Prolog, работающая на многочисленных архитектурах (мэйнфрейм IBM, VAX, PDP-11, Intel 8086 и т. д.) и ОС (DOS/OS/CMS/BS2000, VMS/Unix, DOS/Windows/OS2)). Последнее, в частности, является свидетельством портативности CDL2.

Хотя большинство программ, написанных с использованием CDL, были компиляторами, существует по крайней мере одно коммерческое приложение с графическим интерфейсом, которое было разработано и поддерживается на CDL. Это приложение представляло собой приложение для получения стоматологических изображений, которое теперь принадлежит DEXIS. В CDL когда-то также была разработана система управления стоматологическим кабинетом.

Программное обеспечение для шахматного компьютера Mephisto III было написано на CDL2.

Дальнейшее чтение

• Книга о языке CDL1/CDL2.
• Описание для CDL3
• Арпад Бедо: Методы создания программ; Экономико-правовое издательство, 1979. ISBN   963-220-760-2