Страница:
*/
Приоритет правила автоматически определяется приорите-
том последней лексемы в теле правила. Если в секции деклара-
ций для этой лексемы не задан приоритет или если правая
часть правила вообще не содержит лексем, то приоритет пра-
вила не определен. Этот принцип можно отменить явным зада-
нием приоритета правила равным приоритету любой (имеющей
приоритет) лексемы с помощью директивы:
%prec <лексема>
помещенной вслед за правой частью правила (перед точкой с
запятой или действием). Например, правилу:
expr: '-' expr %prec '*';
директива %prec придает приоритет лексемы "*" (лексема "-"
при задании грамматики выражений часто используется для
обозначения унарной и бинарной операций, имеющих разный при-
оритет; с помощью директивЫ %prec унарной операции можно
приписать более высокий приоритет. Иногда, чтобы связать с
правилом приоритет, не совпадающий с приоритетом ни одной
лексемы, вводят псевдолексему, задав ей в секции деклараций
уникальный приоритет, и приписывают приоритет псевдолексемы
правилу. В примере грамматики настольного калькулятора, при-
водимом в приложении, с операцией "унарный минус" связан
приоритет псевдолексемы UMINUS).
- 26 -
Сформулируем теперь полностью используемые yacc правила
разрешения конфликтов сдвиг/свертка на основе информации о
приоритетах и ассоциативности (напомним, что конфликты
свертка/свертка разрешаются только по принципу умолчания):
Если для входной лексемы и правила заданы приоритеты и
эти приоритеты различны, то выбирается действие с боль-
шим приоритетом. Больший приоритет правила вызывает
свертку по нему, больший приоритет лексемы вызывает
сдвиг.
Если приоритеты заданы и совпадают, то принимается во
внимание заданная одновременно с приоритетом ассоциа-
тивность: в случае левой ассоциативности используется
свертка, в случае правой - сдвиг. Отсутствие свойства
ассоциативности (директива %nonassoc) в данном случае
указывает на ошибку во входном тексте и анализатор
воспримет вызвавшую данный конфликт лексему как ошибоч-
ную.
Если не задан приоритет входной лексемы и/или приоритет
правила, то действует принцип разрешения конфликтов по
умолчанию, в результате чего выбирается сдвиг.
Пример грамматики константного выражения, уточненной зада-
нием приоритетов:
%left '+' '-'
%left '*' '/'
%%
expr: CONST
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr;
9. Структура информационного входного файла y.output
Основную часть данного файла составляет описание состо-
яний построенного грамматического анализатора. Информация о
каждом состоянии приводится в следующем порядке:
- Перечень соответствующих данному состоянию конфигураций
грамматики (конфигурация характеризуется определенным
грамматическим правилом и позицией в его правой части,
достигнутой к данному моменту разбора). Каждая конфигу-
рация представляется правилом с отмеченной с помощью
символа подчеркивания "_" распознанной частью (позицией
конфигурации). Например, конфигурация:
expr: expr +_expr
- 27 -
соответствует распознанной при разборе строки по ука-
занному правилу последовательности символов expr+.
- Действия анализатора при вводе в качестве очередного
просматриваемого символа каждой из лексем. Различные
виды действий указываются следующим образом:
<лексема> сдвиг <номер_состояния> -
сдвиг при вводе данной лексемы в состояние с указанным
номером;
<лексема> свертка <номер_правила> -
свертка при вводе лексемы по правилу с указанным номе-
ром;
<лексема> error -
выдача сообщения об ошибке во входных данных ("синтак-
сическая ошибка") и возврат из процедуры грамматичес-
кого анализа с кодом 1 (дальнейший разбор невозможен);
<лексема> accept -
возврат из процедуры грамматического анализа с кодом 0
(успешное завершение разбора). Последняя из строк,
описывающих действия анализатора, содержит вместо ука-
зания лексемы символ "." и сообщает действие, выполняе-
мое анализатором для всех лексем, не перечисленных в
данном состоянии. Часто эта строка имеет вид:
. error
и указывает, что все перечисленные лексемы в данном
состоянии являются недопустимыми.
- Перечень переходов для данного состояния. Каждый пере-
ход задается строкой
<имя_терминала> переход <номер_состояния>
сообщающей, в какое состояние перейдет анализатор после
свертки указанного нетерминала, если его распознавание
было начато из данного состояния.
Кроме того, описанию состояния может предшествовать
информация о конфликтах обнаруженных yacc для этого состоя-
ния и разрешенных по принципу умолчания. Информация о конф-
ликте содержит тип конфликта (св/св или сдв/св), конкурирую-
щие действия анализатора (при этом для сдвига указывается
номер состояния, для свертки - номер правила) и лексему, при
появлении которой возникает данный конфликт. Узнать, какое
- 28 -
из возможных действий будет выполнено анализатором, можно из
описания самого состояния.
Пример описания состояния:
8:Конфликт сдв/св (сдвиг 5,свертка 2) при +
Состояние 8
a:a_+a
a:a+a_ (2)
+ сдвиг 5
. свертка 2
Состоянию 8 здесь соответствуют две различные позиции, дос-
тигнутые при разборе по правилу
a: a '+' a
Kонфликт между сверткой по этому правилу и сдвигом в состоя-
ние 5 при вводе лексемы "+" разрешен в пользу сдвига. Ввод
остальных лексем вызывает свертку.
После описания состояния возможен ряд сообщений о нес-
вернутых правилах (с указанием этих правил), т.е. о прави-
лах, свертка по которым не будет произведена ни в одном из
состояний. Наличие таких правил с большой вероятностью сви-
детельствует о некорректности грамматики.
В конце файла приводится информация статистического
характера о реальном и предельном количестве терминальных и
нетерминальных символов, грамматических правил и состояний.
Фиксируется число конфликтов каждого типа, число различных
действий грамматического анализатора, занимаемый им объем
памяти, приводятся данные об использовании внутренних струк-
тур данных (множеств).
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();}
/* В случае максимизации выполнить conv() */
| линейная_функция '-''>' оптим
{if($4) conv();stf();}
линейная_функция: элем1
| линейная_функция элем ;
элем: знак число Xi {stc($1*$2,$3); }
| знак Xi '*' число { stc($1*$4,$2);}
| знак Xi { stc($1,$2);}
/* Формы записи коэффициентов */
элем1: элем
| число Xi { stc($1,$2);}
| Xi '*' число { stc($3,$1);}
- 36 -
| Xi { stc(1,$1); }
знак: '+' {$$=1; }
| '-' {$$= -1;}
система_ограничений: ограничение '\n'
| система_ограничений ограничение '\n'
| система_ограничений error '\n'
{aclear();yyerrok;
printf("повторите последнюю строку\n");}
/* В случае ошибки: стирание инф. о строке,
восстановление и выдача подсказки */
ограничение: линейная_функция '=' число
{ stcb($3);}
| линейная_функция '=' знак число
{ if($3<0) conv(); stcb($4);}
/* Если bi<0, выполнить conv() */
%%
#include "stdio.h"
#define MAXM 100 /* предельное число */
#define MAXN 100 /* ограничений и перем.*/
int c[MAXN],b[MAXM],a[MAXM+1][MAXN],
,nx,x[MAXN];
/* Лексический анализатор возвращает:
* для целых чисел - число,
* yylval равно знач. числа;
* для идент.вида xi, i=1,2,...XI*
* yylval равно его порядк. номеру;
* для max/min - оптим,
* yylval равно соответственно 1 или 0
*/
yylex() {
char c,i;
while((c=getc(stdin))==' ');
switch(c) {
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9': yylval=c-'0';
while((c=getc(stdin))<='9'&&c>='0')
yylval=yylval*10+c-'0';
ungetc(c,stdin); return(число);
- 37 -
case'm': if((c=getc(stdin))=='i') yylval=0;
else if(c=='a') yylval=1;
else return('m');
while((c=getc(stdin))<='z'&&c>='a');
ungetc(c,stdin); return(оптим);
case'X':
case'x': if((c=getc(stdin))<'0' || c>'9')
return('x');
yylval=0;
while(c<='9'&&c>='0')
{yylval=yylval*10+c-'0';c=getc(stdin);}
ungetc(c,stdin);
for(i=0;i<nx;i++)
if(x[i]==yylval){yylval=i;return(Xi);}
x[nx]=yylval; yylval=nx++;return(Xi);
}
return(c);
}
/* Печать условия задачи в матричной форме */
final() {
char i,j;
printf("c:\n");
for(i=0;i<nx;i++) printf("%8d",c[i]);
printf("\na:\n");
for(i=0;i<neqs;i++) {
for(j=0;j<nx;j++) printf("%8d",a[i][j]);
printf("\n"); }
printf("b:\n");
for(i=0;i<neqs;i++) printf("%8d",b[i]);
}
/* Изменение знаков коэффициентов */
conv() {
char i;
for(i=0;i<nx;i++) a[neqs][i]*=(-1);
}
/* Запоминание коэффициентов функционала */
stf() {
char i;
for(i=0;i<nx;i++)
{ c[i]=a[neqs][i]; a[neqs][i]=0; }
}
/* Запоминание очередного коэффициента */
stc(nmb,adr) {
a[neqs][adr]=nmb; }
/* Запоминание свободного члена */
stcb(nmb) {
b[neqs++]=nmb; }
- 38 -
/* Стирание ошибочной строки*/
aclear(){
char i;
for(i=0;i<nx;i++)
a[neqs][i]=0;
}
- 39 -
Приложение 3
Формальное описание структуры спецификационного файла.
файл_спецификаций:
секция_деклараций '%''%'
'\n' секция_правил '%''%'
'\n' секция_программ
| секция_деклараций '%''%'
'\n' секция_правил ;
секция_деклараций:
| секция_деклараций дир_или_описание
'\n' ;
дир_или_описание:
'%''{''\n'ВНЕШНИЕ_ОПИСАНИЯ
'\n''%''}'
| '%''s''t''a''r''t' ИДЕНТИФИКАТОР
| '%''t''o''k''e''n'список_им_лексем
| ассоциативность список_лексем ;
ассоциативность:
'%''l''e''f''t'
| '%'''r''i''g''h''t'
| '%''n''o''n''a''s''s''o''c' ;
список_им_лексем:
| декл_имени_лексемы
| список_им_лексем
декл_имени_лексемы ;
список_лексем:
декл_лексемы
| список_лексем декл_лексемы ;
декл_имени_лексемы:
ИДЕНТИФИКАТОР
| ИДЕНТИФИКАТОР ЦЕЛОЕ_БЕЗ_ЗНАКА;
декл_лексемы:
декл_лексемы
| декл_литерала;
декл_литерала:
ЛИТЕРАЛ
| ЛИТЕРАЛ ЦЕЛОЕ_БЕЗ_ЗНАКА;
секция_правил:
набор_правил
| '%''{''\n'СИ_ОПЕРАТОРЫ'\n''%''}'
'\n' набор_правил '\n' ;
набор_правил:
правило
| набор_правил ';' правило ;
правило:
левая_часть ':' альтернатива
| правило '|' альтернатива ;
левая_часть: ИДЕНТИФИКАТОР ;
альтернатива:
- 40 -
правая_часть
| правая_часть изм_приор
| правая_часть изм_приор действие
| правая_часть действие ;
правая_часть:
| правая_часть лит_или_идент
| правая_часть действие лит_или_идент;
изм_приор:
секция_программ:
ПРОГРАММНЫЕ_КОМПОНЕНТЫ ;
При описании структуры спецификационного файла не рас-
шифровывались некоторые исходные конструкции, совпадающие с
аналогичными конструкциями Си: идентификатор, литерал, целое
без знака. Не описаны также и более сложные конструкции,
являющиеся фрагментами Си-программ, переносимыми в текст
анализатора (внешние описания, Си-операторы). Под расширен-
ными Си-операторами понимаются операторы с возможным исполь-
зованием псевдопеременных. ПРОГРАММНЫЕ_КОМПОНЕНТЫ включают
операторы препроцессора, описания внешних переменных и функ-
ций (возможный состав их приводится в разделе 4.3).
- 41 -
СОДЕРЖАНИЕ
. Аннотация ......................................... 2
1. Принципы работы yacc .............................. 3
2. Входные и выходные файлы, структура грамматического
анализатора ....................................... 4
3. Процедура построения грамматического анализатора .. 5
4. Задание входной информации yacc ................... 6
4.1. Структура спецификационного файла ............... 6
4.2. Секция правил ................................... 7
4.3. Секция деклараций ............................... 12
5. Декларация имен лексем ............................ 13
6. Декларация приоритетов и ассоциативности лексем ... 13
7. Декларация имени начального символа ............... 15
7.1. Секция программ ................................. 15
7.2. Действия с использованием псевдопеременных ...... 17
8. Конфликты грамматического разбора ................. 20
9. Структура информационного входного файла
y.output .......................................... 27
10. Обработка ошибок при грамматическом разборе ....... 29
11. Диагностика ошибок ................................ 32
Приложение 1 ...................................... 34
Приложение 2 ...................................... 36
Приложение 3 ...................................... 40
- 42 -
Приоритет правила автоматически определяется приорите-
том последней лексемы в теле правила. Если в секции деклара-
ций для этой лексемы не задан приоритет или если правая
часть правила вообще не содержит лексем, то приоритет пра-
вила не определен. Этот принцип можно отменить явным зада-
нием приоритета правила равным приоритету любой (имеющей
приоритет) лексемы с помощью директивы:
%prec <лексема>
помещенной вслед за правой частью правила (перед точкой с
запятой или действием). Например, правилу:
expr: '-' expr %prec '*';
директива %prec придает приоритет лексемы "*" (лексема "-"
при задании грамматики выражений часто используется для
обозначения унарной и бинарной операций, имеющих разный при-
оритет; с помощью директивЫ %prec унарной операции можно
приписать более высокий приоритет. Иногда, чтобы связать с
правилом приоритет, не совпадающий с приоритетом ни одной
лексемы, вводят псевдолексему, задав ей в секции деклараций
уникальный приоритет, и приписывают приоритет псевдолексемы
правилу. В примере грамматики настольного калькулятора, при-
водимом в приложении, с операцией "унарный минус" связан
приоритет псевдолексемы UMINUS).
- 26 -
Сформулируем теперь полностью используемые yacc правила
разрешения конфликтов сдвиг/свертка на основе информации о
приоритетах и ассоциативности (напомним, что конфликты
свертка/свертка разрешаются только по принципу умолчания):
Если для входной лексемы и правила заданы приоритеты и
эти приоритеты различны, то выбирается действие с боль-
шим приоритетом. Больший приоритет правила вызывает
свертку по нему, больший приоритет лексемы вызывает
сдвиг.
Если приоритеты заданы и совпадают, то принимается во
внимание заданная одновременно с приоритетом ассоциа-
тивность: в случае левой ассоциативности используется
свертка, в случае правой - сдвиг. Отсутствие свойства
ассоциативности (директива %nonassoc) в данном случае
указывает на ошибку во входном тексте и анализатор
воспримет вызвавшую данный конфликт лексему как ошибоч-
ную.
Если не задан приоритет входной лексемы и/или приоритет
правила, то действует принцип разрешения конфликтов по
умолчанию, в результате чего выбирается сдвиг.
Пример грамматики константного выражения, уточненной зада-
нием приоритетов:
%left '+' '-'
%left '*' '/'
%%
expr: CONST
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr;
9. Структура информационного входного файла y.output
Основную часть данного файла составляет описание состо-
яний построенного грамматического анализатора. Информация о
каждом состоянии приводится в следующем порядке:
- Перечень соответствующих данному состоянию конфигураций
грамматики (конфигурация характеризуется определенным
грамматическим правилом и позицией в его правой части,
достигнутой к данному моменту разбора). Каждая конфигу-
рация представляется правилом с отмеченной с помощью
символа подчеркивания "_" распознанной частью (позицией
конфигурации). Например, конфигурация:
expr: expr +_expr
- 27 -
соответствует распознанной при разборе строки по ука-
занному правилу последовательности символов expr+.
- Действия анализатора при вводе в качестве очередного
просматриваемого символа каждой из лексем. Различные
виды действий указываются следующим образом:
<лексема> сдвиг <номер_состояния> -
сдвиг при вводе данной лексемы в состояние с указанным
номером;
<лексема> свертка <номер_правила> -
свертка при вводе лексемы по правилу с указанным номе-
ром;
<лексема> error -
выдача сообщения об ошибке во входных данных ("синтак-
сическая ошибка") и возврат из процедуры грамматичес-
кого анализа с кодом 1 (дальнейший разбор невозможен);
<лексема> accept -
возврат из процедуры грамматического анализа с кодом 0
(успешное завершение разбора). Последняя из строк,
описывающих действия анализатора, содержит вместо ука-
зания лексемы символ "." и сообщает действие, выполняе-
мое анализатором для всех лексем, не перечисленных в
данном состоянии. Часто эта строка имеет вид:
. error
и указывает, что все перечисленные лексемы в данном
состоянии являются недопустимыми.
- Перечень переходов для данного состояния. Каждый пере-
ход задается строкой
<имя_терминала> переход <номер_состояния>
сообщающей, в какое состояние перейдет анализатор после
свертки указанного нетерминала, если его распознавание
было начато из данного состояния.
Кроме того, описанию состояния может предшествовать
информация о конфликтах обнаруженных yacc для этого состоя-
ния и разрешенных по принципу умолчания. Информация о конф-
ликте содержит тип конфликта (св/св или сдв/св), конкурирую-
щие действия анализатора (при этом для сдвига указывается
номер состояния, для свертки - номер правила) и лексему, при
появлении которой возникает данный конфликт. Узнать, какое
- 28 -
из возможных действий будет выполнено анализатором, можно из
описания самого состояния.
Пример описания состояния:
8:Конфликт сдв/св (сдвиг 5,свертка 2) при +
Состояние 8
a:a_+a
a:a+a_ (2)
+ сдвиг 5
. свертка 2
Состоянию 8 здесь соответствуют две различные позиции, дос-
тигнутые при разборе по правилу
a: a '+' a
Kонфликт между сверткой по этому правилу и сдвигом в состоя-
ние 5 при вводе лексемы "+" разрешен в пользу сдвига. Ввод
остальных лексем вызывает свертку.
После описания состояния возможен ряд сообщений о нес-
вернутых правилах (с указанием этих правил), т.е. о прави-
лах, свертка по которым не будет произведена ни в одном из
состояний. Наличие таких правил с большой вероятностью сви-
детельствует о некорректности грамматики.
В конце файла приводится информация статистического
характера о реальном и предельном количестве терминальных и
нетерминальных символов, грамматических правил и состояний.
Фиксируется число конфликтов каждого типа, число различных
действий грамматического анализатора, занимаемый им объем
памяти, приводятся данные об использовании внутренних струк-
тур данных (множеств).
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();}
/* В случае максимизации выполнить conv() */
| линейная_функция '-''>' оптим
{if($4) conv();stf();}
линейная_функция: элем1
| линейная_функция элем ;
элем: знак число Xi {stc($1*$2,$3); }
| знак Xi '*' число { stc($1*$4,$2);}
| знак Xi { stc($1,$2);}
/* Формы записи коэффициентов */
элем1: элем
| число Xi { stc($1,$2);}
| Xi '*' число { stc($3,$1);}
- 36 -
| Xi { stc(1,$1); }
знак: '+' {$$=1; }
| '-' {$$= -1;}
система_ограничений: ограничение '\n'
| система_ограничений ограничение '\n'
| система_ограничений error '\n'
{aclear();yyerrok;
printf("повторите последнюю строку\n");}
/* В случае ошибки: стирание инф. о строке,
восстановление и выдача подсказки */
ограничение: линейная_функция '=' число
{ stcb($3);}
| линейная_функция '=' знак число
{ if($3<0) conv(); stcb($4);}
/* Если bi<0, выполнить conv() */
%%
#include "stdio.h"
#define MAXM 100 /* предельное число */
#define MAXN 100 /* ограничений и перем.*/
int c[MAXN],b[MAXM],a[MAXM+1][MAXN],
,nx,x[MAXN];
/* Лексический анализатор возвращает:
* для целых чисел - число,
* yylval равно знач. числа;
* для идент.вида xi, i=1,2,...XI*
* yylval равно его порядк. номеру;
* для max/min - оптим,
* yylval равно соответственно 1 или 0
*/
yylex() {
char c,i;
while((c=getc(stdin))==' ');
switch(c) {
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9': yylval=c-'0';
while((c=getc(stdin))<='9'&&c>='0')
yylval=yylval*10+c-'0';
ungetc(c,stdin); return(число);
- 37 -
case'm': if((c=getc(stdin))=='i') yylval=0;
else if(c=='a') yylval=1;
else return('m');
while((c=getc(stdin))<='z'&&c>='a');
ungetc(c,stdin); return(оптим);
case'X':
case'x': if((c=getc(stdin))<'0' || c>'9')
return('x');
yylval=0;
while(c<='9'&&c>='0')
{yylval=yylval*10+c-'0';c=getc(stdin);}
ungetc(c,stdin);
for(i=0;i<nx;i++)
if(x[i]==yylval){yylval=i;return(Xi);}
x[nx]=yylval; yylval=nx++;return(Xi);
}
return(c);
}
/* Печать условия задачи в матричной форме */
final() {
char i,j;
printf("c:\n");
for(i=0;i<nx;i++) printf("%8d",c[i]);
printf("\na:\n");
for(i=0;i<neqs;i++) {
for(j=0;j<nx;j++) printf("%8d",a[i][j]);
printf("\n"); }
printf("b:\n");
for(i=0;i<neqs;i++) printf("%8d",b[i]);
}
/* Изменение знаков коэффициентов */
conv() {
char i;
for(i=0;i<nx;i++) a[neqs][i]*=(-1);
}
/* Запоминание коэффициентов функционала */
stf() {
char i;
for(i=0;i<nx;i++)
{ c[i]=a[neqs][i]; a[neqs][i]=0; }
}
/* Запоминание очередного коэффициента */
stc(nmb,adr) {
a[neqs][adr]=nmb; }
/* Запоминание свободного члена */
stcb(nmb) {
b[neqs++]=nmb; }
- 38 -
/* Стирание ошибочной строки*/
aclear(){
char i;
for(i=0;i<nx;i++)
a[neqs][i]=0;
}
- 39 -
Приложение 3
Формальное описание структуры спецификационного файла.
файл_спецификаций:
секция_деклараций '%''%'
'\n' секция_правил '%''%'
'\n' секция_программ
| секция_деклараций '%''%'
'\n' секция_правил ;
секция_деклараций:
| секция_деклараций дир_или_описание
'\n' ;
дир_или_описание:
'%''{''\n'ВНЕШНИЕ_ОПИСАНИЯ
'\n''%''}'
| '%''s''t''a''r''t' ИДЕНТИФИКАТОР
| '%''t''o''k''e''n'список_им_лексем
| ассоциативность список_лексем ;
ассоциативность:
'%''l''e''f''t'
| '%'''r''i''g''h''t'
| '%''n''o''n''a''s''s''o''c' ;
список_им_лексем:
| декл_имени_лексемы
| список_им_лексем
декл_имени_лексемы ;
список_лексем:
декл_лексемы
| список_лексем декл_лексемы ;
декл_имени_лексемы:
ИДЕНТИФИКАТОР
| ИДЕНТИФИКАТОР ЦЕЛОЕ_БЕЗ_ЗНАКА;
декл_лексемы:
декл_лексемы
| декл_литерала;
декл_литерала:
ЛИТЕРАЛ
| ЛИТЕРАЛ ЦЕЛОЕ_БЕЗ_ЗНАКА;
секция_правил:
набор_правил
| '%''{''\n'СИ_ОПЕРАТОРЫ'\n''%''}'
'\n' набор_правил '\n' ;
набор_правил:
правило
| набор_правил ';' правило ;
правило:
левая_часть ':' альтернатива
| правило '|' альтернатива ;
левая_часть: ИДЕНТИФИКАТОР ;
альтернатива:
- 40 -
правая_часть
| правая_часть изм_приор
| правая_часть изм_приор действие
| правая_часть действие ;
правая_часть:
| правая_часть лит_или_идент
| правая_часть действие лит_или_идент;
изм_приор:
секция_программ:
ПРОГРАММНЫЕ_КОМПОНЕНТЫ ;
При описании структуры спецификационного файла не рас-
шифровывались некоторые исходные конструкции, совпадающие с
аналогичными конструкциями Си: идентификатор, литерал, целое
без знака. Не описаны также и более сложные конструкции,
являющиеся фрагментами Си-программ, переносимыми в текст
анализатора (внешние описания, Си-операторы). Под расширен-
ными Си-операторами понимаются операторы с возможным исполь-
зованием псевдопеременных. ПРОГРАММНЫЕ_КОМПОНЕНТЫ включают
операторы препроцессора, описания внешних переменных и функ-
ций (возможный состав их приводится в разделе 4.3).
- 41 -
СОДЕРЖАНИЕ
. Аннотация ......................................... 2
1. Принципы работы yacc .............................. 3
2. Входные и выходные файлы, структура грамматического
анализатора ....................................... 4
3. Процедура построения грамматического анализатора .. 5
4. Задание входной информации yacc ................... 6
4.1. Структура спецификационного файла ............... 6
4.2. Секция правил ................................... 7
4.3. Секция деклараций ............................... 12
5. Декларация имен лексем ............................ 13
6. Декларация приоритетов и ассоциативности лексем ... 13
7. Декларация имени начального символа ............... 15
7.1. Секция программ ................................. 15
7.2. Действия с использованием псевдопеременных ...... 17
8. Конфликты грамматического разбора ................. 20
9. Структура информационного входного файла
y.output .......................................... 27
10. Обработка ошибок при грамматическом разборе ....... 29
11. Диагностика ошибок ................................ 32
Приложение 1 ...................................... 34
Приложение 2 ...................................... 36
Приложение 3 ...................................... 40
- 42 -