
            дддд   ееееее   м     м    oooo     сссс
           д   д   е        мм   мм   o    o   с    с
          д    д   е        м м м м   o    o   с    с
          д    д   еееее    м  м  м   o    o   с
          д    д   е        м     м   o    o   с
          д    д   е        м     м   o    o   с    с
         дддддддд  ееееее   м     м    oooo     сссс



          демосдемосдемосдемосдемосдемосдемосдемосде
          емосдемосдемосдемосдемосдемосдемосдемосдем
          мо                                      мо
          ос                                      ос
          сд        ОПЕРАЦИОННАЯ СИСТЕМА          сд
          де                                      де
          ем               ДЕМОС                  ем
          мо                                      мо
          ос                                      ос
          сд                                      сд
          де             Версия 1.0               де
          ем                                      ем
          мо                                      мо
          сдемосдемосдемосдемосдемосдемосдемосдемосд
          демосдемосдемосдемосдемосдемосдемосдемосде







                  LEX - ГЕНЕРАТОР ПРОГРАММ
                    ЛЕКСИЧЕСКОГО АНАЛИЗА






                  Давидов Михаил Изгияевич
                 Антонов Вадим Геннадьевич











                       МОСКВА - 1985









                                                           1







   В документе описан язык программирования Lex,  предназна-
ченный  для разработки программ лексического анализа. Приво-
дятся правила работы с компилятором языка Lex ОС ДЕМОС.
























































2




                        1. Введение


   Lex - генератор программ лексического анализа.  Лексичес-
кий анализ - это распознавание лексем во входном потоке сим-
волов. Предположим, что задано некоторое конечное  множество
слов  (лексем)  в некотором языке и некоторое входное слово.
Необходимо установить, какой элемент множества (если он  су-
ществует) совпадает с данным входным словом.

   Обычно лексический анализ выполняется так называемым лек-
сическим анализатором. Лексический анализатор - это програм-
ма.

   Лексический анализ применяется во многих случаях,  напри-
мер,  для построения пакетного редактора или в качестве рас-
познавателя директив в диалоговой программе и  т.д.  Однако,
наиболее  важное  применение  лексического анализатора - это
использование его в компиляторе. Здесь лексический  анализа-
тор выполняет функцию программы ввода данных.

   Лексический анализатор выполняет первую стадию компиляции
-  читает строки компилируемой программы, выделяет лексемы и
передает их на дальнейшие стадии компиляции  (грамматический
разбор, кодогенерацию и т.д.).

   Лексический анализатор распознает тип  каждой  лексемы  и
соответствующимобразом помечает ее. Например, при компиляции
Си-программы могут  быть  выделены  следующие  типы  лексем:
число, идентификатор, оператор, ограничитель и т.д.

   Лексический анализатор должен не только выделить лексему,
но и выполнить некоторые преобразования. Например, если лек-
сема - число, то  его  необходимо  перевести  во  внутреннюю
(двоичную)  форму  записи как число с плавающей или фиксиро-
ванной точкой. А если лексема - идентификатор, то его  необ-
ходимо разместить в таблице, чтобы в дальнейшем обращаться к
нему не по имени, а по адресу в таблице.

   Хотя лексический анализ по своей идее прост, тем не менее
эта  фаза  работы компилятора часто занимает больше времени,
чем любая другая. Частично это происходит из-за необходимос-
ти  просматривать  и  анализировать исходный текст символ за
символом. Иногда даже бывает необходимо вернуть  прочитанный
символ  во  входной  поток с тем, чтобы повторить просмотр и
анализ.

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

   Допустим имеется две лексемы:

        make
        makefile

Пусть из входного потока поступает набор символов:





                                                           3

        ...makefile...

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

   Единственный способ преодолеть это затруднение - просмотр
полученной  цепочки символов назад и вперед. В нашем примере
при выделении лексемы make мы должны  просмотреть  следующий
поступающий  символ и, если он будет символом "f", то вполне
возможно, что поступает лексема makefile.

   Процесс просмотра входного потока можно рассматривать как
движение  влево  и  вправо  рамки над цепочкой символов. При
этом  анализируется  только  тот  символ,  который   охвачен
рамкой.

               ...
               . .
   source  make.f.ile file compiler
               . .
               ...
    <===                      ===>

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

   Например, регулярное выражение

        (\+?[0-9])+|(-?[0-9])+

позволяет выделить в цепочке все лексемы типа  целое,  перед
которыми  либо  указан  знак  (+ или -), либо не указан. Для
чисел с точкой это выражение имело бы вид:

        (\+?[0-9.])+|(-?[0-9.])+

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

   Lex - частично или полностью автоматизирует процесс напи-
сания программы лексического анализа. Lex - это программиру-
ющая программа или генератор программ. Lex строит  программу
-  лексический  анализатор на так называемом host-языке (или
"главном" языке). Это значит, что Lex-программа  пишется  на
"языке"  Lex,  а  Lex-генератор,  в свою очередь, генерирует
программу лексического анализа на каком-либо  другом  языке.
Данная версия Lex генерирует лексические анализаторы на язы-
ках Си и Ратфор (рациаональный диалект Фортрана). В качестве
host-языка  мы  будем  использовать язык Си. Сведения об ис-
пользовании в качестве host-языка Ратфор выделены в  отдель-
ный параграф.

   В каталоге /usr/lib/lex  имеется  файл-заготовка  ncform,
который  используется для построения лексического анализато-
ра, который строит Lex. Этот файл является уже готовой прог-
раммой  лексического  анализа,  но  в нем не определены дей-
ствия, которые необходимо выполнить при распознавании лексе-


4

мы,  отстутствуют  и  сами  лексемы, не сформированы рабочие
массивы и т.д.

   Lex на основе Lex-программы достраивает  файл  ncform.  В
результате  мы получаем файл со стандартным именем lex.yy.c,
который является текстом Си-программы, осуществляющей лекси-
ческий анализ.

   Lex-программа имеет следующий формат:

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

Любой из этих разделов может быть  пустым.  Простейшая  Lex-
программа имеет вид:

        %%

Здесь нет никаких определений и никаких правил.

   Все разделы Lex-программы мы  подробно  рассмотрим  ниже.
Сейчас  целесообразно  рассмотреть,  что  представляют собой
правила.

   Правило состоит из двух частей:

        РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ

По регулярным выражениям, содержащимся в левой части правил,
Lex  строит детерминированный конечный автомат. Этот автомат
осуществляет интерпретацию, а не компиляцию. Количество пра-
вил и их сложность не влияют на скорость лексического анали-
за, если только правила не требуют слишком  большого  об'ема
повторных  просмотров  входной  последовательности символов.
Однако, с ростом числа правил и их сложности  растет  размер
конечного  автомата,  интерпретирующего их и, следовательно,
растет размер Си-программы, реализующей этот конечный  авто-
мат.

   Рассмотрим в качестве примера следующую Lex-программу:

%%
[jJ][aA][nN][uU][aA][rR][yY]          {
                     printf("Январь");    }
[fF][eE][bB][rR][uU][aA][rR][yY]      {
                     printf("Февраль");   }
[mM][aA][rR][cC][hH]                  {
                     printf("Март");      }
[aA][pP][rR][iI][lL]                  {
                     printf("Апрель");    }
[mM][aA][yY]                          {
                     printf("Май");       }
[jJ][uU][nN][eE]                      {
                     printf("Июнь");      }
[jJ][uU][lL][yY]                      {
                     printf("Июль");      }
[aA][uU][gG][uU][sS][tT]              {
                     printf("Август");    }


                                                           5

[sS][eE][pP][tT][eE][mM][bB][eE][rR]  {
                     printf("Сентябрь");  }
[oO][cC][tT][oO][bB][eE][rR]          {
                     printf("Октябрь");   }
