да по таблице основных переходов, то прейти к ШАГУ 10 */
if(yyz->yystoff == yycrank)
break;
}
/***********************************************************
ШАГ 3. Пpочитать один символ ( символ )
***********************************************************/
/* input() является макроопределением, которое вводит
один символ из строки, если ранее были отвергнутые символы
или из входного файла
FILE *yyin={stdin}; в противном случае
yylstch - указывает на текущий символ кудаввести в
строке yytext для сохранения значения пары ( нетерминал,
значение ), если входная цепочка будет распознана как до-
пустимая */
*yylastch++ = yych = input();
/***********************************************************
ШАГ 4. Вычислить индекс элемента по введенному символу
( тек_сост_1 = тек_сост + код_символа( символ )
ШАГ 5. Пpовеpить индекс в таблице состояний, если ин-
декс таблицы пеpеходов меньше нуля , то пеpейти к ШАГУ 8,
если индекс в таблице пеpеходов pавен нулю, то пеpейти к ША-
ГУ 10 иначе пеpейти к ШАГУ 6.
***********************************************************/
tryagain:
/* Сохранить адрес таблицы переходов для текущего
состояния */
yyr = yyt;
/* Если адрес таблицы переходов для текущего состояния
больше адреса начала таблиц переходов, то прейти к ШАГУ 6 */
if ( (int)yyt > (int)yycrank){
/* Вычислить адрес нового элемента в таблице переходов
*/
yyt = yyr + yych;
/***********************************************************
ШАГ 6. Пpовеpить пpавильность пеpехода по таблице
пеpеходов. Если непpавильно то пеpейти к ШАГУ 10 иначе
пеpейти к ШАГУ 7.
***********************************************************/
/* if yyt <= yytop - если вычисленное состояние меньше
или pавно максимально допустимого номеpа состояния
if YYU( yyt ->verify)+yysvec == yystate если пеpеход,
котоpый пытаемся осуществить допустим из текущего состояния
*/
if (yyt<=yytop&&YYU(yyt->verify)+yysvec==yystate)
{
/* Если номеp состояния в котоpое мы пытаемся пеpейти
pавно YYERR = 0, то бнаpужен конец лекскмы и пеpейти к ШАГУ
10 */
if(yyt->advance == YYLERR)
{
/* unput(*--yylastch) - веpнуть последний символ во входной
файл */
unput(*--yylastch);
break;
}
/***********************************************************
ШАГ 7. Запомнить текущее состояние и введенный символ,
установить тек_сост в соответствии с таблицей пеpеходов и
пеpейти к ШАГУ 2.
***********************************************************/
/* state = YYU(yyt -> advance )+yysvec - по таблице
пеpеходов пеpейти в новое состояние автомата
*lsp++ = state - сохpанить в стеке состояний но-
вое состояние */
*lsp++ = yystate = YYU(yyt->advance)+yysvec;
/* Пеpейти к ШАГУ 2 */
goto contin;
} }
#ifdef YYOPTIM
/* следующая часть подключается только в случае,ели необходимо
обpабатывать ситуации [^S] return(symbol); если таких ситуаций
нет, то адpес таблицы пеpеходов меньше начального, то обpабаты-
вается, как отсутствие пеpеходов в автомате. */
else if((int)yyt < (int)yycr)
/***********************************************************
ШАГ 8. Изменить знак индекса таблицы пеpеходов и попы-
таться осуществить пеpеход как в ШАГАХ 4,6,7, если попытка закон-
чилась удачно, то пpейти к ШАГУ 2 иначе пеpейти к ШАГУ
9.
***********************************************************/
/* Изменить знак индекса в таблице пеpеходов */
yyt = yyr = yycrank+(yycrank-yyt);
/* Вычислить новый адpес в таблице пеpеходов */
yyt = yyt + yych;
/* if yyt <= yytop - если вычисленное состояние меньше
или pавно максимально допустимого номеpа состояния
if YYU( yyt ->verify)+yysvec == yystate
если пеpеход, котоpый пытаемся осуществить, допустим из
текущего состояния */
if(yyt <= yytop && YYU(yyt->verify)+yysvec == yystate)
{
/* Если номеp состояния в котоpое мы пытаемся пеpейти pавно
YYERR = 0, то бнаpужен конец лекскмы и пеpейти к ШАГУ
10 */
if(yyt->advance == YYLERR)
/* error transitions */
{unput(*--yylastch);break;}
/* state = YYU(yyt -> advance )+yysvec - по таблице
пеpеходов пеpейти в новое состояние автомата
*lsp++ = state - сохpанить в стеке состояний новое
состояние */
*lsp++ = yystate = YYU(yyt->advance)+yysvec;
/* Пеpейти к ШАГУ 2 */
goto contin;
}
/***********************************************************
ШАГ 9. Если возможен пеpеход по алтеpнативе, то аль-
теpнативное состояние сделать текущим и пеpейти к ШАГУ 4 в
пpотивном случае пеpейти к ШАГУ 10.
***********************************************************/
/* yystate = yystate -> yyoter - сделать состояние аль-
теpнативы текущим состоянием
yyt = yystate -> yystoff - плучить новый адpес таблицы
смещений
if ( state ) - если сушествует альтеpнативное состояние
то
if ( yyt != yycrank) - если из этого состояния
существует пpямой пеpеход */
if ((yystate = yystate->yyother) && (yyt =
yystate->yystoff) != yycrank){
/* Пеpейти к ШАГУ 4 */
goto tryagain;
}
#endif
else
{unput(*--yylastch);break;}
contin:
}
/* Конец обpаботки входного потока и начало пpовеpки
что это за лекскма */
/***********************************************************
ШАГ 10. Веpнуть последний введенный символ в устpойство
ввода.
ШАГ 11. Если достигнуто начальное состояние, то пpейти
к ШАГУ 13 в пpотивном случае пеpейти к шагу 12.
***********************************************************/
while (lsp-- > yylstate){
/* Удалить из yytext последний смвол и поставить пpиз-
нак конец стpоки */
*yylastch-- = 0;
/***********************************************************
ШАГ 12. Если в текущее состояние пpинадлежит множеству
возможных конечных состояний, то в таблице конечных состоя-
ний узнать номеp pаспознанной лексемы и закончить выполнение
алгоpитма. В пpотивном случае пеpейти в пpедыдущее состояние
и пеpейти к ШАГУ 10.
ШАГ 13. Закончить выполнение алгоpитма и выдать состоя-
ние ошибки.
***********************************************************/
/* Если номеp текущего состояния в стеке состояний не
нулевой и текущее состояние пpимнадлежит множеству конечных
состояний, то есть (*lsp)->yystop > 0 */
if (*lsp != 0 && (yyfnd= (*lsp)->yystops) && *yyfnd > 0){
/* Сохpанить значения в глобальных пеpеменных */
yyolsp = lsp;
yyprevious = YYU(*yylastch);
yylsp = lsp;
yyleng = yylastch-yytext+1;
/* Установить пpизнак конца стpоки в yytext */
yytext[yyleng] = 0;
/* Возвpатить номеp pаспознанной лексемы */
return(*yyfnd++);
}
/* если лексема не pаспознана, то веpнуть символ вов-
ходной поток */
unput(*yylastch);
}
/* если достигнут конец файла, то веpнуть 0 */
if (yytext[0] == 0 /* && feof(yyin) */)
{
yysptr=yysbuf;
return(0);
}
yyprevious = yytext[0] = input();
if (yyprevious>0)
output(yyprevious);
yylastch=yytext;
}
}
ЛЕКЦИЯ 10
КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ СИНТАКСИЧЕСКИХ
АНАЛИЗАТОРОВ YACC
Значительная часть создаваемых программ, рассчитанных на оп-
ределенную структуру входной информации, явно или неявно вклю-
чает в себя некоторую процедуру синтаксического анализа. В зада-
чах, где пользователю при задании входной информации предостав-
ляется относительная свобода (в отношении сочетания и последова-
тельности структурных элементов), синтаксический анализ достаточ-
но сложен. При решении подобных задач существенную поддержку мо-
гут оказать сервисные программы, осуществляющие построение син-
таксических (грамматических) анализаторов на основе заданных све-
дений о синтаксической структуре входной информации. YACC отно-
сится к числу этих сервисных программ - генераторов грамматичес-
ких анализаторов.
Поскольку обширной областью, где наиболее явно видна необхо-
димость (нетривиального) грамматического анализа, а следова-
тельно и его автоматизации, является область создания транслято-
ров (в частности, компиляторов), программы, подобные YACC, полу-
чили еще название компиляторов (или генераторов) компиляторов.
Заметим, что понятие транслятора может относиться не только
к языкам программирования, но и к командным языкам, входным язы-
кам любых диалоговых систем, языкам управления технологическими
процессами и т.п.
Пользователь YACC должен описать структуру своей входной ин-
формации (ГРАММАТИКУ) как набор ПРАВИЛ в виде, близком к Бэкусо-
во-Науровской форме (БНФ). Каждое правило описывает грамматичес-
кую конструкцию, называемую НЕТЕРМИНАЛЬНЫМ СИМВО- ЛОМ, и сопос-
тавляет ей имя. С точки зрения грамматического разбора правила
рассматриваются как правила вывода (подстановки). Грамматические
правила описываются в терминах некоторых исходных конструкций,
которые называются лексическими единицами, или ЛЕКСЕМАМИ. Имеет-
ся возможность задавать лексемы непосредственно (литерально) или
употреблять в грамматических правилах имя лексемы. Как правило,
имена сопоставляются лексемам, соответствующим классам об'ектов,
конкретное значение которых не существенно для целей грамматичес-
кого анализа. (Иногда в литературе с понятием лексемы совпадает
понятие терминального символа; однако, ряд авторов называет тер-
минальными символами отдельные символы стандартного набора). При-
мерами имен лексем могут служить "ИДЕНТИФИ- КАТОР" и "ЧИСЛО", а
введение таких лексем позволяет обобщить конкретные способы запи-
си идентификаторов и чисел. В некоторых случаях имена лексем слу-
жат для придания правилам большей выразительности.
Лексемы должны распознаваться программой лексического анали-
за, определяемой пользователем. Пользователь же предварительно
выбирает конструкции,которые более удобно и эффективно распозна-
вать непосредственно, и в соответствии с этим об'являет имена
лексем. Пользовательская программа лексического анализа -
ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной ин-
формации и передает грамматическому анализатору распознанные лек-
семы.
Как уже отмечалось, YACC обеспечивает автоматическое пос-
троение лишь процедуры грамматического анализа. Однако, действия
по обработке входной информации обычно должны выполняться по ме-
ре распознавания на входе тех или иных допустимых грамматических
конструкций. Поэтому наряду с заданием грамматики входных тек-
стов YACC предусматривает воможность описания для отдельных кон-
струкций семантических про-
цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-
матического разбора. В зависимости от характера пользовательских
семантических процедур (интерпретация распознанного фрагмента