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

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

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

Рассмотренный метод иллюстрируется следующим образом:

Вид программы Begin int a,b

begin int c,d

end;

begin int e,f

Таблица символов показана после встречи с begin int e и f.

6.3. ДРУГИЕ ПРИЛОЖЕНИЯ

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

Как уже отмечалось ранее, компилятор - это просто программа, которая принимает на входе программу, написанную на определенном языке, и выдает на выходе программу в машинном коде. Выход в виде машинного кода не совсем уместен по отношению к синтаксическому анализатору, поэтому заслуживает внимания идея создания «синтаксического анализатора» с втходом какого-либо

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

1. Программа размещения

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

2. Анализаторы программ

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

а) перечисление идентификаторов, используемых в каждом блоке;

б) учет числа реализаций различнтх типов предложений, операторов и т. п.;

в) оптимизация исходного кода. Здесь выходом будет другая версия программы на том же самом языке.

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

Упражнения

6.1. Покажите, как нужно изменить пример из разд. 6.1, чтобы вместо четверок получать постфиксную нотацию. (В постфиксной нотации каждый знак операции появляется сразу вслед за своими операндами. Например, (инфиксное) выражение

(a+b)x(c+d) примет вид ab + cd+x

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

6.3. Необходимо ли в примере из разд. 6.1. помещать в стек знак операции, если имеется только один знак операции с каждым приоритетом?

6.4. В некоторых языках приоритет знака может объявляться программистом. Как, по вашему мнению, синтаксический анализатор отреагирует на это?

6.5. Приведите примеры входов (помимо программ), которые синтаксический анализатор смог бы обработать.

6.6. Какие проблемы вы видите в написании полностью удовлетворительной программы «размещения»?

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

6.8. Как вы считаете, какую форму примет таблица символов в языке Бейсик или Фортран?

6.9. Какие вы можете привести аргументы, чтобы разрешить описаниям появиться почти в любом месте в блоке?

6.10. В настоящей главе мы познакомили вас с таблицей разбора, которая может «вызвать» действия, выполняемые во время компиляции. Как в связи с этим следует видоизменить элементы таблицы разбора и драйвер LL(1), рассмотренный в разд. 4.5.?