[nN][oO][vV][eE][mM][bB][eE][rR]     {
                     printf("Ноябрь");    }
[dD][eE][cC][eE][mM][bB][eE][rR]      {
                     printf("Декабрь");   }
[mM][oO][nN][dD][aA][yY]              {
                    printf("Понедельник");}
[tT][uU][eE][sS][dD][aA][yY]          {
                     printf("Вторник");   }
[wW][eE][dD][nN][eE][sS][dD][aA][yY]  {
                     printf("Среда");     }
[tT][hH][uU][rR][sS][dD][aA][yY]      {
                     printf("Четверг");   }
[fF][rR][iI][dD][aA][yY]              {
                     printf("Пятница");   }
[sS][aA][tT][uU][rR][dD][aA][yY]      {
                     printf("Суббота");   }
[sS][uU][nN][dD][aA][yY]              {
                    printf("Воскресенье");}

Программа  строит  конечный  автомат,   который   распознает
английские наименования месяцев и дней недели. Каждое прави-
ло здесь определеяет действие (оно взято в фигурные скобки).
Обратите  внимание  на  то,  что открывающая фигурная скобка
стоит в той же строке, что и правило - это требование Lex.

   Действие в каждом  правиле  данной  Lex-программы  -  это
вывод  русского значения найденного английского слова. В ка-
честве оператора, выполняющего действие, используется библи-
отечная функция языка Си.

   Пара фигурных скобок определяет блок (в смысле языка Си),
который  может  содержать  любое количество строк. Если дей-
ствие содержит всего одну строку Си, то можно ее указать без
фигурных  скобок,  как  обычно.  Единственное  условие - она
должна начинаться в той же строке,  где  указано  регулярное
выражение.

   В программе содержится только раздел правил, их всего 19.
Регулярное  выражение  каждого правила определяет английское
слово, написанное маленькими или большими латинскими  симво-
лами.  Например "May" (Май) определен как "[mM][aA][yY]". По
этому регулярному выражению будет выделена во входном потоке
символов  лексема  "May",  а по действию этого правила будет
выведено "Май". Наличие большой и малой буквы  в  квадратных
скобках  обеспечивает  распознавание  слова May, написанного
любыми латинскими символами.

   Таким образом, данная Lex-программа строит  Си-программу,
которая переводит на русский язык имена месяцев и дней неде-
ли.

   Допустим,  Lex-программа   размещена  в  файле  source.l,
тогда,  чтобы получить лексический анализатор на Си, необхо-
димо выполнить следующий набор команд:






6

        % lex source.l
        % cc -O lex.yy.c -ll -o program
        %

Lex всегда, если не указано другое, строит выходной  файл  с
именем  lex.yy.c - Си-программу - лексический анализатор. Во
второй строке этой последовательности команд запускается Си-
компилятор, который выводит результат в файл program.

   Program может работать как фильтр в конвейере команд, как
самостоятельная команда и в интерактивном режиме. Например:

        % program

        May
        Май
        MONDAY
        Понедельник
        MoNdaY
        Понедельник

        CNTRL/C
        %

Флаг -ll требует подключения  библиотеки  /usr/lib/libl.a  -
библиотеки  Lex.  Если  необходимо  получить самостоятельную
программу, как в данном случае, подключение библиотеки  обя-
зательно,  поскольку  тогда  из  нее  подключается  головной
раздел main. В противном случае, если имеется  необходимость
включить  анализатор  в  качестве функции в другую программу
(например в программу грамматического разбора),  эту  библи-
отеку  необходимо  вызвать уже при сборке и тогда, если main
определен в вызывающей лексический анализатор программе, ре-
дактор  связей не будет подключать раздел main из библиотеки
Lex.

   Если имеется необходимость получить файл с именем, отлич-
ным от lex.yy.c, то можно воспользоваться флагом "-t" :

        % lex -t source.l > file

По этому флагу результат поступает на стандартный вывод.






















                                                           7




           2. Регулярные выражения в Lex-правилах


   Регулярные выражения определяют лексему. Регулярное выра-
жение  может содержать символы латинского и русского алфави-
тов в верхнем и нижнем  регистрах,  другие  символы  (цифры,
знаки препинания и т.д.) и символы-операторы.

   Операторы позволяют осуществлять различные  действия  над
выделенной  цепочкой  символов. Операторы также обозначаются
символами.



   2.1. Обозначения символов в выражениях


   В выражении можно использовать любой символ. Символ можно
указывать в двойных кавычках. В этом случае это всегда прос-
то символ - его специальное значение отменяется. Например:

        "abc"
         abc

эти последовательности символов идентичны.

.    точка означает любой символ, кроме символа новой строки
     "\n";

\восьмеричный_код_символа
     указание символа его восьмеричным кодом (как в Си);

\n   символ новой строки;

\t   символ табуляции;

\b   возврат курсора на один шаг назад;

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



   2.2. Операторы регулярных выражений


   Операторы обозначаются символами-операторами, к ним отно-
сятся:

     \   ^   ?   *   +   |   $   /   %
           []   {}   ()   <>

Каждый из этих символов или пар скобок в регулярном  выраже-
нии  играет  роль оператора. Если необходимо отменить специ-
альное значение символа, обозначающего оператор,  перед  ним


8

нужно  поставить символ "\" или указать его в двойных кавыч-
ках. Например:

        abc+    - символ "+" - оператор;
        abc\+   - символ "+";
        abc"+"  - символ "+".




   2.3. Оператор выделения классов символов


   Квадратные скобки задают классы символов, которые  в  них
заключены.

[abc]
     означает либо символ "a", либо "b", либо символ "c";

   Знак "-" используется для указания любого символа из лек-
сикографически упорядоченной последовательности:

[A-z]
     означает любой латинский символ;

[А-Я]
     любая прописная русская буква;

[+-0-9]
     все цифры и знаки "+" и "-".



   2.4. Повторители


   Когда необходимо указать повторяемость вхождения  символа
в регулярном выражении, используют операторы-повторители "*"
и  "+".

   Оператор "*" означает любое (в том числе и 0) число вхож-
дений символа или класса символов. Например:

x*   любое число вхождений символа "x";

abc* любое число вхождений цепочки abc;

[A-z]*
     любое число вхождений любой латинской буквы;

[A-ZА-Яa-zа-я_0-9]*
     любое вхождение русских и латинских букв, знака подчер-
     кивания и цифр.

   Оператор "+" означает одно и более вхождений. Например:

x+   одно или более вхождений "x";

[0-9]+
     одно или более вхождений цифр;




                                                           9

abc+ одно или более вхождений цепочки abc;

[A-z]+
     одно или более вхождений любой латинской буквы.



   2.5. Операторы выбора


   Операторы:

        /   |   ?   $   ^

управляют процессом выбора символов.

   Оператор "/":

ab/cd
     "ab" учитывается только тогда,  когда  за  ним  следует
     "cd".

   Опeратор "|":

ab|cd
     или "ab", или "cd".

   Опeратор "?":

x?   означает необязательный символ "x".

_?[A-Za-z]*
     означает, что  перед  цепочкой  любого  количества  ла-
     тинских букв может быть необязательный знак подчеркива-
     ния.

-?[0-9]+
     выделит любое целое число с необязательным минусом впе-
     реди.

   Оператор "$":

x$   означает выбрать символ "x", если он является последним
     в строке. Стоит перед символом "\n"!

abc$ означает выбрать  цепочку  "abc",  если  она  завершает
     строку.

   Оператор "^":

^x   означает выбрать символ "x", если  он  является  первым
     символом строки;

^abc означает выбрать цепочку символов "abc", если она начи-
     нает строку.

