Этюды для программистов

Вполне вероятно, что проект останется незавершенным. Поэтому целесообразно наметить очередность реализации различных возможностей языка. Если порядок выбран правильно, конечный продукт станет подмножеством Мини. Начните с реализации отдельных {программных сегментов). Внутри них попытайтесь реализовать (выражения), основные типы инструкций, внутренние процедуры, декларации переменных с (базовыми типами). Пожалуй, труднее всего сгенерировать код для (инструкции цикла); оставьте это напоследок. На начальной стадии вам придется написать подпрограммы для вывода перемещаемого объектного кода; постарайтесь, чтобы ими было легко воспользоваться в дальнейшем.

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

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

Длительность исполнения.

Двоим, троим или четверым на 10 недель. Каждый участник независимо отвечает за одну тестовую программу на Мини.

Литература

Грис (Gries D.). Compiler Construction for Digital Computers. Wiley, New York, NY, 1971. [Имеется перевод: Грис Д. Конструирование компиляторов для цифровых вычислительных машин. — М.: Мир, 1975.]

Выдающаяся книга по реализации компиляторов. В ней описано все о простых компиляторах и даны указания по сложным. Правда, остались недостаточно освещенными таблично-управляемые методы разбора LR(k), но этот пробел с избытком покрывают другие упоминаемые здесь книги. Если вы уже выбрали язык для компиляции, Грис покажет, как ее провести.

Мак-Киман, Хорнинг, Уортмен (McKeeman W. M., Horning J. J. Wortman D. В.), A Compiler Generator. Prentice-Hall, Englewood Cliffs, NJ, 1970.

В книге описывается язык XPL и его использование для конструирования компиляторов, В качестве иллюстрации метода приведен компилятор с XPL, написанный на XPL. В первых изданиях использовался ныне устаревший таблично-управляемый метод разбора SMSP, однако в следующих изданиях подробно обсуждается разбор LR(k). К сожалению, опубликованный листинг не претерпел изменений в сторону LR(k). He вошел и табличный генератор Де Ремера SLR(k). Книга может служить руководством по JCPL.

Николс (Nickholls J. E.). Тhe Structure and Design of Programming Languages. Addison-Wesley, Reading, MA, 1975. Пратт (Pratt T. W.) Programming Languages Design and Implementation. Prentice Hall, Englewood Cliffs, NJ, 1975. [Имеется перевод: Пратт Т. Языки программирования: разработка и реализация. — М.: Мир, 1979.]

Обе книги нужно читать до проектирования языка и реализации компилятора. В них внимание сконцентрировано не на конкретных методах компиляции, а на изучении влияния языковых структур на программиста, поддерживаемую систему, конечного пользователя и разработчика компилятора. Авторы тщательно взвешивают все «за» и «против» различных решений при создании языка программирования.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода я компиляции. Т. 1, 2. — Пер. с англ. — М.: Мир, 1978.

28. Новый атТРАКцион, или... ПОСТРОЕНИЕ ИНТЕРПРЕТАТОРА ЯЗЫКА ТРАК

Немного найдется языков программирования, которые начинающий программист мог бы реализовать в одиночку всего за несколько недель, но Трак (TRAC) [58] — как раз такой язык. Целью разработчика Трака Калвина Муэрса было создание простого, элегантного, мощного и к тому же интерактивного языка. Он ухитрился на основе старой идеи макро сделать язык, который удовлетворяет всем этим требованиям, может использоваться также в пакетном режиме и вдобавок ко всему необычайно прост для реализации (для написания первого процессора хватило двух выходных дней). Для набора и редактирования рукописи английского оригинала книги использовался некоторый диалект языка Трак.

Язык Трак