yacc_doc (1119422), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Фиксируется число конфликтов каждого типа, число различных

действий грамматического анализатора, занимаемый им объем

памяти, приводятся данные об использовании внутренних струк-

тур данных (множеств).

10. Обработка ошибок при грамматическом разборе

Если входной поток не удовлетворяет заданной грамма-

тике, то грамматический анализатор в момент ввода лексемы,

делающей невозможным продолжение разбора, фиксирует ошибку.

Эту лексему мы в дальшейшем будем называть ошибочной лексе-

мой. Реально ошибка может быть вызвана не только неверными

входными данными, но и некорректностью самого грамматичес-

кого анализатора, являющейся следствием некорректной грамма-

тики.

Стандартной реакцией грамматического анализатора на

ошибку является выдача сообщения ("синтаксическая ошибка") и

прекращение разбора. Эту реакцию можно несколько изменить,

например, сделать сообщение об ошибке несколько более инфор-

мативным, задав собственную процедуру yyerror. Однако, наи-

более важная задача состоит в том, чтобы заставить анализа-

тор в этом случае продолжать просмотр входного потока, в

- 29 -

частности, для выявления остальных ошибок. Применяемый yacc

механизм восстановления основан на чтении и отбрасывании

некоторого числа входных лексем; от пользователя требуется

введение дополнительных грамматичсеких правил, указывающих,

в каких конструкциях синтаксические ошибки являются допусти-

мыми (в отношении возможности восстановления). Одновременно

эти правила определяют путь дальнейшего разбора для ошибоч-

ных ситуаций. Для указания точек допустимых ошибок исполь-

зуется зарезервированное с этой целью имя лексемы error.

Пример:

a: b c d ; /*1*/

a: b c error; /*2*/

d: d1 d2 d3; /*3*/

Второе правило указывает путь разбора в случае, если при

распознавании нетерминала a встретится ошибка после выделе-

ния элементов b и c.

yacc обрабатывает правила, содержащие лексему error,

так же, как все остальные правила. В результате в ряде сос-

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

действие для лексемы error (отличное от действия error).

Будем говорить, что в этих состояниях лексема error допус-

тима. Рассмотрим порядок работы анализатора при появлении

во входном потоке ошибочной лексемы (т.е. лексемы, ввод

которой в данном состоянии вызывает действие error):

Фиксируется состояние ошибки; вызывается функция yyer-

ror для выдачи сообщения.

Путем обратного просмотра пройденных состояний,начиная

с данного, делается попытка найти состояние, в котором

допустима лексема error. Отсутствие такого состояния

говорит о невозможности восстановления, и разбор прек-

ращается.

Осуществляется возврат в найденное состояние (кроме

случая, когда им является непосредственно то состояние,

в котором встретилась ошибка)

Выполняется действие, заданное в этом состоянии для

лексемы error. Очередной входной лексемой становится

лексема, вызвавшая ошибку.

Разбор продолжается, но анализатор остается в состоянии

ошибки до тех пор, пока не будут успешно прочитаны и

обработаны три подряд идущие лексемы. При нахождении

анализатора в состоянии ошибки отличие в обработке оши-

бочной лексемы заключается в том, что сообщения об

ошибке не выдается, а сама лексема игнорируется.

- 30 -

После обработки трех допустимых лексем считается, что

восстановление произошло, и анализатор выходит из сос-

тояния ошибки.

Итак, грамматический анализатор, встретив ошибку, пыта-

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

лексема error. При этом сначала делается попытка возврата в

рамках правила, по которому шел разбор в момент появления

ошибочноЙ лексемы, затем поиск распространяется на правила

все более высокого уровня. В примере, приведенном в начале

раздела, ввод недопустимой лексемы после того, как прочитана

строка b c d1 d2 вызовет возврат к состоянию, характеризую-

щемуся конфигурациями:

a: b c_d;

a: b c_error;

и продолжение разбора по правилу (2).

Часто правила, учитывающие возможность ошибки, задаются

на уровне основных структурных единиц входного текста. Нап-

ример, для пропуска в тексте ошибочных операторов может быть

использовано правило

оператор: error;

При этом восстановление из состояния ошибки произойдет после

нахождения трех лексем, которые могут следовать после опера-

тора, например, начинать новый оператор. Если точно распоз-

нать начало оператора невозможно, то ошибочное состояние

может быть подавлено преждевременно, а обработка нового опе-

ратора начата с середины ошибочного, что, вероятно, приведет

к повторному сообщению об ошибке (на самом деле не существу-

ющей). Учитывая это, более надежного результата следует ожи-

дать от правил вида:

оператор: error ';'

Здесь восстановление произойдет только после нахождения ";"

и двух начальных лексем следующего оператора; все лексемы

после найденной ошибочной до ";" будут отброшены.

С правилами, включающими лексему error, могут быть свя-

заны действия. С их помощью пользователь может самостоя-

тельно обработать ошибочную ситуацию. Кроме обычных операто-

ров, здесь можно использовать специальные операторы yyerror

и yyclearin, которые yacc на макроуровне расширяет в нужные

последовательности. Оператор yyerror аннулирует состояние

ошибки. Таким образом, можно отменить действие принципа

"трех лексем". Это помогает предотвратить маскирование новых

ошибок в случаях, когда конец ошибочной конструкции распоз-

нается самим пользователем или однозначно определяется в

правиле по меньшему числу лексем.

- 31 -

Оператор yyclearin стирает хранимую анализатором пос-

