Язык описания компилятора - Compiler Description Language

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

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

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

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

Дизайн

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

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

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

Поскольку оценка правила основана на вызове более простых и простых правил, внизу должны быть некоторые примитивные правила, которые выполняют фактическую работу. Вот где очень удивительно CDL1: у него нет этих примитивов. Вы должны сами установить эти правила. Если вам нужно добавить в вашу программу, вы должны создать правило с двумя входными параметрами и одним выходным параметром, а выход устанавливается как сумма двух входов по вашему коду. Компилятор CDL использует ваш код в виде строк (существуют соглашения о том, как обращаться к входным и выходным переменным) и просто генерирует его по мере необходимости. Если вы описываете свое правило добавления с помощью сборки, вам понадобится ассемблер для преобразования вывода компилятора CDL в машинный код. Если вы описываете все примитивные правила (макросы в терминологии CDL) на Паскале или 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 почти уникальна: он может выполнять оптимизацию для разных модулей компиляции, то есть обрабатывать всю программу как одну компиляцию.

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.

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

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