[^A-Z]*
     означает все символы, кроме прописных  латинских  букв.
     Когда  символ  "^"  стоит  перед  выражением или внутри
     "[]", он выполняет операцию дополнение. Внутри квадрат-
     ных  скобок символ "^" должен обязательно стоять первым
     у открывающей скобки!


10




   2.6. Оператор {}


   Оператор {} имеет два различных применения:

x{n,m}  здесь n и m натуральные, m > n. Означает от n  до  m
        вхождений  x, например, x{2,7} - от 2 до 7 вхождений
        x.

{имя}   вместо  "{имя}"  в  данное  место  выражения   будет
        подставлено определение имени из области определений
        Lex-программы.

   Пример:

БУКВА           [A-ZА-Яa-zа-я_]
ЦИФРА           [0-9]
ИДЕНТИФИКАТОР   {БУКВА}({БУКВА}|{ЦИФРА})*
%%
{ИДЕНТИФИКАТОР} printf("\n%s",yytext);

Lex построит лексический анализатор, который  будет  опреде-
лять  и выводить все "слова" из входного файла. Под словом в
данном случае подразумевается идентификатор Си-программы.  В
этом    примере    {ИДЕНТИФИКАТОР}    будет    заменен    на
{БУКВА}({БУКВА}|{ЦИФРА})*, затем  на  [A-ZА-Яa-zа-я_]([A-ZА-
Яa-zа-я_]|[0-9])*.

   yytext - это внешний массив символов программы  lex.yy.c,
которую  строит  Lex.  yytext  формируется в процессе чтения
входного файла и содержит текст,  для  которого  установлено
соответствие  какому-либо  выражению.  Этот  массив доступен
пользовательским разделам Lex-программы.

   Оператор printf выводит  каждый  идентификатор  на  новой
строке.

   Правило ".|\n           ;" используется для  того,  чтобы
пропустить  (не  выводить)  все цепочки символов, которые не
соответствуют регулярному выражению {ИДЕНТИФИКАТОР}.



   2.7. Оператор <>. Служебные слова START и BEGIN


   Раздел правил Lex-программы может  содержать  активные  и
неактивные  правила.  Активные  правила  выполняются всегда.
Неактивные выполняются только в тех случаях, когда  выполня-
ется некоторое начальное условие.

   Начальные условия Lex-программы помещаются в раздел опре-
делений,  а  неактивные  правила помечаются соответствующими
условиями. Оператор Start позволяет указать список начальных
условий  Lex-программы, а оператор BEGIN позволяет активиро-
вать правила, помеченные начальными условиями.





                                                          11

   Активные правила имеют следующий синтаксис:

               РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ  ДЕЙСТВИЕ

Неактивные правила имют следующий синтаксис:

           <МЕТКА_УСЛОВИЯ>РЕГ_ВЫРАЖЕНИЕ  ДЕЙСТВИЕ


   ВАЖНО: любое правило должно начинаться с  первой  позиции
строки,  пробелы  и табуляции недопустимы - они используются
как разделители между регулярным выражением  и  действием  в
правиле!

   Рассмотрим пример:

%Start  COMMENT

КОММ_НАЧАЛО     "/*"
КОММ_КОНЕЦ      "*/"

%%
{КОММ_НАЧАЛО}         { ECHO;
                        BEGIN COMMENT;};
[\t\n]*               ;


<COMMENT>[^*]*          ECHO;
<COMMENT>\*/[^/]        ECHO;
<COMMENT>{КОММ_КОНЕЦ} {
                        ECHO;
                        printf("\n");
                        BEGIN 0;};

Lex построит лексический анализатор, который  выделяет  ком-
ментарии  в  Си-программе и записывает их в стандартный файл
вывода. Программа начинается с ключевого слова START,  кото-
рое  указано  после  символа "%". Ключевое слово START можно
указать и так:  Start, или S, или s  .  За  ключевым  словом
Start указана метка начального условия COMMENT.

   Оператор "<COMMENT>x" означает - x, если анализатор нахо-
дится в начальном условии COMMENT.

   Oператор "BEGIN COMMENT;" переводит анализатор в  началь-
ное  условие COMMENT (смотрите первое правило раздела правил
этой Lex-программы). После этого анализатор уже находится  в
новом  состоянии  и  теперь  разбор входного потока символов
будет осуществляется и теми  правилами,  которые  начинаются
оператором "<COMMENT>". Например, правило

        <COMMENT>[^*]*          ECHO;

выполняется только тогда, когда во входном  потоке  символов
будет  обнаружено  начало комментариев ("/*"). В этом случае
анализатор записывает в стандартный файл вывода любое  число
(в том числе и ноль) символов, отличных от символа "*". Опе-
ратор "BEGIN 0;" переводит анализатор в исходное состояние.

   Lex-программа может содержать  несколько  помеченных  на-
чальных  условий.  Например,  если  Lex-программа начинается
строкой


12

        %Start AA BB CC DD

то это означает, что она управляет четырьмя начальными  сос-
тояниями  анализатора.  В каждое из этих начальных состояний
анализатор можно перевести, используя оператор BEGIN.

   Каждое  правило,  перед  которым  указан  оператор   типа
"<МЕТКА>",  мы будем называть помеченым правилом. Метка фор-
мируется также как и метка в Си.

   Количество помеченных  правил  не  ограничивается.  Кроме
того, разрешается одно правило помечать несколькими метками,
например:

        <МЕТКА1,МЕТКА2,МЕТКА3>x  ДЕЙСТВИЕ

Запятая - обязательный разделитель списка меток!

   Рассмотрим пример с несколькими начальными условиями:

%START AA BB CC

БУКВА           [A-ZА-Яa-zа-я_]
ЦИФРА           [0-9]
ИДЕНТИФИКАТОР   {БУКВА}({БУКВА}|{ЦИФРА})*

%%
^#                          BEGIN AA;
^[ \t]*main                 BEGIN BB;
^[ \t]*{ИДЕНТИФИКАТОР}      BEGIN CC;
\t                          ;
\n                          BEGIN 0;

<AA>define       printf("Определение.\n");
<AA>include      printf("Включение.\n");
<AA>ifdef        {
    printf("Условная компиляция.\n"); }

<BB>[^\,]*","[^\,]*")"  {
    printf("main с аргументамии.\n"); }

<BB>[^\,]*")"   {
    printf("main без аргументов.\n"); }

<CC>":"/[ \t]    printf("Метка.\n");

Программа содержит активные и неактивные правила. Все  неак-
тивные правила помечены, перед ними указана метка начального
условия. Lex-программа управляет тремя начальными условиями,
в соответствии с которыми активируются помеченные правила.

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







                                                          13




                 3. Структура Lex-программы


   Lex-программа  включает  разделы  опредeлений,  правил  и
пользовательских   программ.  Рассмотрим  подробнее  способы
оформления этих разделов.

   Все строки, в которых занята первая позиция, относятся  к
Lex-программе.  Любая  строка,  не являющаяся частью правила
или действия, которая начинается с  пробела  или  табуляции,
копируется  в сгенерированную программу lex.yy.c - результат
работы Lex.



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


   Определения, предназначенные для  Lex,  помещаются  перед
первым %%. Любая строка этого раздела, не содержащаяся между
%{ и %} и начинающаяся в первой колонке, является  определе-
нием   строки   подстановки  Lex.  Раздел  определений  Lex-
программы может включать:

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


   НАЧАЛЬНЫЕ УСЛОВИЯ задаются в форме:

        %START имя1 имя2 ...

Если начальные условия определены, то эта строка должна быть
первой в Lex-программе.

   ОПРЕДЕЛЕНИЯ задаются в форме:

        имя  трансляция

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

БУКВА           [A-ZА-Яa-zа-я_]
DIGIT           [0-9]
ИДЕНТИФИКАТОР   {БУКВА}({БУКВА}|{DIGIT})*

