Смекни!
smekni.com

Проектирование трансляторов (стр. 14 из 31)

да по таблице основных переходов, то прейти к ШАГУ 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 предусматривает воможность описания для отдельных кон-

струкций семантических про-

цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-

матического разбора. В зависимости от характера пользовательских

семантических процедур (интерпретация распознанного фрагмента