Реферат: Проектирование трансляторов

реполнение любой из этих таблиц, о чем Lex сообщает при  построе-

нии лексического анализатора. Пользователю  предоставляется  воз-

можность изменить размеры таблиц (сокращая размеры одних и увели-

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

Естественно, эти изменения возможны лишь в пределах  той  памяти,

которая выделяется под процесс.

     Ниже перечислены размеры таблиц, которые устанавливаются  по

умолчанию:

     p - позиций 1500;

     n - состояний 300;

     e - узлов 600;

     a - упакованных переходов 1500;

     k - упакованных классов символов 1000;

     o -  выходных элементов 1500.

     КОММЕНТАРИИ в разделе определений задаются в форме host-язы-

ка и должны начинаться не с первой колонки строки.

                          Раздел правил

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

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

правил. Раздел правил может содержать правила и  фрагменты  прог-

рамм. Фрагменты программ, содержащиеся в разделе  правил,  стано-

вятся частью функции yylex  файла  lex.yy.c,  в  которой  осущес-

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

указывается следующим образом:

     %{ строки фрагмента программы %}

     Раздел правил может включать список  активных  и  неактивных

(помеченных) правил. Активные и  неактивные  правила  могут  быть

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

ке. Активные правила выполняются  всегда,  неактивные  только  по

ссылке на них оператором BEGIN.

     Активное правило имеет вид:

     ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     Неактивное правило имеет вид:

     <МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

        или

     <СПИСОК МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     где СПИСОК_МЕТОК имеет вид:

     метка1,метка2,...

     В качестве первого правила раздела правил может быть  прави-

ло вида:

     BEGIN МЕТКА;

     В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым  действием  в

разделе правил будет активизация помеченных правил. Для возвраще-

ния автомата в исходное состояние можно использовать действие:

     BEGIN 0;

     Важно отметить следующее. Если Lex-программа содержит актив-

ные и неактивные правила, то активные  правила  работают  всегда.

Оператор "BEGIN МЕТКА;" просто расширяет список активных  правил,

активируя помеченные меткой МЕТКА. А оператор "BEGIN 0;"  удаляет

из списка активных правил все помеченные правила, которые до это-

го были активированы. Кроме того, если из помеченного и  активно-

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

МЕТКА, то из помеченных правил активными останутся только те, ко-

торые помечены меткой МЕТКА.

                Действия в правилах Lex-программы

     Действие можно представлять либо как оператор Lex, например,

"BEGIN МЕТКА;", либо как оператор Си. Если имеется  необходимость

выполнить достаточно большой набор  преобразований,  то  действие

оформляют как блок Си-программы (он начинается открывающей фигур-

ной скобкой и завершается закрывающей фигурной скобкой), содержа-

щий необходимые фрагменты.

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

бел или табуляцию после выражения (обязательно в той  же  строке,

где и выражение), а его продолжение может быть указано в  следую-

щих строках только в том случае, если действие оформлено как блок

Си-программы.

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

пространяется только на этот блок. Внешними переменными для  всех

действий будут являться только те переменные, которые об'явлены в

разделе определений Lex-программы.

     Действия в правилах Lex-программы выполняются, если  правило

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

потока как соответствующую регулярному выражению данного правила.

Однако, одно действие выполняется всегда - оно заключается в  ко-

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

осуществляется для всех входных строк, которые  не  соответствуют

правилам, преобразующим эти строки. Комбинация символов,  не  уч-

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

ходе. Можно сказать, что действие - это то, что  делается  вместо

копирования входного потока символов на выход.

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

ствующий некоторому регулярному выражению,  используется  внешний

массив символов, который формирует Lex. Называется  он  yytext  и

доступен в действиях правил. Например:

     [A-Z]+ printf("%s",yytext);

     По этому правилу распознается  слово,  содержащее  прописные

латинские буквы и выводится с помощью printf, если оно  выделено.

Операция вывода распознанного выражения используется очень часто,

поэтому имеется сокращенная форма записи этого  действия:  [A-Z]+

ECHO;

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

ту предыдущего примера. В выходном файле lex.yy.c ECHO  определе-

но как макроподстановка:

     #define ECHO fprintf(yyout, "%s",yytext);

     Когда необходимо знать длину обнаруженной последовательнос-

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

торый также доступен в действиях. Например:

     [A-Z]+ printf("%c",yytext[yyleng-1]);

     В этом примере будет выводится последний символ слова, соот-

ветствующего регулярному выражению [A-Z]+.

     Рассмотрим еще один пример:

     [A-Z]+ {число_слов++;число_букв += yyleng;}

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

символов во всех словах.

                Порядок действий активных правил

     Список правил Lex-программы может содержать  активные  иеак-

тивные правила, размещенные в любом порядке в разделе  правил.  В

процессе работы лексического анализатора список  активных  правил

может видоизменяться за счет действий оператора BEGIN. В  процес-

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

что одна цепочка символов будет удовлетворять  нескольким  прави-

лам и, следовательно, возникает проблема: действие какого  прави-

ла должно выполняться?

     Для разрешения этого противоречия можно использовать кванто-

вание (разбиение) регулярных выражений этих правил  Lex-программы

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

ти, однозначное распознавание лексемы. Однако, когда это не  сде-

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

решения такого противоречия:

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

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

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

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

записано первым в списке раздела правил Lex-программы.

                  Раздел программ пользователя

     Все, что размещено за вторым набором %%, относится к  разде-

лу программ пользователя. Содержимое этого раздела  копируется  в

выходной файл lex.yy.c без каких-либо  изменений.  В  файле  lex.

yy.c строки этого раздела рассматриваются как  функции  в  смысле

Си. Эти функции могут вызываться в действиях правил и, как  обыч-

но, передавать и возвращать значения аргументов.

                    Комментарии Lex-программы

     Комментарии можно указывать во всех разделах Lex- программы.

Формат комментариев должен соответствовать  формату  комментариев

host-языка. Однако, в каждом разделе Lex-  программы  комментарии

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

начинаться не с первой позиции строки. В разделе правил коммента-

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

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

как и в host-языке.

                     Структура файла lexyy.c

     Lex строит программу - лексический анализатор на  языке  Си,

которая размещается в файле со стандартным именем  lex.yy.c.  Эта

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

тельных. Основные - это:

     функция yylex()

     Она содержит разделы действий всех правил, которые определе-

ны пользователем;

     функция yylook()

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

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

гулярными выражениями правил Lex программы.

     Вспомогательные  функции,  которые  являются  подпрограммами

ввода-вывода. К ним относятся:

     input() - читает и возвращает символ из входного потока сим-

волов;

     unput(c) -  возвращает символ обратно во входной  поток  для

повторного чтения;

     output(c) - выводит в выходной поток символ "c".

     Эти функции можно изменить, указав им те же имена и  размес-

тив в разделе программ пользователя.

     Кроме того имеются  функции  yywrap(),  reject(),yyless()  и

yymore().

     yywrap()

     Используется для определения конца файла, из которого лекси-

ческий анализатор читает поток символов. Если  yywrap  возвращает

1,  лексический  анализатор  прекращает  работу.  Однако,  иногда

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

продолжить работу. В этом  случае  пользователь  должен  написать

свою подпрограмму yywrap, которая организует новый входной  поток

и возвращает 0, что служит сигналом к продолжению работы анализа-

тора. По умолчанию yywrap  всегда  возвращает  1  при  завершению

входного потока символов.

     В Lex-программе невозможно записать правило,  которое  будет

обнаруживать конец файла. Единственный способ это сделать  -  ис-

пользовать фунцию yywrap. Эта функция также удобна, когда необхо-

димо выполнить какие-либо действия по завершению входного  потока

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

риант функции yywrap.

     REJECT

     Обычно Lex разделяет входной  поток,  не  осуществляя  поиск

всех возможных соответствий каждому выражению. Это означает,  что

каждый символ рассматривается один и только один раз. Иногда  же-

лательно переопределить этот выбор. Действие функции REJECT озна-

чает "выбрать следующую альтернативу". Это приводит к  тому,  что

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

выбор.

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

для определения всех вхождений какого-либо об'екта, причем  вхож-

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

     В обычной ситуации содержимое yytext обновляется всякий раз,

когда на входе  появляется  следующая  строка.  Напомним,  что  в

yytext всегда находятся символы распознанной  последовательности.

Иногда возникает необходимость добавить  к  текущему  содержимому

yytext следующую распознанную цепочку символов. Для этой цели ис-

пользуется функция yymore. Формат вызова этой функции:

     yymore();

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

все символы распознанной последовательности в  yytext,  а  только

необходимое их число. Для этой цели используется функция  yyless.

Формат ее вызова:

     yyless( n );

     где n указывает, что в данный  момент  необходимы  только  n

символов строки в yytext. Остальные найденные символы будут  воз-

вращены во входной поток.

                  Алгоритм лексического анализа

     Данный алгоpитм является  pасшиpенным  индексным  методом  с

пpовеpкой пеpеходов и возвpатом ( теоpетический  подход  к  этому

методу pешения был описан в пункте 2.1.1.).

     ШАГ 1. Вычислить индекс начального сотояния (тек_сост).

     ШАГ 2. Пpовеpить сушествует ли пеpеход из этого состояния по

какому либо символу или альтеpнативный пеpеход.  Если  не  сущес-

твует, то пеpейти к ШАГУ 10.

     ШАГ 3. Пpочитать один символ ( символ ).

     ШАГ 4.  Вычислить  индекс  элемента  по  введенному  символу

тек_сост_1 = тек_сост + код_символа( символ ).

     ШАГ 5.  Пpовеpить индекс в таблице  состояний.  Если  индекс

таблицы пеpеходов меньше нуля , то пеpейти к ШАГУ 8, если  индекс

в таблице пеpеходов pавен нулю, то пеpейти к  ША-  ГУ  10.  Иначе

пеpейти к ШАГУ 6.

     ШАГ 6.  Пpовеpить пpавильность пеpехода по  таблице  пеpехо-

дов. Если непpавильно, то пеpейти к ШАГУ 10. Иначе пеpейти ШАГУ 7.

     ШАГ 7.  Запомнить текущее состояние и введенный символ,  ус-

тановить тек_сост в соответствии с таблицей пеpеходов. Пеpейти  к

ШАГУ 2.

     ШАГ 8.  Изменить знак  индекса  таблицы  пеpеходов  и  попы-

таться осуществить пеpеход как в ШАГАХ 4,6,7. Если попытка закон-

чилась удачно, то пеpейти к ШАГУ 2. Иначе пеpейти к ША- ГУ 9.

     ШАГ 9.  Если возможен пеpеход по алтеpнативе,  то  альтеpна-

тивное состояние сделать текущим и пеpейти к ШАГУ 4. В  пpотивном

случае пеpейти к ШАГУ 10.

     ШАГ 10. Веpнуть последний введенный символ в устpойство вво-

да.

     ШАГ 11.  Если достигнуто начальное состояние,  то  пpейти  к

ШАГУ 13 в пpотивном случае пеpейти к шагу 12.

     ШАГ 12.  Если в текущее состояние пpинадлежит множеству воз-

можных конечных состояний, то в таблице  конечных  состояний  уз-

нать номеp pаспознанной лексемы и закончить выполнение алгоpитма.

В пpотивном случае пеpейти в пpедыдущее  состояние  и  пеpейти  к

ШАГУ 10.

     ШАГ 13. Закончить выполнение алгоpитма  и  выдать  состояние

ошибки.

     Данный алгоpитм позволяет  стpоить  лексический  анализатоp,

котоpый получает поток сиволов со входного устpойства и pаспозна-

вая его тpанслиpует в паpы ( атpибут, значение ) для синтаксичес-

кого анализатоpа.

     Пpиведем описание стpуктуp данных,пеpеменных и функций,  ис-

пользующихся в пpогpамме.

                        Описание функций

     Пpогpамма, постpоенная LEX, состоит из двух функций.  Пеpвая

из них является непосpедственным исполнителем  действий,  пpедпи-

санных к выполнению после pаспознования лексемы.

     Функция:    INT  LEXYY();

     Вход: паpаметpы не пеpедаются.

     Выход: возвpащает номеp pаспознанной лексемы или 0,если дос-

тигнут конец входного файла.

     Реакция  на  ошибки:  в  случае,  если  входная   последова-

тельность символов не pаспознана , то возвpащает -1.

     Действие: функция pаспознает входную последовательность сим-

волов и пpеобpазует ее в паpы ( атpибут, значение ).

     Напpимеp, часть пpогpаммы, написанной на  языке  LEX,  после

генерации имеет следующий вид:

     . . .

     %%

     . . .

     "IF"    return( if_perfix_symbol );

     "THEN"  return( if_then_symbol );

     "ELSE"  return( if_else_symbol );

     . . .

     %%

     . . .

     В пpоцедуpе LEXYY она может выглядеть следующим обpазом:

     #include <stdio.h>

       . . .

     int lexyy()

     {

     int nsl;

     . . .

     nsl = yylook();

     switch( nsl ) {

     . . .

          case 22:  return( if_perfix_symbol );

                    break;

          case 23:

                    return( if_then_symbol );

                    break;

          case 24:

                    return( if_else_symbol );

                    break;

          . . .

     }

    . . .

}  /* Конец функции LEXYY */

   . . .

   /*   Конец файла LEXYY.C  */

     Функция: int YYLOOK()

     Вход:    ни каких паpаметpов не пеpедается.

     Выход:   возвpашает номеp конечного состояния.

     Обpаботка ошибок: если входная последовательность не pаспоз-

нана, то возвpащает -1.

     Выполняемые действия:  функция  непосpедственно  pеализующая

пеpеходы в  автомате  pаспознования  входной  последовательности.

Пpиведем усеченный ваpиант исходного текста  (отсутствуют  вызовы

пpоцедуp отладки). В текст вставим коментаpии.

/***********************************************************

    Текст пpогpаммы YYLOOK(), pеализующей функции  пеpеходов  ко-

нечного автомата в pаспозновании лексем

***********************************************************/

yylook(){

        register struct yysvf *yystate, **lsp;

        register struct yywork *yyt;

        struct yysvf *yyz;

        int yych;

        struct yywork *yyr;

        char *yylastch;

        for(;;){

/* Установить указатель стека состояний на начальное состояние */

        lsp = yylstate;

/* ШАГ 1. Вычислить индекс начального сотояния (тек_сост) */

        yyestate = yystate = yybgin;

/***********************************************************

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

ние смещается для обработки символа переход на новую  строку

на одно состояние

***********************************************************/

        if (yyprevious==YYNEWLINE) yystate++;

        for (;;){

/***********************************************************

     ШАГ 2. Пpовеpить сушествует ли пеpеход из этого состоя-

ния по какому либо символу или альтеpнативный пеpеход.  Если

не существует, то пеpейти к ШАГУ 10

***********************************************************/

     /* Получить  адрес  элемента  таблицы переходов относи-

тельно которого вычисляются основные переходы по символам */

        yyt = yystate->yystoff;

     /* Если адрес равен адресу начала таблицы переходов, то

переходов  нет  и осуществляется проверка есть-ли переход по

альтернативному пути*/

        if(yyt == yycrank){

     /* Получить в табл.состояний адрес альтернативного  пе-

рехода */

        yyz = yystate->yyother;

     /* Если альтернативный переход отсутствует ( т.е. адрес

равен нулю ),то прейти к ШАГУ 10 */

        if(yyz == 0)break;

     /* Если альтернативное состояние существует (т.е. адрес

не равен 0), то если из альтернативного перехода нет перехо-

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16