Имя - как обычно, любая последовательность букв и цифр,  на-
чинающаяся  с  буквы.  Трансляция - это регулярное выражение
(или его часть), которое будет подставлено  всюду  там,  где
указано имя (смотрите третью строку этого примера).

   ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя спосо-
бами:



14

   - в виде "пробел фрагмент";

   - в виде:

        %{
        строки
        фрагмента
        программы
        пользователя
        %}

Такая форма включения пользовательского фрагмента необходима
для ввода, например, макроопределений Си, которые должны на-
чинаться в первой колонке строки. Все строки фрагмента поль-
зовательской  программы,  размещенные в разделе определений,
будут являться внешними для любой функции программы lex.yy.c

   ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде:

        %T
        целое_число   строка_символов
        .........
        целое_число   строка_символов
        %T

Сгенерированная программа lex.yy.c  осуществляет  ввод-вывод
символов  посредством  библиотечных  функций  Lex  с именами
input, output, unput. Таким образом, Lex помещает  в  yytext
символы  в  представлении,  используемом в этих библиотечных
функциях. Для внутреннего использования символ представляет-
ся целым числом, значение которого образовано набором битов,
представляющих символ в конкретной ЭВМ. Пользователю предос-
тавляется  возможность  менять представление символов (целых
констант) с помощью таблицы наборов символов.  Если  таблица
символов   присутствует  в  разделе  определений,  то  любой
символ, появляющийся либо во входном потоке, либо  в  прави-
лах,  должен  быть  определен  в  таблице символов. Символам
нельзя назначать число 0 и число, большее числа, выделенного
для внутреннего представления символов конкретной ЭВМ.

   Пример:

        %T
        1       Aa
        2       Bb
        3       Cc
        .
        .
        .
        26      Zz
        27      \n
        28      +
        29      -
        30      0
        31      1
        .
        .
        .
        39      9
        %T

В этом примере символы верхнего и нижнего регистров  перево-


                                                          15

дятся  в числа 1-26, символ новой строки в 27, "+" и "-" пе-
реводятся в числа 28 и 29, а цифры - в числа 30-39.

   УКАЗАТЕЛЬ host-языка имеет вид:

%C   для Си;

%R   для Ратфора.

   Если указатель host-языка отсутствует,  то  по  умолчанию
принимается Си.

   ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме:

        %x   число

"число" - новый размер массива;
"x"     - одна из букв:

     p   - позиции;
     n   - состояния;
     e   - узлы дерева;
     a   - упакованные переходы;
     k   - упакованные классы символов;
     o   - массив выходных элементов.

Lex имеет внутренние таблицы,  размеры  которых  ограничены.
При построении программы лексического анализа может произой-
ти переполнение любой из этих таблиц, о чем Lex сообщает при
построении лексического анализатора. Пользователю предостав-
ляется возможность изменить размеры таблиц (сокращая размеры
одних  и увеличивая размеры других) таким образом, чтобы они
не переполнялись. Естественно, эти изменения возможны лишь в
пределах той памяти, которая выделяется под процесс.

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

p - позиций                      1500
n - состояний                     300
e - узлов                         600
a - упакованных переходов        1500
k - упакованных классов символов 1000
o - выходных элементов           1500

Для того чтобы определить, каковы размеры таблиц и насколько
они заняты, можно использовать флаг "-v", например:

%  lex -v source.l
33/600 узлов(%e)
97/1500 позиций(%p)
17/300 состояний(%n)
2551 переходов
18/1000 упакованных классов символов(%k)
41/1500 упакованных переходов(%a)
68/1500 выходных элементов(%o)
%

Здесь показано сообщение, которое выводит Lex по флагу "-v".
Число перед символом "/" указывает сколько элементов массива
занято, а число  за  символом  "/"  указывает  установленный
размер массива.


16


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



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


   Все, что указано после первой пары %%  и  до  конца  Lex-
программы или до второй пары %%, если она указана, относится
к разделу правил. Раздел правил может  содержать  правила  и
фрагменты  программ. Фрагменты программ, содержащиеся в раз-
деле правил, становятся частью функции yylex файла lex.yy.c,
в  которой  осуществляется выполнение действий активных пра-
вил. Фрагмент программы указывается следующим образом:

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

Например:

        %%
        %{
        #include file.h
        %}
        .
        .
        .

Здесь  строка  "#include  file.h"  станет  строкой   функции
yylex().

   Раздел правил может включать список активных и неактивных
(помеченных)  правил.  Активные  и  неактивные правила могут
быть указаны в любом порядке, в том числе быть "перемешанны-
ми"  в списке. Активные правила выполняются всегда, неактив-
ные только по ссылке на них оператором BEGIN.

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

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


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

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

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

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

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





                                                          17

        BEGIN МЕТКА;

В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым  действием  в
разделе  правил  будет  активизация  помеченных  правил. Для
возвращения автомата в исходное состояние можно использовать
действие:

        BEGIN 0;

Важно отметить следующее. Если Lex-программа содержит актив-
ные и неактивные правила, то активные правила работают всег-
да. Оператор "BEGIN МЕТКА;" просто расширяет список активных
правил, активируя помеченные меткой МЕТКА. А оператор "BEGIN
0;" удаляет из списка активных правил все помеченные  прави-
ла,  которые до этого были активированы. Кроме того, если из
помеченного и активного в данный момент времени правила осу-
ществляется  действие  BEGIN  МЕТКА, то из помеченных правил
активными  останутся  только  те,  которые  помечены  меткой
МЕТКА.



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


   Действие можно представлять либо как оператор Lex, напри-
мер,  "BEGIN МЕТКА;", либо как оператор Си. Если имеется не-
обходимость выполнить достаточно большой набор  преобразова-
ний, то действие оформляют как блок Си-программы (он начина-
ется открывающей фигурной скобкой и завершается  закрывающей
фигурной скобкой), содержащий необходимые фрагменты.

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

   Область действия переменных,  об'явленных  внутри  блока,
распространяется  только  на этот блок. Внешними переменными
для всех действий будут являться только те переменные, кото-
рые об'явлены в разделе определений Lex-программы.

   Действия в правилах Lex-программы выполняются, если  пра-
вило  активно, и если автомат распознает цепочку символов из
входного потока как  соответствующую  регулярному  выражению
данного  правила. Однако, одно действие выполняется всегда -
оно заключается в копировании входного потока символов в вы-
ходной.  Это  копирование  осуществляется  для  всех входных
строк, которые не соответствуют правилам, преобразующим  эти
строки.  Комбинация  символов,  не учтенная в правилах и по-
явившаяся на входе, будет напечатана на выходе.  Можно  ска-
зать, что действие - это то, что делается вместо копирования
входного потока символов на выход. Часто  бывает  необходимо
не  копировать  на выход некоторую цепочку символов, которая
удовлетворяет некоторому  регулярному  выражению.  Для  этой
цели используется пустой оператор Си, например:







18

        [ \t\n]         ;

Это правило игнорирует (запрещает) вывод пробелов, табуляций
и  символа  "новая  строка". Запрет выражается в том, что на
указанныe символы во входном потоке осуществляется  действие
";"  - пустой оператор Си, и эти символы не копируются в вы-
водной поток символов.

   Существует возможность для нескольких регулярных  выраже-
ний  указывать  одно действие. Для этого используется символ
"|", который указывает, что действие данного правила  совпа-
дает с действием для следующего, например:

        " "             |
        \t              |
        \n              ;

Результат будет тот же, что и в примере, указанном выше.

   Когда необходимо вывести или преобразовать  текст,  соот-
ветствующий  некоторому  регулярному выражению, используется
внешний массив символов, который формирует  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;}

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










                                                          19

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


   Список правил Lex-программы может  содержать  активные  и
