Стратегии восстановления после ошибок

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

Этот раздел посвящен следующим стратегиям восстановления: режим паники, уровень фразы, продукции ошибок и глобальная коррекция.

Восстановление в режиме паники

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

Восстановление на уровне фразы

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

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

Продукции ошибок

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

Глобальная коррекция

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

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

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

Контекстно-свободные языки