Разработка компиляторов
Локальные стратегии продолжения анализа
Оказывается, большинство ошибок в программе обнаруживается на фазе синтаксического анализа. Это можно объяснить с одной стороны тем, что многие ошибки являются синтаксическими по своей природе или их проще выявить, когда поток лексем поступает на вход синтаксическому анализатору. С другой стороны, это можно объяснить тем, что наиболее развиты именно методы синтаксического анализа. Вообще говоря, ошибки в программе можно классифицировать следующим образом: 60% составляют пунктуационные ошибки, 20% - ошибки в операторах и операндах, 15% - ошибки в ключевых словах, на все остальные ошибки остается 5%.
Пусть дана контекстно-свободная грамматика и неверная цепочка serr = t1t2…te-1tete+1 …tn . Мы можем выделить ошибочный символ te как первый символ, на котором может быть определена ошибка при сканировании входной цепочки слева направо. Таким образом, подцепочка t1t2…te-1 является префиксом некоторой правильной цепочки t1t2…te-1 … языка в то время, как не существует правильной цепочки правильной цепочки t1t2…te-1te…, содержащей неверный символ.
В случае ошибки лексический анализатор, сгенерированный YACC'ом, вызывает функцию yyerror, которая должна быть описана пользователем, и полностью завершает обработку. Это означает, что вы можете обнаружить только одну ошибку.
Когда обнаружена ошибка, редко бывает достаточно остановить всю обработку при обнаружении ошибки; более полезно продолжить сканирование входных данных для нахождения дальнейших синтаксических ошибок. Методы восстановления после синтаксической ошибки разделяются на локальные и глобальные. Локальные методы сводятся к изменению только цепочки tete+1…tn , тогда как глобальные методы позволяют изменять символы, расположенные до ошибочного символа. Локальные методы меньше влияют на среду анализатора, поскольку при их использовании не приходится отменять решения уже принятые анализатором, например, не требуется перестраивать синтаксическое дерево.
Имеются различные стратегии продолжения анализа после нахождения синтаксической ошибки:
- Panic mode. Это простейший для реализации метод и он может быть использован для большинства синтаксических анализаторов. При обнаружении ошибки анализатор пропускает лексемы до тех пор, пока не будет обнаружена одна из синхронизирующих лексем. Под синхронизирующими лексемами обычно понимаются ограничители, например, такие, как точка с запятой или end, роль которых в исходной программе ясна. Конечно, разработчики компилятора могут выбрать и другие лексемы в качестве синхронизирующих. Понятно, что при такой стратегии может быть пропущено большое количество лексем без анализа их правильности. Этот метод привлекает своей простотой, хотя в отличии от других методов он не может гарантировать, что компилятор не попадет, например, в бесконечный цикл. Наиболее эффективен этот метод может быть в таких случаях, когда несколько ошибок в одном операторе встречаются редко. На самом деле, это почти всегда так. По статистике 80% неверных операторов имеют только одну ошибку, 13% - две.
- Phrase level. При обнаружении ошибки анализатор может попытаться подправить еще не обработанную часть входной цепочки. Например, он может заменить префикс оставшейся части входной цепочки на некоторую строку, которая позволит ему продолжить анализ. Типичные локальные коррекции - это замена точки с запятой на запятую, удаление ошибочной точки с запятой или вставка отсутствующей. Выбор локальных исправлений полностью ложится на разработчика компилятора. Главный недостаток этого метода заключается в том, что на самом деле ошибка может находиться до того, как она будет обнаружена. Обычно возможно более одного изменения неверной цепочки и требуется сделать выбор между ними. Один из методов принятия решения об изменении неверной цепочки называется методом минимального расстояния или минимальной цены восстановления. Этот метод связывает с каждым символом стоимость его удаления из неверной строки или его добавления к неверной строке. Затем выбирается символ и операция над ним с минимальной стоимостью. Методы восстановления, связанные с системами генерации синтаксических анализаторов, требуют взаимодействия с пользователем генератора.Некоторые из них полностью автоматические, иные требуют, чтобы пользователь определил стоимости вставки/удаления.