неактивные  правила,  размещенные  в любом порядке в разделе
правил. В процессе работы  лексического  анализатора  список
активных правил может видоизменяться за счет действий опера-
тора BEGIN. В процессе распознавания символов входного пото-
ка  может  оказаться  так,  что  одна цепочка символов будет
удовлетворять нескольким правилам и, следовательно, возника-
ет проблема: действие какого правила должно выполняться?

   Для  разрешения  этого  противоречия  можно  использовать
квантование  (разбиение)  регулярных  выражений  этих правил
Lex-программы на такие новые регулярные  выражения,  которые
дадут,  по  возможности,  однозначное распознавание лексемы.
Однако, когда это не сделано,  Lex  использует  определенный
детерминированный механизм разрешения такого противоречия:

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

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

   Рассмотрим пример:

        .
        .
        .
        [Мм][Аа][Йй]          ECHO;
        [А-Яа-я]+             ECHO;
        .
        .
        .

Слово "Май" распознают оба правила, однако, выполнится  пер-
вое  из  них,  так как и первое, и второе правило распознали
лексему одинакового размера (3 символа). Если во входном по-
токе  будет,  допустим, слово "майский", то первые 3 символа
удовлетворяют первому правилу, а все 7 символов удовлетворя-
ют  второму правилу, следовательно, выполнится второе прави-
ло, так как ему удовлетворяет более  длинная  последователь-
ность символов.



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


   Все, что размещено за вторым набором %%, относится к раз-
делу программ пользователя. Содержимое этого раздела копиру-
ется в выходной файл lex.yy.c без  каких-либо  изменений.  В
файле  lex.yy.c  строки  этого  раздела  рассматриваются как
функции в смысле Си. Эти функции могут вызываться в действи-
ях  правил  и,  как обычно, передавать и возвращать значения
аргументов.




20

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


   Комментарии  можно  указывать  во  всех   разделах   Lex-
программы. Формат комментариев должен соответствовать форма-
ту комментариев host-языка. Однако, в  каждом  разделе  Lex-
программы  комментарии указываются по разному. В разделе оп-
ределений комментарии должны начинаться не с первой  позиции
строки.  В разделе правил комментарии можно указывать только
внутри блоков, принадлежащих действиям. В  разделе  программ
пользователя комментарии указываются как и в host-языке.



   3.5. Примеры Lex-программ


   Пример1.

%Start  KOMMENT
      /*
       *  Программа записывает в
       *  стандартный файл вывода
       *  комментарии Си-программы.
       *  Обратите внимание на то, что
       *  здесь строки комментариев указаны
       *  не с первой позиции строки!
       */

КОММ_НАЧАЛО     "/*"
КОММ_КОНЕЦ      "*/"

%%
{КОММ_НАЧАЛО}         { ECHO;
                        BEGIN KOMMENT;}
[\t\n]*               ;

<KOMMENT>[^*]*          ECHO;
<KOMMENT>\*/[^/]        ECHO;
<KOMMENT>{КОММ_КОНЕЦ} {
                        ECHO;
                        printf("\n");
/*
 *    Здесь приведен  пример
 *    использования комментариев в
 *    разделе правил Lex-программы.
 *    Обратите внимание на то, что
 *    комментрий указан внутри блока,
 *    определяющего действие правила.
 */
                        BEGIN 0;}
%%

/*
 *  Здесь приведен пример комментариев
 *  в разделе программ пользователя.
 */


   Пример 2.




                                                          21

%Start IC1 IC2 Normal

       /*
        *   Отладочный фрагмент
        *   Lex-программы, которая строит
        *   лексический анализатор для
        *   компилятора языка Паскаль.
        *   Действие return(...)
        *   возвращает тип лексемы в
        *   в вызывающую анализатор
        *   программу.
        *   Обратите внимание на то, что в
        *   этой Lex-программе отсутствуют
        *   активные правила. Это сделано
        *   в связи с тем, что нет
        *   необходимости иметь правила,
        *   которые всегда активны.
        *   Все цепочки символов входного
        *   потока, не распознанные в
        *   правилах, копируются в выходной
        *   поток символов.
        */

LETTER          [A-ZА-Яa-zа-я_]
DIGIT           [0-9]
IDENT           {LETTER}({LETTER}|{DIGIT})*
INT             {DIGIT}+
FIXED           {INT}?\.{INT}
WHISP           [ \t\n]*

%%
                      BEGIN Normal;
<Normal>"{"           BEGIN IC1;
<IC1>[^}]             ;
<IC1>"}"              BEGIN Normal;
<Normal>"(*"          BEGIN IC2;
<IC2>[^*]|\*/[^)]     ;
<IC2>"*)"             BEGIN Normal;

<Normal>'([^']|'')*'  return( строка );
<Normal>"<>"          return( не_равно );
<Normal>"="           return( равно );
<Normal>"<"           return( меньше );
<Normal>">"           return( больше );
<Normal>">="      return(больше_или_равно);
<Normal>"<="      return(меньше_или_равно);
<Normal>".."         return( точка_точка );
<Normal>"+"           return( плюс );
<Normal>"-"           return( минус );
<Normal>":="          return( присвоить );
<Normal>"*"           return( умножить );
<Normal>"/"           return( разделить );
<Normal>mod           return( t_mod );
<Normal>div           return( t_div );
<Normal>and           return( t_and );
<Normal>or            return( t_or );
<Normal>not           return( t_not );
<Normal>"("           return( lpar );
<Normal>")"           return( rpar );
<Normal>"["           return( lbracket );
<Normal>"]"           return( rbracket );
<Normal>","           return( comma );


22

<Normal>":"           return( colon );
<Normal>"^"           return( circumflex );
<Normal>";"           return( semicolon );
<Normal>write         return( Write );
<Normal>writeln       return( Writeln );
<Normal>label         return( t_label );
<Normal>program       return(  );
<Normal>const         x( "константы" ) ;
<Normal>type          x( "типы" ) ;
<Normal>var           x( "перем" ) ;
<Normal>procedure     x( "процедура" ) ;
<Normal>function      x( "функция" ) ;
<Normal>begin         x( "начало" ) ;
<Normal>end{WHISP}\.  x( "конец прогр" ) ;
<Normal>end           x( "конец" ) ;
<Normal>array         x( "массив" ) ;
<Normal>of            x( "из" ) ;
<Normal>record        x( "запись" ) ;
<Normal>case          x( "выбор" ) ;
<Normal>in            x( "в" ) ;
<Normal>file          x( "файл" ) ;
<Normal>for           x( "для" ) ;
<Normal>to            x( "к" ) ;
<Normal>downto        x( "вниз к" ) ;
<Normal>do            x( "выполн" ) ;
<Normal>while         x( "пока" ) ;
<Normal>repeat        x( "повт" ) ;
<Normal>until         x( "до" ) ;
<Normal>set           x( "множество" ) ;
<Normal>with          x( "с" );
<Normal>nil           x( "nil" ) ;
<Normal>if            x( "если" ) ;
<Normal>then          x( "то" ) ;
<Normal>else          x( "иначе" ) ;
<Normal>{FIXED}       x( "float" ) ;
<Normal>{INT}         x( "ц.б.з" ) ;
<Normal>{IDENT}       x( "идент" ) ;
<Normal>[ \n\t]       ;

%%

x( s )
char *s ;
{

printf("%-15.15s \177> %s <\177\n",
                        s, yytext ) ;

}















                                                          23




                4. Структура файла lex.yy.c


   Lex строит программу - лексический  анализатор  на  языке
Си,  которая  размещается  в  файле  со  стандартным  именем
lex.yy.c. Эта программа содержит две основных функции и нес-
колько вспомогательных. Основные - это:

функция yylex()
     Она содержит разделы действий всех правил, которые  оп-
     ределены пользователем;

