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

Контекстно-зависимые требования языка, как правило, представляются действиями, включенными в контекстно-свободную грамматику. Ими могут быть внесение информации в таблицу символов или таблицу выделенных слов и поиск вида либо другой информации в одной из этих таблиц. Такие действия соответствуют атрибутам в атрибутивной грамматике или метапонятиям в двухуровневой грамматике. Действие, соответствующее каждому атрибуту или метапонятию в грамматике, появляется в одном из проходов на стадии анализа. Например, проход, который распознает описания идентификаторов, включает действия по внесению в таблицу символов информации о видах, а последующий проход включает действия поиска этой информации в таблице символов. Проверку контекстно-зависимых аспектов языков можно представить распределённой по ряду проходов в компиляции аналогично тому, как это имеет место с контекстно-свободными аспектами. Существует алгоритм, позволяющий определить минимальное число проходов, необходимых для анализа заданной атрибутивной грамматики [9].

Можно назвать ещё ряд причин, по которым компиляторы Алгола 68 (или другие) могут иметь дополнительные проходы. Это связано с используемой для генерации машинного кода моделью, с тем, какие требуются оптимизации, и должны ли мы сделать компилятор переносным. Некоторые из указанных вопросов будут обсуждаться в главе 10 и 11.

Мы определили, что компилятору Алгола 68 понадобиться не менее трёх проходов, чтобы проанализировать все программы на этом языке. Но не каждой программе для анализа нужны все три прохода. Например, в программе могут отсутствовать прикладные реализации идентификаторов, встречающиеся перед их определяющими реализациями, либо специфицируемые пользователем виды или обозначения операций. В таком случае программа могла бы быть скомпилирована за один проход. Обработка её тремя проходами, в то время как можно обойтись только одним, представляется излишней. Однако компилятору не известно в начале компиляции (если ему не сообщит пользователь), требуются ли проходы для построения таблиц символов и т. п. Или ему достаточно одного прохода. Он узнает об этом лишь по завершении анализа. В Манчестерском компиляторе Ангола 68 для Ми5 [5] принято следующее решение. Считается, что анализ может быть выполнен за один проход, если это не окажется невозможным.

Рассмотрим следующий пример:

begin int p; begin proc q=void: begin p end;

proc p = void:

Компилятор может пытаться завершить анализ приведённой программы за один проход. Информация заносится в таблицы по мере поступления, и компиляция выполняется при допущении, что все было описано заранее. Этот процесс продолжается до тех пор, пока это условие не нарушится. В нашем примере первоначально считается, что прикладная реализация p в теле процедуры q относится к p, описанному во внешнем блоке. Когда же описание p встретится в том же самом блоке, станет очевидным, что было сделано ложное допущение, и от попытки завершить анализ за один проход придётся отказаться. Однако компилятор продолжит чтение исходного текста, чтобы собрать как можно больше информации для таблицы символов. Таблица символов потребуется при следующем проходе, когда снова будет сделана попытка проанализировать всю программу полностью, на этот раз с помощью некоторой табличной информации. Ясно, что из-за неправильного допущения, принятого при первом проходе, могут появиться ложные сообщения об ошибках, но они не передаются сразу пользователю.

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

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

7.2. Промежуточные языки.

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

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

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

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

7.3. Объектные языки.

Иногда можно разделять не зависящие и зависящие от машины части компилятора, что весьма желательно в тех случаях, когда его предлагают сделать переносным. С этой целью нужно определить так называемый объектный язык, который является посредником между двумя частями: не зависящей от машины частью компилятора, транслирующей исходный код в объектный язык, и зависящей от машины частью, транслирующей объектный язык в конкретный машинный код. Если бы мы могли использовать один и тот же объектный язык (и общий язык реализации), задача реализации m языков на n машинах свелась бы к написанию m + n частей программного обеспечения, т. е. m не зависящих от машины «фронтальных частей» компилятора и n зависящих от неё «хвостов» компилятора, а не m*n полнтх компиляторов. Объектный язык можно также представить себе в виде машины, обычно называемой абстрактной, так как фронтальная часть компилятора видит его как объектную машину. Существует целый ряд таких универсальных объектных языков или абстрактных машин, например Янус (JANUS) [48], но все же эта идея, по-видимому, не нашла должного применения.