Глава 7. Проектирование компилятора

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

7.1. Число проходов

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

Некоторые языки, такие как Фортран или Паскаль, полностью компилируются за один проход. Если же язык нельзя скомпилировать за один проход, однопроходные компиляторы пишутся для его подмножеств или диалектов. Обычное ограничение, которое вводится для этих компиляторов. Заключается в том, что все идентификаторы и т. д. должны описываться (в тексте) до их использования. В некоторых ситуациях язык необходимо расширить, чтобы, например, при взаимно рекурсивных типах или процедурах объект можно было бы «описать» до того, как он будет полностью определен. Так, ряд компиляторов Алгола 60 требуют описания меток, а компилятор Алгола 68R, написанный в RSRE (Малверн, Англия), имеет «описание»

mode abc

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

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

определенном языке, и не будем вводить ограничения на язык или добавлять к нему средства суперязыка, помогающие разработчику компилятора.

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

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

Необходимость в более чем одном проходе обычно возникает в связи с тем, что какая - то требуемая компилятору информация отсутствует в соответствующий момент времени. Так, для компиляции

x + y

во многих языках нужно знать типы x и y, чтобы определить знак операции может означать сложение либо двух целых чисел, либо двух вещественных чисел, либо одного вещественного и одного целого и т.д. Если определяющим реализациям x и y разрешено следовать за их прикладными реализациями, код обычно не может генерировать за один проход. В Алголе 60 эта проблема не возникает, но при наличии взаимно рекурсивных процедур одна процедура неизбежно должна объявляться раньше другой. Допустим, например, что тело процедуры А содержит вызов или вызовы процедуры В, а процедура В содержит вызов ил вызовы процедуры А. Если процедура А объявляется первой, то компилятор не будет генерировать код для вызова В внутри А, не зная типа параметров В «если они есть», и в случае процедуры возвращающий результат « функции», и тип этого результата может потребоваться для идентификации, с кажем, обозначения операции.

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

Это даст возможность определить типы идентификаторов и т.д. и поместить их в таблицу символов с тем, чтобы ими могли воспользоваться последующие проходы. Теоретически Алгол 60 можно скомпилировать таким методом за два прохода, хотя многие более ранние компиляторы Алгола 60[47] имели часто семь - восемь

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

Многие языки нуждаются по меньшей мере в двух проходах по тем же причинам, что и Алгол 60. Компиляторы полного Алгола 68 обычно имеют четыре -восемь проходов. Интересно выяснить, сколько проходов действительно необходимо для компиляции этого языка. Как и в Алголе 60, для генерации кода здесь нужно знать вид (или тип) каждого идентификатора, константы и т.д., а, поскольку описания идентификаторов могут появляться после их употребления, определенно требуется не меньше двух проходов. Представим себе такой проход, который просматривает программу, отмечая виды всех идентификаторов и помещая эту информацию в таблицу символов, чтобы ею можно было воспользоваться при следующем проходе для генерации кода. Однако во время первого прохода нельзя распознать все описания, так как последовательность

abc abc

Может быть описанием идентификаторов abc, вида ref abc или выражения

monadic operator «abc» identifier «abc»

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

abc abc

Указанная проблема разрешается с помощью еще одного прохода. В терминах Алгола 68 abc - это выделенное слово, а выделенные слова могут использоваться для представления специфицируемых пользователем видов или обозначений операций. Информация о выделенном слове (вид или обозначение операции) может быть дана в виде текста после того, как она потребуется проходу, помещаемому сведения о видах в таблицу символов. Поэтому нужен еще один, предшествующий этому, проход, который строил бы таблицы, содержащие информацию о том, как используются выделенные слова в различных блоках программы.

Теперь оказывается, что для компиляции Алгола 68 требуется не менее трех проходов. Причина, по которой Алголу 68 может понадобиться более трех проходов, связана с перегрузкой символа открывающей скобки «(». Этот символ употребляется для обозначения начала условного предложения, вариантного предложения, процедуры, совместного или замкнутого предложения, вместо открывающей квадратной скобки при индексации массивов и т.д. Значение

(real x, y, int a, b) real

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