функция yylook()
     Она реализует детерминированный конечный автомат, кото-
     рый  осуществляет разбор входного потока символов в со-
     ответствии  с  регулярными  выражениями   правил   Lex-
     программы.

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

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

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

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

   Эти функции определены как макроподстановки следующим об-
разом:

   input -

        fprintf( fout, "%s%d%s\n",
  "#define input() (((yytchar=yysptr>yysbuf
        ctable['\n'],
 "?(yylineno++,yytchar):yytchar)==EOF?0:yyt


   unput -

#define unput(c){
        yytchar = (c);
        if( yytchar == '\\n' ) yylineno--;
        *yysptr++ = yytchar;
}


   output -

#define output(c) putc(c,yyout)\n


   Эти функции можно изменить, указав им те же имена и  раз-
местив в разделе программ пользователя.



24

   Кроме того имеются функции yywrap(), reject(),yyless()  и
yymore(), описание которых выделено в отдельные параграфы.

   Файл lex.yy.c - это Си-программа, в которой можно сделать
любые необходимые изменения и добавления. Ниже приведен файл
/usr/lib/lex/ncform, из которого формируется файл  lex.yy.c.
В  нем  отсутствует  функция yylex(). Эту функцию генерирует
Lex и включает в файл lex.yy.c.

int yylineno = 1;
# define YYU(x) ((int)(x)&0377)
# define NLSTATE yyprevious = YYNEWLINE
char yytext[YYLMAX];
struct yysvf *yylstate[YYLMAX], **yylsp;
struct yysvf **yyolsp;
char yysbuf[YYLMAX];
char *yysptr = yysbuf;
int *yyfnd;
extern struct yysvf *yyestate;
int yyprevious = YYNEWLINE;
yylook(){
 register struct yysvf *yystate, **lsp;
 register struct yywork *yyt;
 struct yysvf *yyz;
 int yych;
 struct yywork *yyr;
 char *yylastch;
 /* start off machines */
 if(!yymorfg)
        yylastch = yytext;
 else {
        yymorfg = 0;
        yylastch = yytext + yyleng;
 }
 for(;;){
  lsp = yylstate;
  yyestate = yystate = yybgin;
  if(yyprevious == YYNEWLINE) yystate++;
  for(;;){
        yyt = yystate->yystoff;
        if( yyt == yycrank ){
        /* may not be any transitions */
                yyz = yystate->yyother;
                if(yyz == 0) break;
                if(yyz->yystoff==yycrank)
                        break;
   }
   *yylastch++ = yych = input();
   tryagain:
   yyr = yyt;
   if( (int)yyt > (int)yycrank ){
        yyt = yyr + yych;
        if( yyt <= yytop
            && YYU(yyt->verify) + yysvec
            == yystate ){
                if(yyt->advance==YYLERR){
                  /* error transitions */
                    unput(*--yylastch);
                    break;
               }
               *lsp++ = yystate
               = YYU(yyt->advance)+yysvec;


                                                          25

               goto contin;
        }
   }
   yyt = yyt + yych;
   if( yyt <= yytop
           && YYU(yyt->verify) + yysvec
           == yystate ){
        if(yyt->advance == YYLERR){
                /* error transitions */
                unput(*--yylastch);
                break;
        }
        *lsp++ = yystate
               = YYU(yyt->advance)+yysvec;
        goto contin;
   }
   yyt = yyr + YYU( yymatch[yych] );
   if( yyt <= yytop
           && YYU(yyt->verify) + yysvec
           == yystate ){
        if(yyt->advance == YYLERR){
                /* error transition */
                unput(*--yylastch);
                break;
        }
        *lsp++ = yystate
               = YYU(yyt->advance)+yysvec;
        goto contin;
   }
  }
  if( (yystate = yystate->yyother)
       && (yyt = yystate->yystoff)
       != yycrank){

  } else {
        unput(*--yylastch);
        break;
  }

contin:
                ;
  while( lsp-- > yylstate ){
        *yylastch-- = 0;
        if( *lsp != 0
            && ( yyfnd = (*lsp)->yystops )
            && *yyfnd > 0 ){
                yyolsp = lsp;
                if( yyextra[*yyfnd] ){
                        /* must backup */
while( yyback((*lsp)->yystops,-*yyfnd)
       != 1 && lsp > yylstate ){
                                   lsp--;
                    unput( *yylastch-- );
}
                }
                yyprevious=YYU(*yylastch);
                yylsp = lsp;
                yyleng=yylastch-yytext+1;
                yytext[yyleng] = 0;
                return( *yyfnd++ );
        }
        unput( *yylastch );


26

  }
  if( yytext[0] == 0
        /* && feof(yyin) */){
                yysptr = yysbuf;
                return(0);
  }
  yyprevious = yytext[0] = input();
  if( yyprevious > 0 )
        output(yyprevious);
  yylastch = yytext;
 }
}

yyback(p, m)
int *p;
{
        if(p == 0)
                return(0);

        while(*p){
                if( *p++ == m )
                        return(1);
        }
        return(0);
}

/*
 * the following are only used
 * in the lex library
 */

yyinput(){

        return(input());

}

yyoutput(c)
int c;
{
        output(c);
}

yyunput(c)
int c;
{
        unput(c);
}


   При сборке программы лексического анализа редактор  связи
ld  по  флагу -ll подключает головную функцию main, если она
неопределена. Ниже приведен текст этой функции из библиотеки
/usr/lib/libl.a

# include "stdio.h"
main(){
        yylex();
        exit(0);
}




                                                          27




                    5. Функция yywrap()


   Функция yywrap используется для определения конца  файла,
из  которого  лексический  анализатор читает поток символов.
Если yywrap возвращает 1, лексический анализатор  прекращает
работу.  Однако,  иногда  имеется  необходимость начать ввод
данных из другого источника и продолжить работу. В этом слу-
чае  пользователь  должен написать свою подпрограмму yywrap,
которая организует новый входной поток и возвращает  0,  что
служит сигналом к продолжению работы анализатора. По умолча-
нию yywrap всегда возвращает 1 при завершению входного пото-
ка символов.

   В  Lex-программе  невозможно  записать  правило,  которое
будет обнаруживать конец файла. Единственный способ это сде-
лать - использовать фунцию yywrap. Эта функция также удобна,
когда необходимо выполнить какие-либо действия по завершению
входного потока символов, определив в разделе программ поль-
зователя новый вариант функции yywrap. Пример:

%START AA BB CC

   /*
    *   Строится лексический анализатор,
    *   который распознает наличие
    *   включений файлов в Си-программе,
    *   условных компиляций,
    *   макроопределений,
    *   меток и головной функции main.
    *   Анализатор ничего не выводит, пока
    *   осуществляется чтение входного
    *   потока, а по его завершении
    *   выводит статистику.
    */

БУКВА           [A-ZА-Яa-zа-я_]
ЦИФРА           [0-9]
ИДЕНТИФИКАТОР   {БУКВА}({БУКВА}|{ЦИФРА})*

                int a1,a2,a3,b1,b2,c;
%%
        {a1 = a2 = a3 = b1 = b2 = c = 0;}

^#                          BEGIN AA;
^[ \t]*main                 BEGIN BB;
^[ \t]*{ИДЕНТИФИКАТОР}      BEGIN CC;
\t                          ;
\n                          BEGIN 0;

<AA>define                  { a1++; }
<AA>include                 { a2++; }
<AA>ifdef                   { a3++; }

<BB>[^\,]*","[^\,]*")"      { b1++; }
<BB>[^\,]*")"               { b2++; }

<CC>":"/[ \t]               { c++;  }



28

%%

