это приводит к значительному снижению эффективности). В гл. 10 было показано, что обнаружение последовательностей приведения тоже может основываться почти непосредственно на сообщении. Костер [40] описывает компилятор компиляторов, базирующийся на двухуровневых грамматиках, который использовался при создании Манчестерского компилятора Алгола 68 [5].

Конечно, разработчику компиляторов хотелось бы, чтобы формальное определение языка позволяло реализовать его более или менее непосредственным путем, хотя это в некоторой степени может противоречить другим требованиям, предъявляемым к формальному определению. Взаимосвязь между формальным определением языка и его реализацией рассматривается в [23], а способы выражения контекстно-зависимых аспектов Алгола 60 и Бейсика с помощью формальной нотации - в [58].

13.2. МОДУЛЬНОЕ ПРОЕКТИРОВАНИЕ

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

С целью обеспечения надежности, простоты обновления и т. п. желательно, чтобы коды для различных фаз компиляции, входящих в один проход, хранились по возможности отдельно. Часто этого можно добиться, если одна фаза будет вызывать другую как процедуру. Общеизвестно, например, что синтаксический анализатор вызывает лексический анализатор как процедуру. Можно привести и другой пример: когда две фазы обладают одинаковым статусом, используются сопрограммы или фазы считаются кооперированными последовательными процессами [18].

Если код какого-либо прохода включает в основном действия, вызываемые синтаксическим анализатором, а сами действия являются элементами вариантного предложения case, то для разделения кодов, соответствующих, скажем, двум фазам, составляющим этот проход, можно применить следующую стратегию. Предложение case, содержащее действия, вызываемые анализатором, имеет форму:

case i in action 1, action 2, action 3,

Здесь action 1 может быть таким: begin prologue;

phase 1 (1); phase2 (I); epilogue

где phase 1 - процедура вида

proc phase1 = (int no) void: begin case no in

esac

Так что вызов phasel (1) повлечет за собой выполнение первого элемента предложения case в пределах phase1. Процедура phase 2 по форме аналогична phase1, a prologue включает такие действия, как удаление из стека значений времени компиляции, требуемых и для phase1, и для phase2. Prologue и epilogue введены с тем, чтобы эти фазы не выполняли одни и те же поддействия.

Как уже отмечалось, коды для различных фаз должны храниться по возможности раздельно. Более того, весьма желательно, чтобы эти фазы знали друг о друге как можно меньше. Например, синтаксическому анализатору вовсе не нужно знать, как лексический анализатор собирает литеры в символы; все что ему требуется, - это вызвать подпрограмму, которая выдаст следующий символ. Генератору кода не должно быть известно, как распределяются адреса, если он может получить их при необходимости из таблицы символов, а распределение адресов и помещение их там, где это нужно, в таблицу символов является задачей распределителя памяти. Ни генератору кода, ни распределителю памяти не требуется знать структуру таблицы символов, если имеются соответствующие подпрограммы обращения к таблице и ее обновления.

В таких языках, как Ада, состоящих из модулей или пакетов, можно прятать идентификаторы от тех частей программы, для которых доступ к ним не нужен. Идентификаторы можно прятать также в Алголе 68R. Когда какой-то сегмент программы компилируется отдельно, идентификаторы будут видны следующим сегментам, только если они явно включена: в список keep, ассоциируемый с определеннтм сегментом. Следующий сегмент объявляет, что массив должен использоваться в виде стека вместе с указателем стека и процедурами push и pop для помещения элемента в стек и удаления его оттуда:

stackseg

begm[/:50] ил stack; int stackptr: = 0; proc push = (int v) void : begin if stackptr =/= 50

then stackptr plusab 1/ ;

stack [stackptr] : = v

else full

end:

proc pop = int ; begin int v;

if stackptr =/= О then v : = stack [stackptr] ; stackptr minusab / else empty

end; skip end

keep push, pop

Здесь, как обычно, full и empty - процедуры обращения с переполнением и незаполнением соответственно.

После того как сегмент скомпилирован и помещен в так называемый альбом myalbum, можно скомпилировать другой сегмент mainprog, имеющий вид

mainprog with stackseg from myalbum

begin

В сегменте mainprog для доступа к стеку, описанному в сегменте stackseg, можно использовать процедуры push и pop, но никак нельзя обратиться к stack или stackptr идентификаторов. Можно преобразовать структуру данных, представляющих стек, например, в список, переписать процедуры push и pop и перекомпилировать сегмент stackseg. Если старую скомпилированную версию stackseg, находящуюся в альбоме, заменить новой, mainprog, тогда можно запустить с новым типом стека, но сам этот сегмент останется неизменным.

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

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

13.3. ПРОВЕРКА КОМПИЛЯТОРА

Как и другие программы, компилятор не следует считать надежным, пока он не будет тщательно выверен на пробном вводе. Желательно проверять каждый аспект компиляции отдельно по мере разработки компилятора, чтобы устранять большинство возникающих ошибок, а не уже полностью написаннтй компилятор. Конечно, необходимо проверить и компилятор в целом на предмет устранения каких-либо общих недостатков проектирования. Программы для проверки компилятора должны быть написаны не самими разработчиками, а другими лицами, не знакомыми с деталями реализации. Можно также генерировать инте проверяющие программы с помощью синтаксического анализатора [30].