КаталогИндекс раздела
НазадОглавлениеВперед


LEX

СОДЕРЖАНИЕ

1. Обзор использования lex'а

2. Разработка lex-программ
    2.1. Основные элементы правил lex'а
        2.1.1. Спецификации
        2.1.2. Действия
    2.2. Более сложные элементы lex'а
        2.2.1. Некоторые специфические свойства
        2.2.2. Секция определений
        2.2.3. Секция подпрограмм
    2.3. Совместное использование lex'а и yacc

3. Выполнение lex'а в системе UNIX


 

1. ОБЗОР ИСПОЛЬЗОВАНИЯ LEX'А

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

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

Чтобы понять, что делает lex, изучите приведенную ниже диаграмму. Начало - это исходный lex-текст (часто называемый lex-спецификацией), который Вы, программист, пишете для решения Вашей задачи. lex-спецификация состоит из списка правил, определяющих последовательности символов (выражения), которые надо искать во входном тексте, и действия, которые надо выполнять, когда выражения найдены. Спецификация читается генератором программ lex. Результатом работы генератора является C-программа. Ее, в свою очередь, надо обработать стандартным C-компилятором, чтобы сгенерировать выполняемую объектную программу, осуществляющую лексический анализ. Отметим, что обычно эта процедура не автоматическая; требуется вмешательство пользователя.

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

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

После этого Вы сможете самостоятельно оценить мощность средств, предоставляемых lex'ом.

 

2. РАЗРАБОТКА LEX-ПРОГРАММ

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

2.1. Основные элементы правил lex'а

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

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

2.1.1. Спецификации

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

       apple
       orange
       pluto

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

       orange  ;

Так как действие справа от шаблона (перед точкой с запятой) не задано, lex не делает ничего, кроме вывода первоначального текста с удалением каждого вхождения данного регулярного выражения, то есть вообще без вхождений цепочки orange.

В отличие от orange, большинство распознаваемых выражений нельзя специфицировать так просто. Например, само выражение может быть слишком длинным. В более общем случае класс распознаваемых выражений оказывается слишком большим; на самом деле, он может быть бесконечным. Благодаря использованию операций можно формировать регулярные выражения, обозначающие любое выражение из определенного класса. Операция +, например, обозначает одно или более вхождений предшествующего выражения, ? обозначает 0 или 1 вхождение предшествующего выражения (что, конечно, эквивалентно необязательности предшествующего выражения), * обозначает 0 или более вхождений предшествующего выражения. (На первый взгляд кажется странным говорить о 0 вхождениях выражения и иметь операцию , чтобы выразить данную мысль, однако часто это весьма полезно. Ниже мы увидим соответствующий пример). Так, m+ - это регулярное выражение, которое сопоставляется с любой цепочкой из символов m, такой, как каждая из следующих:

       mmm
       m
       mmmmm
       mm

Далее, 7* - это регулярное выражение, которое сопоставляется с любой цепочкой из нуля или большего числа семерок:

       77
       77777
       
       777

Цепочка пробелов в третьей строке сопоставляется просто потому, что в ней вообще нет семерок.

