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

Real x

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

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

Приведем пример типичного фрагмента программы, в котором появляются открывающиеся скобки:

(square:=(int q) int:q 2 a:=(bcd)

обозначающие соответственно begin, начало процедуры, и if.

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

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

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

(a:=b; L:c:=d; a=cxy)

В этом фрагменте есть синтаксическая ошибка, поскольку в условном предложении между If (представленным открывающей скобкой) и then (представленным посредством черты ) метки не допускаются. Однако если открывающая скобка не распознается как if, сообщение об ошибке не выдается до тех пор, пока не встретится «».

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

Проход, выясняющий значение скобок, применяют также для проверки исходного текста. В Алголе 68 if должно иметь соответствующее ему fi, а открывающая скобка - закрывающую, т. е. последовательности.

If...........)

(...........fi

Является недопустимыми (то же относится к вариантному предложению и т.д.). Скобочный проход должен проверять такое соответствие и просто заменять открывающие и закрывающие скобки на if, fi,case и т. д., что поможет сократить размер грамматики (а следовательно, и таблицы разбора).

В Алголе 68 квадратные скобки обычно употребляются в связи с массивами как для определяющих, так и для прикладных реализаций, например

[1:n] real x

x[4]

Однако в полной реализации языка квадратные скобки разрешается заменять (согласующимися) круглыми скобками. Это неизбежно приводит к осложнениям в том, что касается стадии анализа в компиляции. Рассмотрим сначала прикладные реализации. Фрагмент

S(i,j)

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

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

Обратимся теперь к определяющим реализациям, например к

(m:n) int S

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

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

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