6.5. Нейтрализация ошибок

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

В ряде компиляторов, разработанных в 60-х – 70-х годах (Алгол, PL/C), пытались “исправлять” ошибки, генерировать команды и даже выполнять полученную программу, независимо от количества обнаруженных ошибок. На первый взгляд кажется, что это приведет к необоснованной потере времени, но надо учитывать технологию подготовки и отладки программ того времени. Программа набивалась на перфокарты или перфоленту, сдавалась на машину, запускалась в пакетном режиме и в результате через некоторое время разработчик получал листинг – протокол трансляции и выполнения программы. В этом случае для программиста преимущества очевидны, – уменьшается количество отладочных пусков, поскольку независимо от количества обнаруженных синтаксических ошибок предоставляется дополнительный шанс найти еще и логическую, алгоритмическую ошибку на этапе выполнения программы. Одна ошибка в пробивке перфокарты не станет препятствием для выполнения программы, и с большой вероятностью она будет исправлена разумным образом.

Техника исправления ошибок довольно сложна и опирается на нейтрализацию семантических и синтаксических ошибок, которые будет обсуждаться в разделах 6.5.2 и 6.5.3. Единственный метод, который можно легко объяснить – это метод исправления орфографических ошибок, который мы и рассмотрим в первую очередь.

6.5.1. Исправления орфографических ошибок

Существует несколько случаев, когда компилятор может сомневаться в правильности написания идентификатора:

1. Часто во время синтаксического анализа бывает известно, что следующий символ должен быть словом из некоторого набора служебных (ключевых) слов языка. Если вместо него оказался идентификатор, следует проверить, не служебное ли это слово, искаженное орфографической ошибкой. Именно с этим случаем мы встречаемся в языках типа BASIC, где любой оператор начинается с ключевого слова. Другим примером может служить логическое выражение Фортрана и других языков, в котором должны встречаться операции типа AND, OR, NOT, GE, LE и т.п. Можно было бы также следить за ошибочной “конкатенацией”. Например, если ожидается BEGIN, а встретился BEGINA, то его надо заменить на BEGIN A.

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

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

Далее возникает вопрос, какой из идентификаторов был неправильно написан. В методе Д. Фримана, предложенном в 1963 году, использовалась сложная оценочная функция, вычисляющая “вероятность” того, что один идентификатор является искажением другого. В этой функции использовалась информация о количестве совпадающих букв и о количестве совпадающих букв после одной или двух их перестановок. Учитывались также часто встречающиеся ошибки в пробивке перфокарт (цифра 0 вместо буквы O или цифра 1 вместо буквы l или I ).

Позднее этот метод был заменен более эффективным, но менее мощным методом, в основу которого положен тот факт, что около 80 процентов всех орфографических ошибок попадает в один из следующих четырех классов:

1) неверно написана или пробита одна буква;

2) пропущена одна буква;

3) вставлена одна лишняя буква;

4) две соседние литеры переставлены местами.

Суть этого метода состоит в следующем:

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

2. Затем нужно определить, какой идентификатор из выбранного подмножества можно превратить в заданный искаженный идентификатор, используя одно из четырех указанных выше преобразований.