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

Упражнения

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

12.2. Некоторые языки используют «зарезервированные» идентификаторы в качестве слов. Какие преимущества это дает в смысле обнаружения ошибок?

12.3. Какие средства языка могут спровоцировать программиста на ошибку или не позволят ему допустить ее?

12.4. Какие средства языка могут способствовать полезным сообщениям об ошибках, а какие нет?

12.5. Объясните, как при наличии фиктивного оператора (не состоящего из каких-либо символов) в Алголе 60 и Паскале может остаться незамеченным неправильное употребление точек с запятой.

12.6. Какое преимущество в отношении исправления ошибок предлагают ограничители

комментария в Паскале («{»,«}») по сравнению с ограничителями в Алголе 68 (со, со)?

12.7. Считаете ли вы, что стратегия исправления ошибок не должна зависеть от исходного языка?

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

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

12.10. Предложите, как можно написать компилятор с одним ограничением в отношении объема памяти, т. е. чтобы программы не могли бы компилироваться только из-за недостатка в объеме памяти, если бы вся доступная компилятору память была заполнена.

Глава 1 3. СОЗДАНИЕ НАДЕЖНЫХ КОМПИЛЯТОРОВ

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

13.1. ИСПОЛЬЗОВАНИЕ ФОРМАЛЬНОГО ОПРЕДЕЛЕНИЯ

В формальном определении языка описываются 1) его синтаксис и 2) его семантика. Что касается синтаксиса, то с точки зрения разработчика контекстно-свободные и контекстно-зависимые аспекты удобно рассматривать отдельно. Как мы уже видели, контекстно-свободную грамматику, соответствующую контекстно-свободным аспектам языка, обычно с помощью соответствующего генератора анализаторов можно преобразовать в контекстно-свободный синтаксический анализатор. Более того, привлечение к этому делу программы (а не вручную) дает еще большую уверенность в надежности получаемого анализатора. Двухуровневая грамматика, на которой базируется Алгол 68, представляет собой, конечно, обобщение контекстно-свободной грамматики, и поэтому нужно тщательно определить лежащую в ее основе контекстно-свободную грамматику, вводимую в генератор анализаторов. В значительной степени этого можно добиться, подавляя метапонятия и предикаты, связанные с видами, определяющими и прикладными реализациями, и т. д. Если допустить, что в генератор анализаторов подается «правильная» контекстно-свободная грамматика, можно надеяться, что полученный в результате анализатор будет достаточно надежным.

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

Например, большинство контекстно-зависимых аспектов Алгола 68 можно выразить с помощью атрибутивной грамматики [51]. Уже разработаны методы автоматического построения анализаторов на основании определенных классов атрибутивных грамматик [57].

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

REF to MODE NEST assignation : REF TO MODE NEST destination, становится

token, MODE NEST source.

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

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

MODE1 NEST source : strong MODE2 NEST unit, where MODE1 deflexes to MODE2. у нас имеется предикат

where MODE1 deflexes to MODE2

который позволяет обеспечить соотношения двух видов путем «приведения». При выполнении приведения можно воспользоваться действием, включенным в грамматику в соответствующем месте. Это - вызов процедуры deflexes с параметром MODEL Определение предиката deflexes дано в сообщении ([55] разд. 4.7.1), а вызов соответствующей процедуры может быть рекурсивным.

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

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