Как известно, алгоритмические языки бесполезны без надежных и эффективнтх трансляторов. Преимущественное распространение языка Алгол 60 в нашей стране в 60-70-е годы было связано, прежде всего, со своевременной разработкой трансляторов для основных типов отечественных ЭВМ.

К сожалению, активная роль разработчиков компиляторов во внедрении новых перспективных алгоритмических языков заметно снизилась. Примером тому может служить язык Паскаль, опубликованный его автором еще в 1971 г. и ожидавший около 10 лет своего компилятора на ЕС ЭВМ.

Советским специалистам в области программирования предлагается перевод новой книги Р. Хантера «Проектирование и конструирование компиляторов» не только для того, чтобы в какой-то мере обеспечить подготовку высококвалифицированных разработчиков компиляторов. В большей степени эта книга будет способствовать познанию специалистами процесса компиляции, пониманию работы компиляторов и как следствие лучшему применению языков программирования. Без познания этого процесса, без необходимого теоретического уровня и практического опыта в программировании нельзя рассчитывать на своевременную разработку нового поколения языков спецификации очень высокого уровня. Поскольку развитие программирования обеспечивается применяемыми алгоритмическими языками и компиляторами с этих языков, книга Р. Хантера, детально описывающая известные методы построения компиляторов, безусловно, сыграет свою положительную роль в этом процессе.

Предлагаемая книга является первым практическим пособием, в котором все составные части компилятора и сам механизм их проектирования достаточно полно раскрыты с использованием средств, хорошо известных программистам. И хотя изложение материала опирается на еще не получивший широкого распространения Алгол 68, для чтения книги достаточно знания одного из массовых алгоритмических языков (Алгола 60, Фортрана или ПЛ/1).

Основная часть книги посвящена контекстно-свободным грамматикам, применяемым для разбора текста исходных программ. Читателю становится понятно, почему грамматики алгоритмических языков, а следовательно, и сами языки не могут быть выбраны произвольно и должны быть предельно простыми. На примере LL(1)-

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

Значительная роль отведена автором регулярной грамматике, или в иерархической классификации Хомского грамматике типа 3 и регулярным выражениям. Поскольку из регулярных выражений получают регулярные множества, с которыми устанавливаются алгоритмические соответствия строк языка, такие свойства регулярных множеств используются разработчиками компиляторов. Например, проверку строк языка в этом случае организуют конечным автоматом, так как существует полное соответствие между регулярными выражениями (грамматиками типа 3) и конечными автоматами. На этом основании лексический анализатор может быть представлен различными автоматами для распознавания идентификаторов, чисел, зарезервированных слов и т.п.

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

Большой интерес представляет механизм распределения памяти для параллельной обработки, допускаемой в языке.

Цели создания компилятора в некоторой степени противоречивы. Так, эффективность объектного кода зависит от размера программы, трудно сделать небольшой компилятор, работающий надежно и хорошо исправляющий ошибки. Общее количество проходов, выбор промежуточного языка - эти и многие другие свойства компиляторов усложняют их разработку. Вот почему так важны четкие требования к определению исходного языка, включая уточнения грамматики, приведенные в книге Р. Хантера.

Практически ни один из вопросов, связанных с проектированием компиляторов, не упущен автором. Доходчивость и строгость изложения позволяют отнести книгу Р. Хантера к числу практических и учебных пособий, способствующих общему повышению программистской грамотности. Такая книга необходима сегодня программистам, студентам и аспирантам вузов, а также разработчикам информационных систем.

В. М. Савинков

ПРЕДИСЛОВИЕ

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

Книга может служить учебным пособием для студентов старших курсов, и именно такое применение она нашла в Стратклайдском университете. В ней обсуждается реализация языков с блочной структурой (Алгола 60, ПЛ/1, Алгола 68, Паскаля и Ады) с учетом особенностей конкретных языков. Описание алгоритмов приводится на реальном языке программирования (Алголе 68), но это не препятствует их пониманию, даже если студент незнаком сданным языком. Каждая глава завершается упражнениями, цель которых - помочь студентам лучше разобраться в построении компиляторов. В заключение книги читателю предлагаются схематические ответы на упражнения к гл. I -12.

В гл. 1 рассматривается процесс компиляции в целом, а также связь между языками программирования высокого уровня и типичными ЭВМ. В Гл. 2 дается формальное определение языков программирования, Гл. 3 посвящается лексическому анализу, а Гл. 4 и 5 - методам синтаксического анализа сверху вниз и снизу вверх.

В гл. 6 описывается применение бесконтекстной грамматики в качестве рамок для действий компилятора, а в Гл. 7 -- проектирование компиляторов, причем особое внимание уделяется проектированию многопроходных компиляторов.

Структура таблиц символов и видов (или типов) для языков с комплексными типами обсуждается в Гл. 8. Гл. 9 знакомит читателя с локальным и глобальным распределением памяти. Гл. 10 и 11 посвящены вопросам генерирования кода и использования, не зависящего от машины промежуточного кода.

В гл. 12 обсуждаются методы исправления и диагностики ошибок, а в гл. 13 высказываются некоторые соображения относительно построения надежных компиляторов.