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

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

Во многих случаях, когда неправильно используется идентификатор, достаточно вывести сообщение об ошибке и продолжить компиляцию. Например, если анализируется оператор AB; где A – переменная типа REAL, а B – переменная типа BOOLEAN, то мы можем просто сообщить о несовместимости типов для A и B в операторе присваивания и продолжить работу, так как нет необходимости связывать с нетерминалом инструкция присваивания какую либо “семантику” и, следовательно, лишние сообщения выводится не будут.

Рассмотрим теперь переменную с индексами A[e₁, , e_n], когда с идентификатором связана некоторая “структура”. Положим, что в программе A не объявлено, как массив. Тогда будет выдано сообщение об ошибке и продолжится грамматический разбор индексов. После окончания разбора индексов их число будет сравниваться с размерностью массива, которая указана в элементе таблицы идентификаторов для A. Так как A не имя массива, то появится второе сообщение об ошибке. Такую ошибку можно довольно просто нейтрализовать и подавить лишние сообщения, относящиеся к данному идентификатору, если заменить его в исходной программе “корректным” идентификатором. В таблицу идентификаторов заносится новый корректирующий элемент с правильными, насколько это возможно, атрибутами. Программе, формирующей сообщения об ошибке, передается в качестве параметра указатель элемента таблицы идентификаторов, который вызвал ошибку. Программа проверяет, не является ли этот элемент корректирующим идентификатором, вставленным для нейтрализации ранее обнаруженной ошибки, и если это так, то лишнее сообщение об ошибке не формируется.

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

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

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

На любом этапе грамматического разбора исходная программа имеет следующий вид 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.

Упражнения.

6.1. Перевести в ПОЛИЗ, используя метод Замельсона – Бауэра, следующий фрагмент программы:

iabc

if ( (i  0) and (y  x10) ) then begin

x  b10ay(b-x) j15

while (j  20) do begin y(y2)a jj1 end

i(i a)bc

end aa bc d

Проинтерпретируйте полученную строку ПОЛИЗа и сгенерируйте по ней эквивалентный набор команд на языке ассемблера.

6.2. Перевести в тетрады, используя метод Замельсона – Бауэра, следующий фрагмент программы:

if ( (x  100) or (y   x10) and (y  b) then

x  (ab DIV 10)y MOD b-x

else begin yabcd if y  a then yy2a x yab end;

aabcd

Сгенерируйте по полученным тетрадам эквивалентный набор команд на языке ассемблера.

Упражнения на программирование.

6.3. Программно реализуйте алгоритм Замельсона – Бауэра для перевода ПОЛИЗ арифметических выражений, оператора присваивания и ряда управляющих конструкций. Напишите программу, интерпретирующую строку ПОЛИЗа и формирующую набор команд на языке ассемблера по заданной строке.

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