леднюю входную лексему, если поиск нужной точки для возоб-

новления ввода обеспечивается в заданном пользователем

действии.

Приведем общую форму правила с восстановительным дейст-

вием

оператор : error {resynch();

yyclearin;

yyerror;}

Предполагается, что пользовательская процедура resynch()

просматривает входной поток до начала очередного оператора.

Вызвавшая ошибку лексема, хранимая анализатором в качестве

входной лексемы, стирается, после этого гасится состояние

ошибки.

При построении анализаторов, работающих в интерактивном

режиме, для обработки ошибок рекомендуются правила вида:

входная_строка : error '\n' {yyerrok;

printf("Повторите последнюю строку \n");}

входная_строка {$$=$4;}

В действии, предусмотренном после ввода ошибочной строки,

пользователю делается подсказка, а состояние ошибки гасится.

Значением нетерминала после свертки здесь становится значе-

ние повторно введенной строки.

11. Диагностика ошибок

yacc выдает ряд сообщений об ошибках в случае невозмож-

ности построения грамматического анализатора. В тексте сооб-

щения, предваряемом заголовком "ошибка:", содержится указа-

ние причины ошибки и номер просматриваемой в момент ее появ-

ления строки спецификационного файла. Перечислим основные

типы фиксируемых yacc ошибок:

неверно заданные флаги командной строки;

невозможность открытия входного или временных файлов;

отсутствие файла /usr/lib/yaccpar с текстом процедуры

yyparse;

неверная структура спецификационного файла;

ошибки в задании директив;

синтаксические ошибки в описании грамматических правил,

незавершенность комментариев, строк символов и дейст-

вий;

- 32 -

некорректное использование псевдопеременных;

неопределенные нетерминальные символы;

нарушение количественных ограничений (по числу терми-

нальных или нетерминальных символов, грамматических

правил, состояний и проч.).

- 33 -

Приложение 1

Ниже приведен полный входной файл для yacc, реализующий

небольшой настольный калькулятор; калькулятор имеет 26

регистров, помеченных буквами от a до z и разрешает исполь-

зовать арифметические выражения, содержащие операции +, -,

*, /, % (остаток от деления), & (побитовое и), | (побитовое

или) и присваивание. Как и в Си, целые числа, начинающиеся с

0, считаются восьмеричными, все остальные - десятичными.

В примере демонстрируются способы использования приори-

тетов для разрешения конфликтов, а также простые операции по

восстановлению из состояния ошибки. Калькулятор работает в

интерактивном режиме с построчным формированием выхода.

%token DIGIT LETTER /* имена лексем */

%left '|' /* задание приоритетов */

%left '&' /* операций */

%left '+' '-'

%left '*' '/' '%'

%left UMINUS /* установка приоритета

операции унарный минус */

%{ /* oписания, используемые */

int base, regs[26]; /* в действиях */

%}

%% /* начало секции правил */

list:

| list stat '\n'

| list stat error '\n' {yyerrok; }

stat:

expr {printf("%d\n",$1);}

| LETTER '=' expr {regs[$1]=$3; }

expr:

'(' expr ')' { $$=$2; }

| expr '+' expr { $$=$1+$3; }

| expr '-' expr { $$=$1-$3; }

| expr '*' expr { $$=$1*$3; }

| expr '/' expr { $$=$1/$3; }

| expr '%' expr { $$=$1%$3; }

| expr '&' expr { $$=$1&$3; }

| expr '|' expr { $$=$1|$3; }

| '-' expr %prec UMINUS { $$= -$2; }

| LETTER { $$=regs[$1]; }

| number;

number:

DIGIT { $$=$1; base=10;

if($1==0) base=8; }

- 34 -

| number DIGIT {$$=base*$1+$2; }

%% /* начало секции программ */

/*

* Программа лексического анализа

* для строчных латинских букв

* возвращает LETTER,

* значение yylval от 0 до 25;

* для цифр - DIGIT,

* значение yylval от 0 до 9;

* остальные символы возвращаются

* непосредственно

*/

yylex()

{

int c;

while( (c=getchar()) == ' ' );

if( c>='a' && c<='z' ) {

yylval = c - 'a';

return(LETTER);

}

if( c>='0' && c<='9' ) {

yylval = c - '0';

return(DIGIT);

}

return(c);

}

- 35 -

Приложение 2

Анализ и преобразование в матричную форму входных дан-

ных для задачи линейного программирования.

Входная информация из обычной алгебраической формы:

c1X1+c2X2+...+cnXn -> min(max)

a11x1+a12X2+...+a1nXn=b1

am1X1+am2X2+...+amnXn=bm

преобразуется в матричную:

C: c1 c2 ... cn

A: a11 a12 ... a1n

...

am1 am2 ... amn

B: b1 b2 ... bm

Одновременно изменяются знаки коэффициентов при неизвестных

в ограничениях с отрицательным свободным членом, а также

знаки коэффициентов линейного функционала в случае его мак-

симизации. С иллюстративной целью допускаются некоторые

варианты синтаксической записи. Предусмотрена возможность

повторного задания ошибочных строк.

%token число Xi оптим

%%

злп:функционал '\n' система_ограничений

{final();}

| система_ограничений функционал '\n'

{ final();}

функционал: линейная_функция {stf();}

/* По умолчанию - минимизация */

| оптим '(' линейная_функция ')'

{if($1) conv(); stf();}

Характеристики

Список файлов учебной работы