Реферат: Проектирование трансляторов
***********************************************************/
/* 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 предусматривает воможность описания для отдельных кон-
струкций семантических про-
цедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам-
матического разбора. В зависимости от характера пользовательских
семантических процедур (интерпретация распознанного фрагмента
входного текста, генерация фрагмента об'ектного кода, отметка в
справочной таблице или форматирование вершины в дереве разбора)
генерируемая с помощью YACC программа будет обеспечивать кроме
анализа тот или иной вид обработки входного текста, в частности,
его компиляцию или интерпретацию.
Итак, пользователь YACC подготавливает общее описание
(СПЕЦИФИКАЦИИ) обработки входного потока, включающее правила,
описывающие входные конструкции, кодовую часть, к которой должно
быть организовано обращение при обнаружении этих конструкций, и
программу ввода базовых элементов потока (лексический
анализатор). Kомпилятор компиляторов обеспечивает создание под-
программы (грамматического анализатора), реализующей процедуру
обработки входного потока в соответствии с заданными специфика-
циями.
К компонентам компилятора компиляторов относятся выполняе-
мый файл yacc, библиотека стандартных программ /lib/liby.a, Файл
/usr/lib/yaccpar. Заключительная фаза построения компилятора тре-
бует применения компилятора языка Си.
ПРИНЦИПЫ РАБОТЫ YACC
Грамматические анализаторы, создаваемые с помощью YACC, реа-
лизуют так называемый LALR(1)-разбор, являющийся модификацией од-
ного из основных методов разбора "снизу вверх" - LR(k)-разбора
(буквы L(eft) и R(ight) в обоих сокращениях означают соответ-
ственно чтение входных символов слева направо и использование
правостороннего вывода. Индекс в скобках показывает число предва-
рительно просматриваемых лексических единиц).
Любой разбор по принципу "снизу вверх" (или восходящий раз-
бор) состоит в попытке приведения всей совокупности входных дан-
ных (входной цепочки) к так называемому "начальному символу грам-
матики" путем последовательного применения правил вывода.
В каждый момент грамматического разбора анализатор находит-
ся в некотором СОСТОЯНИИ, определяемом предысторией разбора, и в
зависимости от очередной лексемы предпринимает то или иное дей-
ствие для перехода к новому состоянию. Различают два типа дей-
ствий: "СДВИГ", т.е. чтение следующей входной лексемы, и
"СВЕРТКУ", т.е. применение одного из правил подстановки для заме-
щения нетерминалом последовательности символов, соответствующей
правой части правила. Работа YACC по генерации процедуры грамма-
тического анализа заключается в построении таблиц, которые для
каждого из состояний определяют тип действий анализатора и номер
следующего состояния в соответствии с каждой из входных лексем.
Любой метод разбора требует грамматик с определенными свой-
ствами. В этом смысле YACC предполагает контекстносвободные грам-
матики со свойствами LALR(1). LALR(1)- грамматики, являясь под-
множеством LR(1)-грамматик, допускают при построении таблиц раз-
бора сокращение общего числа состояний за счет об'единения иден-
тичных состояний, различающихся только набором символов-следова-
телей (символов, которые могут следовать после применения одного
из правил вывода, если разбор по этому правилу проходил через
данное состояние). Другие грамматики являются неоднозначными для
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