yywrap(){

if( b1 == 0 && b2 == 0 )
        printf("В программе\
 отсутствует  функция main.\n");

if( b1 >= 1 && b2 >= 1 ){
        printf("Многократное\
 определение функции main.\n");

} else {
    if(b1 == 1 )
        printf("Функция main\
 с аргументами.\n");

    if( b2 == 1 )
        printf("Функция main\
 без аргументов.\n");
}

printf("Включений файлов: %d.\n",a2);
printf("Условных компиляций: %d.\n",a3);
printf("Определений: %d.\n",a1);
printf("Меток: %d.\n",c);

return(1);

}


   Оператор return(1) в функции yywrap указывает, что лекси-
ческий  анализатор  должен завершить работу. Если необходимо
продолжить работу анализатора для чтения  данных  из  нового
файла,  нужно  указать  return(0), предварительно осуществив
операции закрытия и открытия файлов и, в этом случае, анали-
затор  продолжит чтение и обработку входного потока. Однако,
если yywrap не возвращает 1, то это приводит к  бесконечному
циклу.
























                                                          29




                     6. Функция REJECT


   Обычно Lex разделяет входной поток, не осуществляя  поиск
всех возможных соответствий каждому выражению. Это означает,
что каждый символ рассматривается один и  только  один  раз.
Предположим,  что мы хотим подсчитать все вхождения she и he
во входном тексте. Для этого мы могли бы записать  следующие
правила:

        she     s++;
        he      h++;
        .       |
        \n      ;

Так как she включает в себя he, анализатор не распознает  те
вхождения he, которые включены в she, так как, прочитав один
раз she, эти символы он не вернет во входной поток.

   Иногда желательно  переопределить  этот  выбор.  Действие
функции  REJECT  означает  "выбрать следующую альтернативу".
Это приводит к тому, что каким бы  ни  было  правило,  после
него необходимо выполнить второй выбор. Соответственно изме-
нится и положение указателя во входном потоке:

        she         { s++; REJECT; }
        he          { h++; REJECT; }
        .           |
        \n          ;

Здесь после выполнения одного правила  символы  возвращаются
назад во входной поток, и выполняется другое правило.

   Функция REJECT полезна в том случае, когда она применяет-
ся  для определения всех вхождений какого-либо об'екта, при-
чем вхождения могут перекрываться или включать  друг  друга.
Предположим,  необходимо  получить  из одного потока таблицу
всех двухбуквенных сочетаний, которые обычно  перекрываются,
например,  слово  the  содержит  как th, так и he. Допустим,
имеется двумерный массив digram, тогда:

%%
[a-z][a-z]      {

          digram[yytext[0]][yytext[1]]++;
          REJECT;
                }
\n              ;

Здесь REJECT используется для выделения буквенных пар, начи-
нающихся на каждой букве, а не на каждой следующей.










30




                 7. Функции yyless и yymore


   В обычной ситуации содержимое yytext  обновляется  всякий
раз,  когда  на входе появляется следующая строка. Напомним,
что в yytext всегда находятся символы распознанной  последо-
вательности. Иногда возникает необходимость добавить к теку-
щему содержимому yytext следующую распознанную цепочку  сим-
волов. Для этой цели используется функция yymore. Формат вы-
зова этой функции:

                          yymore()

В некоторых случаях возникает необходимость использовать  не
все  символы  распознанной  последовательности  в  yytext, а
только необходимое их  число.  Для  этой  цели  используется
функция yyless. Формат ее вызова:

                         yyless(n)

где n указывает, что в данный  момент  необходимы  только  n
символов  строки в yytext. Остальные найденные символы будут
возвращены во входной поток.

   Пример использования фунцкии yymore:

 .
 .
 .
\"[^"]*         {
         if( yytext[yyleng - 1] == '\\'){
                        yymore();
         }else{

             /*
              *  здесь должна быть часть
              *  программы, обрабатывающая
              *  закрывающую кавычку.
              */

         }
                }
 .
 .
 .

В этом примере распознаются строки симвoлов, взятые в  двой-
ные  кавычки,  причем,  символ  двойная  кавычка внутри этой
строки может изображаться  с  предшествующей  косой  чертой.
Анализатор должен распознавать кавычку, ограничивающую стро-
ку, и кавычку, являющуюся частью строки, когда она изображе-
на как \".

   Допустим, на вход поступает  строка  "абв\"где".  Сначала
будет распознана цепочка "абв\ и, так как последним символом
в этой цепочке будет символ "\", выполнится вызов  yymore().
В  результате  к  цепочке  "абв\  будет  добавлено "где, и в
yytext мы получим:  "абв\"где, что и требовалось.



                                                          31

   Пример использования фунции yyless:

 .
 .
 .
=-[A-ZА-Яa-zа-я]       {

  printf("Oператор (=-) двусмысленный.\n");
  yyless(yyleng - 2);

 /*
  * здесь необходимо указать
  * действия для случая "=-"
  */
                        }
 .
 .
 .

В этом примере  разрешается  двусмысленность  выражения  "=-
буква" в языке Си. Это выражение можно рассматривать как

        "=- буква" (равносильно "-=" )
или
        "= -буква"

Предположим, что желательно эту ситуацию  рассматривать  как
"=  -буква"  и  выводить пердупреждение. Указанное в примере
правило распознает эту ситуацию  и  выводит  предупреждение.
Затем, в результате вызова "yyless(yyleng - 2);"  два симво-
ла "-буква" будут возвращены во входной поток,  а  знак  "="
останется в yytext для обработки, как в нормальной ситуации.
Таким образом, при продолжении чтения  входного  потока  уже
будет обрабатываться цепочка "-буква", что и требовалось.






























32




           8. Совместное использование Lex и Yacc


   Yacc  требует  указание  лексическому  анализатору  имени
yylex(). Именно поэтому эта функция так называется в Lex.

   Известно, что Yacc строит выходной файл y.tab.c .  Основ-
ной  в  файле  y.tab.c является функция yyparse, реализующая
алгоритм грамматического разбора. Функция  yyparse  содержит
многократное обращение к функции лексического анализа yylex.

   Для обеспечения корректной работы грамматического  анали-
затора  функция  yylex  должна быть согласована с конкретной
спецификацией грамматики и удовлетворять определенным требо-
ваниям.

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

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

   Заметим, что ключевые слова описываемого  входного  языка
часто  бывает  удобно  считать лексемами. Имена лексем могут
совпадать с этими ключевыми словами,  недопустимым  является
лишь  совпадение  имен  лексем  с зарезервированными словами
языка Си.

   Основная задача функции yylex состоит во вводе из входно-
го  потока ряда очередных символов до выявления конструкции,
соответствующей одной из лексем, и возвращении  номера  типа
этой лексемы и, когда это необходимо, значения этой лексемы.

   Все виды лексем, кроме литералов, обозначаются некоторыми
именами и под этими именами фигурируют в Yacc-программе, где
об'явление имен лексем осуществляется директивой token:

        %token <список имен лексем>

Благодаря об'явлению имен лексем в директиве token Yacc  от-
личает имена лексем от имен нетерминальных символов.

   Пример об'явления имен лексем в Yacc-программе:

    %token IDENT CONST ЗНАК IF THEN GOTO

При первом появлении лексемы или литерала в секции  об'явле-
ний  Yacc-программы за каждым из них может следовать неотри-
цательное целое число, рассматриваемое как НОМЕР ТИПА лексе-
мы.




                                                          33

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

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

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

   Для каждого имени лексемы независимо от того, переопреде-
лен  ли  ее  номер пользователем, Yacc генерирует в выходном
файле y.tab.c оператор препроцессора:

      #define <имя лексемы> <номер типа>

