Принципы восстановления

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

1. Пропуск части входной последовательности

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

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

В Паскале это правило строго соблюдается: каждый оператор начинается с однозначного служебного слова, такого, как begin, if, while; то же относится к описаниям: они начинаются с var, const или procedure.

Мы назовем это правилом служеб­ных слов, а само множество символов – символами возобновления - renew_sym [ri`nju:].

renew_sym: tsym

renew_sym:= [ ifsym, whilesym, begsym]

2. Не поднимать панику

Второе правило более непосредственно связано с построе­нием программы грамматического разбора. Для нисходящего анализа характерно, что цели разбиваются на подцели; при этом процедуры вызывают другие процедуры, соответствую­щие этим подцелям. Второе правило определяет, что если процедура грамматического разбора обнаруживает ошибку, то она не должна прекращать работу и сообщать о случившемся вызвавшей ее процедуре. Вместо этого она должна самостоя­тельно продолжать просмотр текста до того места, откуда можно возобновить анализ. Мы назовем это правилом «не поднимай панику». Из него следует, что из процедуры грам­матического разбора не может быть другого выхода, кроме обычного завершения работы.

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

out_sym: tsym

Определение внешних символов

(для грамматики арифметических выражений)

1 Prog

expr

.

2 EXPR

add

add

3 ADD

mult

mult

4 MULT

expr

процедура	Внешние символы	out_sym
Expr	. )	dot r_parent
Add	+ – . )	plus minus dot r_parent
Mult	* / + – . )	Umn div plus minus dot r_parent

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

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

Эта процедура имеет три пара­метра:

1. Множество sl допустимых следующих символов; если теку­щий символ к нему не принадлежит, то имеет место ошибка.

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

3. Номер n, который присваивается ошибке, если процедура ее обнаружит.

Процедура возобновления

procedure test (sl, s2: symset; n: integer);

begin

if not (sym in sl)

then

begin

error(n);

sl := sl + s2;

while not (sym in sl) do getsym

end

end

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

if sym = a1

then S1

else if sym = aN

then SN

else X

который получен из порождающего правила

A::- a1 S1 |...| aN SN | X. (5.18- 1)

В этих случаях параметр sl должен содержать множество начальных символов X, а s2 — множество внешних символов A (см. табл. 5.2 1).

Подробно эта процедура показана в про­грамме 5.5, которая представляет собой дополненную версию программы 5.4. Для удобства читателя вся программа при­ведена полностью, за исключением инициации глобальных переменных и процедуры getsym, оставшихся без изменений.