Квадратные скобки, [ ], обозначают произвольный символ из цепочки символов, указанной в скобках. Так, [dgka] сопоставляется с одиночными символами d, g, k и a. Отметим, что символы в квадратных скобках не нужно разделять запятыми. Любая запятая в данном случае рассматривается как символ, который должен распознаваться во входном тексте. Диапазоны букв или цифр (в стандартном алфавитном или числовом порядке) обозначаются при помощи дефиса, -. Так, запись [a-z] обозначает произвольную строчную латинскую букву. Приведем пример более интересного регуляр- ного выражения:

       [A-Za-z0-9*&#]

Такой шаблон сопоставляется с любой латинской буквой (строчной или прописной), любой цифрой, символами *, & или #. Если входной текст имеет вид

       $$$$?? ????!!!*$$ $$$$$$&+====r~~# ((

то лексический анализатор, одно из правил которого содержит приведенный выше шаблон, распознает *, &, r и #, выполняя каждый раз действие, специфицированное в правиле (в примере действие опущено), и выводит остаток текста без изменений.

Иногда проще указать не само множество нужных символов, а его дополнение, поместив сразу за открывающей скобкой [ символ ^.

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

       [a-zA-Z][0-9a-zA-Z]*

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

       e
       pay
       distance
       pH
       EngineNo99
       R2D2

Отметим, что не будут распознаваться как идентификаторы

       not_idenTIFIER
       5times
       $hello

так как not_idenTIFIER содержит подчеркивание, 5times начинается с цифры, но не с буквы, а $hello начинается с символа $. Конечно, в качестве упражнения Вы можете написать спецификации для этих трех примеров.

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

       \*[0-9]*

Чтобы распознать сам символ \, требуется шаблон \\.

2.1.2. Действия

После того, как lex распознает цепочку, сопоставляемую с регулярным выражением, заданным в начале правила, он ищет в правой части правила действие, которое надо выполнить. Среди возможных видов действий - запись типа обнаруженной лексемы и значения, которое принимает лексема (если таковые имеются); замена одной лексемы на другую; подсчет числа вхождений лексем или типов лексем. Все, что Вы хотите проделать, нужно записать в виде фрагментов программ на языке C. Действие может состоять из произвольного числа операторов. Можно напечатать сообщение с найденным текстом или сообщение, как-то трансформирующее этот текст. Так, чтобы распознать выражение Amelia Earhart и сообщить об этом, можно специфицировать правило:

       "Amelia Earhart"        printf("нашли Amelia");

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

       Electroencephalogram    printf("EEG");

Если требуется подсчитать число строк в тексте, нужно распознавать признаки конца строк и увеличивать на единицу счетчик строк. lex использует стандартные для языка C управляющие последовательности символов, подобные \n для символа перевода строки. Для подсчета числа строк можно использовать правило

       \n      lineno++;

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

lex сохраняет каждую сопоставленную цепочку в массиве символов yytext[]. Вы можете распечатать содержимое этого массива или манипулировать им, как угодно. Иногда Ваше действие может состоять из двух или большего числа C-операторов и Вы должны (или решили из соображений стиля и ясности) написать их на нескольких строках. Чтобы информировать lex о том, что действие относится к одному правилу, надо просто заключить C-операторы в скобки. Например, чтобы подсчитать общее число всех цепочек цифр во входном тексте, печатать текущее общее число таких цепочек и выводить каждую из них, как только она обнаружена, можно воспользоваться такой записью:

       \+?[0-9]+       { digstrgcount++;
                         printf("%d",digstrngcount);
                         yytext [yyleng] = (char) 0;
                         printf("%s",yytext); }

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

2.2. Более сложные элементы lex

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

       %%
       -[0-9]+       printf("отрицательное число");
       \+?[0-9]+     printf("положительное число");
       -0\.[0-9]+    { printf("отрицательная дробь,
                             целая часть отсутствует"); }
       rail[ ]+road  printf("railroad - одно слово");
       crook         printf("Это crook");
       function      subprogcount++;
       G[a-zA-Z]*    { yytext [yyleng] = (char) 0;
                       printf("G-слово: %s", yytext);
                       Gstringcount++; }

Первые три правила распознают отрицательные числа, положительные числа и отрицательные дроби от -1 до 0. Использование + в конце каждой спецификации определяет, что рассматриваемое число составлено из одной или более цифр. Символ . является знаком операции, поэтому перед десятичной точкой в третьем правиле указан \. Каждое из трех следующих правил распознает особый шаблон. Спецификация для railroad сопоставляется в случаях, когда между двумя слогами слова вклинивается один или боле пробелов. В случаях railroad и crook можно просто печатать синоним, а не выдавать сообщения. Правило, распознающее function, увеличивает на единицу счетчик. Последнее правило иллюстрирует несколько возможностей:

2.2.1. Некоторые специфические свойства

Кроме сохранения распознанной цепочки в yytext[], lex автоматически подсчитывает число сопоставленных символов и сохраняет его в переменной yyleng. Можно использовать эту переменную, чтобы обратиться к любому отдельному символу, уже помещенному в массив yytext[]. Напомним, что в языке C элементы массива нумеруются, начиная с 0, поэтому, чтобы распечатать третью цифру в распознанном целом числе (если таковая имеется), следует написать:

       [0-9]+          { if (yyleng > 2)
                         printf("%c", yytext[2]); }

Чтобы разрешить неоднозначности, к которым может приводить совокупность заданных пользователем спецификаций, lex следует нескольким соглашениям. Подобные неоднозначности возникают, например, в ситуациях, когда цепочка символов (скажем, зарезервированное слово), может сопоставляться с шаблонами из двух правил. В примере лексического анализатора, описанном ниже в разделе Совместное использование lex и yacc, зарезервированное слово end может сопоставляться как с шаблоном из второго правила, так и с шаблоном из правила (седьмого) для идентификаторов.

Примечание

Если имеет место сопоставление с двумя или более специ- фикациями, выполняется действие, относящееся к первой из них.

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

Другая потенциальная проблема может возникнуть в случаях, когда один из распознаваемых шаблонов является началом другого. Например, два последних правила в упомянутом лексическом анализаторе служат для распознавания операций > и >=. Может возникнуть предположение, что в случае, когда текст содержит цепочку >=, лексический анализатор, обнаружив символ >, выполнит действие для шаблона >, но не станет читать следующий символ и не выполнит действие для >=.

Примечание

Сопоставляется самая длинная из подходящих цепочек символов и выполняется соответствующее действие.

В данном случае распознается операция >= и выполняется ассоциированное с ней действие. Другой пример: данное правило позволяет различить в C-программах операции + и ++.

Наконец, еще одна трудность возникает в случае, когда анализатор должен прочитать символы вне искомой цепочки, поскольку не может быть уверенным в том, что в самом деле обнаружил ее, не прочитав дополнительные символы. Такие случаи доказывают важность завершающего контекста. Классический пример - оператор DO в Фортране. При анализе оператора

       DO 50 k = 1, 20, 1

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

       DO50k = 1

есть просто оператор присваивания. (Напомним, что в Фортране пробелы игнорируются.) Для обработки ситуаций, требующих опере- жающего просмотра, используется символ / (не путать с символом \), который обозначает, что следующая за ним последовательность является завершающим контекстом и ее не следует сохранять в yytext[], поскольку она не входит в саму лексему. Правило для распознавания DO в Фортране можно записать так:

       DO/[0-9 ]*[a-zA-Z0-9 ]+=[a-zA-Z0-9 ]+, printf("нашли DO");

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

Для обозначения специального завершающего контекста - конца строки - lex использует знак операции $. (Это эквивалентно \n). Ниже приведено правило, которое игнорирует все пробелы и табуляции в конце строки:

       [ \t]+$         ;

С другой стороны, если нужно сопоставить шаблон непременно с начала строки, lex предлагает операцию ^ (это пример начального контекста). Например, в утилите форматирования nroff требуется, чтобы строка никогда не начиналась с пробела, поэтому для проверки входных данных nroff можно использовать такое правило:

       ^[ ]    printf("ошибка: удалите начальные пробелы");

Наконец, для выполнения некоторых действий может потребоваться прочитать еще один символ, возвратить символ обратно для последующего повторного прочтения или вывести символ на устройство вывода. lex предоставляет для этих целей три функции - input(), unput(c) и output(c) соответственно. Один из способов пропустить все символы между двумя специальными символами, скажем, между парой двойных кавычек, заключается в использовании input():

       \"      while (input() != '"');

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

Для выполнения специальных операций ввода/вывода можно переписать функции input(), unput(), и output(), используя стандартные для языка C средства вода/вывода. Эти и другие определенные программистом функции следует поместить в секцию подпрограмм. В таком случае новые подпрограммы заменят стандартные. Стандартная функция input(), в действительности, эквивалентна getchar(), а стандартная функция output() - putchar().

В lex'е имеется ряд подпрограмм, которые предоставляют возможность многократной обработки цепочек символов. Это функции yymore() и yyless(n) и действие REJECT. Повторим, что текст, сопоставленный с некоторой спецификацией, помещается в массив yytext[]. В общем случае, после того как выполнено действие для данной спецификации, символы в yytext[] замещаются последующими символами входного потока, образующими следующую сопоставляемую цепочку. Функция yymore(), напротив, гарантирует, что последующие распознаваемые символы будут добавляться после тех, которые уже содержатся в yytext[]. Тем самым в случае, когда значимыми оказываются как одна цепочка символов, так и другая, более длинная, включающая первую, появляется возможность выполнить сначала одно действие, а потом другое, ассоциированное с длинной цепочкой.

В качестве примера рассмотрим словарь, в котором чередуются английские слова и их русские эквиваленты. Слова (как английские, так и русские) разделяются запятыми; запятые стоят также в начале и конце словаря. Требуется распечатать содержимое словаря в виде пар (английское слово, русский эквивалент). К цели ведет следующее правило:

       ,[^,]*  { if (flag == 0) {
                   flag = 1;
                   yymore();
                 }
                 else {
                   flag = 0;
                   yytext [yyleng] = (char) 0;
                   printf ("%s\n", &yytext[1]);
                 }
               }

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

Функция yyless(n) позволяет переустановить указатель конца обработанных символов на символ, оказавшийся n-м в массиве yytext[]. Предположим, что мы занимаемся расшифровкой кода и уловка заключается в том, чтобы обрабатывать только половину символов в последовательности, заканчивающейся определенным символом, например, прописной или строчной буквой z. Достаточно воспользоваться правилом

       [a-yA-Y]+[Zz]   { yyless(yyleng/2);
                        ...обработка первой половины цепочки...}
Наконец, действие REJECT упрощает обработку цепочек символов в случаях, когда они перекрываются или одна является частью другой. Выполнение REJECT заключается в немедленном переходе к следующему правилу без изменения содержимого yytext[]. Например, для подсчета числа вхождений в тексте как цепочки символов snapdragon, так и ее подцепочки dragon, можно использовать правило
       snapdragon      { countflowers++; REJECT; }
       dragon          countmonsters++;

В следующем примере, иллюстрирующем частичное перекрытие двух шаблонов, подсчитывается число вхождений цепочек comedian и diana, причем правильно обрабатываются даже такие входные цепочки, как comediana...:

       comedian        { comiccount++; REJECT; }
       diana           princesscount++;

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

2.2.2. Секция определений

Секция определений может содержать конструкции разных видов, самыми важными из которых являются описания внешних объектов, операторы #include и сокращения. Напомним, что в принципе данная секция необязательна, однако в большинстве случаев некоторые определения необходимы. Описания внешних объектов имеют те же форму и смысл, что и в языке C. Они означают, что переменные, глобально определенные где-то в другом месте (возможно, в другом исходном файле), будут доступны в сгенерированной lex-программе a.out. Рассмотрим определение из примера, который обсуждается ниже:

       extern int tokval;

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

Назначение оператора #include - то же, что и в языке C: включать в программу нужные файлы. Некоторые описания могут требоваться более чем в oодном исходном lex-файле, поэтому предпочтительно поместить их в один файл, включаемый в нужных случаях. Примером может служить использование lex'а совместно с yacc(1), который генерирует функции разбора, вызывающие лексический анализатор. В такой ситуации следует включать файл y.tab.h, поскольку он может содержать операторы #define для имен лексем. Подобно описаниям, операторы #include должны содержаться между скобками %{ и %}:

       %{
       #include "y.tab.h"
       extern int tokval;
       int lineno;
       %}

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

Примечание

Назначение сокращений - избежать излишних повторов при написании спецификаций и улучшить их читаемость.

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

       D               [0-9]
       L               [a-zA-Z]
       B               [ ]
       %%
       -{D}+           printf("отрицательное число");
       \+?{D}+         printf("положительное число");
       -0\.{D}+        printf("отрицательная дробь");
       G{L}*           printf("G-слово");
       rail{B}+road    printf("railroad - одно слово");
       crook           printf("не положено");
       \"\./{B}+       printf(".\"");
         . . .               . . .

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

2.2.3. Секция подпрограмм

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

Иногда подпрограмму помещают в эту секцию по методологическим соображениям - чтобы выделить некоторую часть действий или упростить секцию правил, даже если данное действие используется только в одном правиле. В качестве примера рассмотрим следующую подпрограмму, которая пропускает комментарии в языке, подобном C, где комментарии выделяются символами /* и */:

       "/*"    skipcmnts();
         . . .         /* Остальные правила */
       %%
       skipcmnts ()
       {
         for (;;) {
           while (input () != '*') ;
           if (input () != '/') {
             unput (yytext [yyleng-1]);
           }
           else return;
         }
       }

В этом примере затронуты три интересных вопроса. Во-первых, функция unput(c) (возвратить последний прочитанный символ) нужна, чтобы правильно обработать комментарии, заканчивающиеся комбинацией символов **/. Во-вторых, выражение yytext [yyleng-1] используется для выборки последнего прочитанного символа. В-третьих, в рассматриваемой подпрограмме предполагается, что комментарии не могут быть вложены. (Для языка C это действительно так.) Если, в отличие от C, в исходном тексте комментарии вложены, после распознавания цепочки */, закрывающей внутренний комментарий, сгенерированная программа будет продолжать чтение оставшейся части комментариев, как если бы это была часть текста, которую надо распознавать.

Другими примерами подпрограмм могут служить заданные программистом варианты обсуждавшихся выше функций ввода/вывода input(), unput() и output(). Подобные функции могут использоваться во многих программах, поэтому, вероятно, лучше всего было бы поместить их в отдельный файл или библиотеку и вызывать по мере необходимости. При этом в секцию определений следовало бы поместить соответствующие операторы #include.

2.3. Совместное использование lex'а и yacc

При работе над компилятором или программой, проверяющей правильность исходного текста, целесообразно воспользоваться мощным инструментальным средством системы UNIX - yacc(1). yacc генерирует функции синтаксического разбора и программы, анализирующие входной текст с целью убедиться в его синтаксической корректности. При разработке компиляторов объединение lex'а и yacc'а часто оказывается плодотворным. Даже если Вы пока не предполагаете использовать lex вместе с yacc, обязательно прочитайте этот раздел, так как он содержит информацию, интересную для всех пользователей lex'а.

Процедура лексического анализа, которую генерирует lex, (но не файл, в котором она сохраняется), имеет имя yylex(). Это удобно, поскольку yacc обращается к лексическому анализатору как раз по этому имени. При использовании lex'а для создания лексического анализатора в компиляторе следует завершать каждое lex- действие оператором return лексема, где лексема - введенное обозначение некоторого целочисленного значения. Возвращаемое значение лексемы указывает процедуре разбора, какую цепочку обнаружил лексический анализатор. Процедура разбора, которую yacc помещает в файл y.tab.c, вновь получает управление и выполняет очередное обращение к лексическому анализатору, когда ей требуется очередная лексема.

При компиляции различные значения обозначают типы лексем, то есть показывают, является ли лексема определенным зарезервированным словом, идентификатором, константой, арифметической операцией или операцией сравнения. Во всех перечисленных случаях, кроме первого, анализатор, кроме того, должен указать точное значение лексемы: какой именно идентификатор обнаружен, какая константа, скажем, 10 или 1812, какая арифметическая операция, + или * (умножение), какая операция сравнения, = или >. Рассмотрим следующий фрагмент lex-спецификации лексического анализатора для некоторого языка программирования, несколько напоминающего язык Ада:

       begin                   return (BEGIn);
       end                     return (END);
       while                   return (WHILE);
       if                      return (IF);
       package                 return (PACKAGE);
       reverse                 return (REVERSE);
       loop                    return (LOOP);
       [a-zA-Z][a-zA-Z0-9]*    { tokval = put_in_tabl ();
                                 return (IDENTIFIER); }
       [0-9]+                  { tokval = put_in_tabl ();
                                 return (INTEGER); }
       \+                      { tokval = PLUS;
                                 return (ARITHOP); }
       \-                      { tokval = MINUS;
                                 return (ARITHOP); }
       >                       { tokval = GREATER;
                                 return (RELOP); }
       >=                      { tokval = GREATEREQL;
                                 return (RELOP); }

Классы лексем и значения, присваиваемые переменной tokval, обозначены именованными целочисленными константами, что облегчает понимание и модификацию правил. Соответствие между именами и значениями констант устанавливается при помощи операторов #define в C-процедуре разбора. Пример:

       #define BEGIn   1
       #define END     2
         . . .
       #define PLUS    7
         . . .

(В имени BEGIn последняя буква сделана строчной, поскольку имя BEGIN зарезервировано lex'ом.) При использовании yacc'а целесообразно вставить оператор

       #include "y.tab.h"

в секцию определений lex-спецификаций. Файл y.tab.h содержит операторы #define, связывающие имена лексем, такие, как BEGIn, END и т.д. с целочисленными значениями, имеющими смысл для сгенерированной процедуры разбора.

В нашем примере для того, чтобы однозначно задать зарезервированное слово, достаточно возвращаемого значения. Для других типов лексем значение лексемы сохраняется в определенной программистом переменной tokval. Эта переменная описывается в секции определений как глобальная, доступная и процедуре лексического анализа, и процедуре синтаксического разбора. yacc для этих же целей предоставляет переменную yylval.

Отметим, что в примере показано два способа установки значения переменной tokval. В соответствии с первым способом функция put_in_tabl() заносит имя и тип идентификатора или константы в таблицу символов, к которой компилятор имеет доступ на этой и следующих стадиях процесса компиляции. Кроме того, put_in_tabl() выдает в качестве результата имя идентификатора или значение константы; этот результат присваивается переменной tokval. Предполагается, что функция put_in_tabl() помещается разработчиком компилятора в секцию подпрограмм. При втором способе, например, в нескольких последних действиях примера, переменной tokval присваивается определенное число, обозначающее, какую операцию распознал анализатор. Если PLUS в соответствии с приведенным выше оператором #define обозначает семерку, то при обнаружении знака + переменной tokval будет присвоено значение 7, характеризующее +. Значение, возвращаемое процедуре разбора, обозначает целый класс операций (в нашем примере - значения ARITHOP и RELOP).

 

3. ВЫПОЛНЕНИЕ LEX'А В СИСТЕМЕ UNIX

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

       lex  файл

где файл содержащит lex-спецификацию. Обычно в качестве имени файла берется lex.l, однако в принципе имя файла может быть любым. Порожденный lex'ом выходной файл будет автоматически назван lex.yy.c. Он содержит созданную C-программу лексического анализа, которую следует откомпилировать и выполнить редактирование связей с обязательным подключением библиотеки lex'a libl.a, что достигается указанием опции -ll:

       cc  lex.yy.c -ll

Библиотека предоставляет недостающую программу main(), которая по имени yylex вызывает лексический анализатор, так что создавать свою собственную программу main() нет необходимости.

Если lex-спецификация состоит из нескольких файлов, можно для каждого из них запустить lex, обязательно переименовывая результирующий файл lex.yy.c [при помощи команды mv(1)] перед следующим запуском lex'а. В противном случае каждый следующий результат будет затирать предыдущий. После того как все .c-файлы сгенерированы, можно скомпилировать их все разом посредством одной командной строки.

Если выполняемый файл a.out порожден, с его помощью можно проанализировать любой входной текст. Предположим, текст помещен в файл с именем textin (имя выбирается произвольно). Лексический анализатор по умолчанию осуществляет ввод с терминала. Чтобы использовать файл textin, достаточно переназначить ввод:

       a.out  < textin

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

       a.out  < textin > textout

При использовании lex'а совместно с yacc'ом любой из инструментов может быть запущен первым. Команды

       yacc  -d grammar.y
       lex  lex.l

формируют процедуру разбора в файле y.tab.c. (Если указана опция -d, создается файл y.tab.h, который содержит операторы #define, связывающие назначенные yacc'ом целочисленные значения типов лексем с определенными пользователем именами лексем). Чтобы откомпилировать порожденные файлы и отредактировать связи, введите командную строку

       cc  lex.yy.c y.tab.c -ly -ll

Заметим, что библиотека yacc'а загружается (опция -ly) перед библиотекой lex'а (опция -ll), что гарантирует использование той программы main(), которая вызывает процедуру разбора.

У команды lex есть несколько допустимых опций, которые следует указывать между именем команды lex и именем файла-аргумента. Для того, чтобы lex выводил сгенерированную C-программу lex.yy.c на терминал (устройство вывода, заданное по умолчанию), используется опция -t:

       lex  -t lex.l

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

Для представления конечного автомата lex использует таблицу (двумерный массив в C). Максимально возможное число состояний конечного автомата по умолчанию устанавливается равным 500. Если lex-спецификация содержит много правил или очень сложные правила, может потребоваться большее число состояний. Увеличение максимального числа состояний достигается добавлением к секции определений строки вида

       %n 700

Подобная строка заставляет lex сделать таблицу достаточно большой, чтобы вместить до 700 состояний. (Опция -v позволит узнать, какое число состояний было фактически использовано). Для того, чтобы увеличить максимально допустимое число переходов между состояниями с подразумеваемого значения 2000, предусмотрен параметр a:

       %a 2800

В заключение рекомендуем изучить статью lex(1) из Справочника пользователя, в которой содержится список всех опций, предусмотренных у данной команды. Описание нотации регулярных выражений можно найти, например, в статье ed(1) Справочника пользователя.

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


НазадОглавлениеВперед
КаталогИндекс раздела