Значение, возвращаемое функцией yylex, является номером типа
лексемы. Таким образом, список лексем и номера их типов ука-
зываются в Yacc-программе, а определения этих лексем в  Lex-
программе.  Возникает  проблема  соответствия  номеров типов
лексем в файлах y.tab.c и lex.yy.c, котороя разрешается сле-
дующим образом:

   - при вызове Yacc с флагом -d последовательность операто-
     ров #define помещается в файл y.tab.h.;

   - этот файл посредством оператора #include  включается  в
     Lex-программу.

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

   Примером значения лексемы могут служить числовое значение
символа - цифры, вычисленное значение константы, адрес иден-
тификатора в таблице  имен  (построение  таблицы  имен  осу-
ществляет  Lex).  Кроме  того, эти значения обычно требуется
передать грамматическому анализатору. С  этой  целью  нужное
значение  должно  быть  присвоено  внешней переменной целого
типа с именем yylval. Если функция yylex находится в отдель-
ном файле, то эта переменная должна быть об'явлена:

        extern int yylval;

Уточним, что ЗНАЧЕНИЕМ ЛЕКСЕМЫ мы будем  называть  значение,
присвоенное при ее распознавании переменной yylval. Заметим,
что в yylval всегда должно находится значение последней  вы-
деленной лексемы.

   Допустим, мы располагаем Yacc-программой в файле source.y
и   Lex-программой  в  файле  source.l,  которые  необходимо
собрать в работающую программу. Существует два способа сбор-
ки:

   - сборка Lex- и Yacc-программы с созданием файла y.tab.h;

   - сборка  Lex-  и  Yacc-программы  без   создания   файла
     y.tab.h.

   Рассмотрим первый способ сборки.



34

   Ниже приведен пример makefile, для программы make,  кото-
рая  осущесвляет  последовательную  обработку  и  сборку эих
программ и размещает результат в файле program:

program:        y.tab.o lex.yy.o
      cc y.tab.o lex.yy.o -ly -ll -o program

y.tab.o:        y.tab.c
                cc -c -O y.tab.c

lex.yy.o:       lex.yy.c  y.tab.h
                cc -c -O lex.yy.c

y.tab.h:
y.tab.c:        source.y
                yacc -d source.y

lex.yy.c:       source.l
                lex -v source.l

clear:
       rm -f yy.tab.?  lex.yy.? program

В файле source.l размещена Yacc-программа,  реализующая  не-
большой  настольный  калькулятор.  Калькулятор  имеет 52 ре-
гистра, помеченных буквами от A до z, и разрешает  использо-
вать  арифметические выражения, содержащие операции +, -, *,
/, % (остаток от деления), &  (побитовое  и),  |  (побитовое
или),  и присваивание. Как и в Си, целые числа, начинающиеся
с 0, считаются восьмеричными, все остальные  -  десятичными.
Результат всегда выводится десятичными числами.

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

   Знак "=" используется для присваивания, а  для  выведения
результата достаточно нажать клавишу <ВК>. Распознаются ско-
бочные структуры, изменяющие порядок приоритетов при  вычис-
лениях. Калькулятор работает только с целыми типа integer.

%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS
%{
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;  }


                                                          35

    |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;  }
    |number DIGIT  { $$=base*$1+$2; }


   В файле source.l размещена Lex-программа лексичского ана-
лизатора для этого калькулятора:

%{
#include   "y.tab.h"
extern int yylval;
%}
%%
^\n             ;
[ \t]*          ;
[A-Za-z]     {
       yylval = yytext[yyleng-1] - 'a';
       return(LETTER);}
[0-9]              {
       yylval = yytext[yyleng-1] - '0';
       return(DIGIT);}


   Рассмотрим второй  способ  сборки.  Makefile  теперь  су-
щественно проще:

program:       y.tab.c lex.yy.c
      cc -O y.tab.c -ly -ll -o program

y.tab.c:        source.y
                yacc  source.y

lex.yy.c:       source.l
                lex -v source.l
clear:
        rm -f y.tab.? lex.yy.? program


Но в файлах source.y и source.l произойдут следующие измене-
ния. В разделе входной информации для Yacc-программы необхо-
димо указать строку #include lex.yy.c,  а  из  Lex-программы
необходимо  убрать  строку  #include  "y.tab.h". Теперь файл
source.y выглядит следующим образом:

%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'


36

%left UMINUS
%{
#include "lex.yy.c"
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;  }
    |number DIGIT  { $$=base*$1+$2; }


А файл source.l выглядит следующим образом:

%{
extern int yylval;
%}
%%
^\n             ;
[ \t]*          ;
[A-Za-z]     {
       yylval = yytext[yyleng-1] - 'a';
       return(LETTER);}
[0-9]              {
       yylval = yytext[yyleng-1] - '0';
       return(DIGIT);}















                                                          37




                  9. Использование Ратфора


   Lex можно использовать для генерации программ лексическо-
го анализа на Ратфоре. Для этого в первой строке раздела оп-
ределений необходимо указать %R. Все сказанное выше  об  ис-
пользовании  Си в качестве host-языка относится и к Ратфору.
Необходимо учесть, что Ратфор имеет свою  библиотеку  ввода-
вывода. Однако, состав функций Lex для Ратфора тот же, что и
для Си. Есть и функция,  выделенная  только  для  Ратфора  -
lexshf.  Функция  lexshf  переводит внутреннее представление
символа (младший байт) из  Си  во  внутреннее  представление
символа в Фортране (старший байт).

   Дествия правил Lex-программы для  Ратфора  оформляются  в
виде  вычисляемых  goto в выходном файле, который называется
lex.yy.r.

   Допустим, имеется исходный файл source.l с Ратфором в ка-
честве host-языка, тогда для получения лексического анализа-
тора необходимы следующие действия:

        % lex source.l
        % rc lex.yy.r -llr

Напомним, что в Ратфоре индексы массивов начинаются с 1, по-
этому, например, yytex[yyleng] - это последний полученный из
входного потока символ.

































38




                       10. Флаги Lex



-t   поместить результат в стандартный файл вывода, а  не  в
     файл lex.yy.c;

-v   вывести размеры внутренних таблиц;

-f   ускорить работу, не упаковывая таблицы (только для  не-
     больших программ);

-n   не выводить размеры таблиц (устанавливается по  умолча-
     нию);

-d   используется при отладке Lex.

   Имеется возможность собрать анализатор  для  диагностики.
Для этого необходимо компиляцию файла lex.yy.c  осуществлять
с подключением разделов диагностики:

        cc -d -DLEXDEBUG  lex.yy.c

При работе полученного таким образом анализатора будет выво-
диться  диагностика действий. Флаг -d, кроме того, позволяет
проверить текст программы lex.yy.c с помощью текстового  от-
ладчика cdeb.


































                                                          39



                         СОДЕРЖАНИЕ



1.  Введение...........................................    3

2.  Регулярные выражения в Lex-правилах................    8
    2.1. Обозначения символов в выражениях.............    8
    2.2. Операторы регулярных выражений................    8
    2.3. Оператор выделения классов символов...........    9
    2.4. Повторители...................................    9
    2.5. Операторы выбора..............................   10
    2.6. Оператор {}...................................   11
    2.7. Оператор <>. Служебные слова START и BEGIN....   11

3.  Структура Lex-программы............................   14
    3.1. Раздел определений Lex-программы..............   14
    3.2. Раздел правил.................................   17
    3.2.1. Действия в правилах Lex-программы...........   18
    3.2.2. Порядок действия активных правил............   20
    3.3. Раздел программ пользователя..................   20
    3.4. Комментарии Lex-программы.....................   21
    3.5. Примеры Lex-программ..........................   21

4.  Структура файла lex.yy.c...........................   24

5.  Функция yywrap()...................................   28

6.  Функция REJECT.....................................   30

7.  Функции yyless и yymore............................   31

8.  Совместное использование Lex и Yacc................   33

9.  Использование Ратфора..............................   38

10. Флаги Lex..........................................   39

























40

