Нейтрализация синтаксических ошибок

На любом этапе грамматического разбора исходная программа имеет следующий вид x T t, где x – обработанная часть, T – следующий сканируемый символ, а t – остальная часть исходной программы. Предположим, что встретилась ошибка. При нисходящем разборе это означает, что построено частичное дерево, опирающееся на x, но его нельзя расширить так, чтобы оно опиралось и на T. При восходящем разборе может оказаться, что либо между хвостом x и символом T не определено отношение предшествования, либо никакой хвост x не является основой и т.п.

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

1. Исключить T и попытаться продолжить разбор.

2. Вставить цепочку q, состоящую из терминалов, между x и T (получится цепочка xqTt) и начать разбор, используя голову цепочки qTt. Эта вставка позволит целиком обработать qT, прежде чем возникнет другая ошибка.

3. Вставить цепочку q между x и T (получится цепочка xqTt), но разбор начать с T. (При восходящем разборе q необходимо поместить в стек.)

4. Исключить несколько последних символов из цепочки x.

Способы 1 и 2 предпочтительнее для нейтрализации, так как они не меняют содержимое стека, а значит, и не требуют изменения семантики. Так как цепочка x уже обработана, с ней, возможно, уже связана семантическая информация. Добавление q к x или выбрасывание части x означает, что нужно соответствующим образом изменить и семантическую информацию, а сделать это совсем не просто.

Казалось бы, что можно добавить “ошибочные” правила в грамматику и заранее принять меры против ошибок. Например, мы могли бы добавить правило

<присваивание> ®:=<выражение>

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

Рассмотрим метод нейтрализации ошибок при нисходящем разборе, предложенный в 1963 году Е. Айронсом, на примере грамматики в расширенной форме Бэкуса-Наура:

P ® A;

A ® i:=E

E ® T{+T}

T ® F{*F}

F ® iï(E)

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

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

На любом шаге разбора мы имеем дело с одним или несколькими синтаксическими деревьями, в которых есть несколько неполных кустов. Например, на рис. 6.18 а, сплошными линиями показано, как выглядит частично построенное дерево, а пунктирными – как можно было бы дополнить кусты с именами P и E.

Неполный куст U соответствует применению правила

U®X₁X₂¼X_i-1X_i¼X_n

где X₁X₂¼X_i-1 – построенная, а X_i¼X_n – недостающая часть куста. На рис. 6.18 а неполный куст с именем P соответствует применению правила P®A;, а “; ” – недостающая часть куста. Неполный куст E соответствует применению правила E ® T{+T}. Чтобы дополнить куст необходим нетерминал T, за которым следует любое количество цепочек “+T ”. Недостающей частью, следовательно является T{+T}.

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

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

1. Строится список L из символов недостающих частей неполных кустов.

2. Головной символ T в цепочке Tt проверяется и отбрасывается (при этом каждый раз получается новая цепочка Tt) до тех пор, пока не найдется символ T, такой, что UÞ^* T¼ для некоторого UÎL (либо U=T, либо UÞ⁺ T¼).

3. Определяется неполный куст, который на шаге 2 стал причиной появления символа U в списке L.

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

5. Цепочка q вставляется непосредственно перед T, и разбор продолжается, начиная с головного символа цепочки q, который становится входным символом.

Рассмотрим пример грамматического разбора, изображенного на рис. 6.18 а. Ошибка была обнаружена, когда входным символом была скобка “)”. Строим список L={;, T, +}. На шаге 2 пропускается символ “ ) ”. Неполный куст, вызвавший появление “;” в L, есть P ® A;. Мы должны, следовательно, вставить цепочку q, чтобы дополнить куст E ® T{+T}. Проще всего вставить идентификатор i (см. рис. 6.18 б).

Рис. 6.19 а иллюстрирует, как предлагаемая схема нейтрализации использует “глобальный” контекст. Кажется, что ошибка такая же, что и на рис. 6.18 а: за “ + ” идет “ ) ”. Однако теперь L={;,), T, +} и на этот раз скобка на шаге 2 не выбрасывается. Неполный куст, вызвавший появление “ ) ” в L, - правило F ® (E). Для того, чтобы “ ) ” была связана с этим кустом, мы должны вставить цепочку, чтобы дополнить куст, и такой цепочкой снова будет i (см. рис. 6.19 б). Заметим, что открывающая скобка могла стоять намного дальше от места ошибки, и все же она учитывалась бы при нейтрализации, поскольку при нейтрализации ошибки принимаются во внимание все неполные кусты.

При использовании одной из разновидностей нисходящего разбора – рекурсивного спуска (см. раздел 5.1.2), частично построенное синтаксическое дерево явно не представлено, и здесь применяется несколько иной подход. Если рекурсивная процедура обнаруживает ошибку, то она выводит сообщение о ней и в зависимости от очередного входного символа T можно выбрать одну из двух альтернатив – либо что-то вставить и таким образом исправить ошибку, после чего продолжить работу, либо вернуться в вызывающую программу с указанием об ошибке. Например, если программа для правила

F ® iï(E)

не находит “ ( ” или “ i ”, то она может вставить “ i ” и продолжить разбор. Если она нашла “ (E ”, но не обнаружила закрывающей скобки, то она может предположить, что эта скобка есть, и вернуться в вызывающую программу.

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

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

Подобный подход используется и при восходящем разборе. Так в системе построения компиляторов XPL [12] разработчик компилятора должен занести в массив STOPIT “особые” синхронизирующие символы типа “; ” и “ END ”. Если обнаружена ошибка, то выполняется следующее:

1. Символы в цепочке Tt последовательно просматриваются и выбрасываются до тех пор, пока один из них не совпадет с каким-либо символом из STOPIT.

2. Получен новый символ T. Теперь просматриваются и выбрасываются символы цепочки x до тех пор, пока символ не состыкуется правильно с оставшимися символами x.

Поиск по сайту: