Производственно-внедренческий кооператив
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/P 2.1
Генератор программ лексического анализа lex
Москва
1988
Аннотация
В документе описан язык программирования lex, предназ-
наченный для разработки программ лексического анализа. При-
водятся правила работы с компилятором языка lex ОС ДЕМОС.
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-генератор, в свою очередь, генерирует
программу лексического анализа на каком-либо другом языке.
4
Данная версия lex генерирует лексические анализаторы на язы-
ках Си и Ратфор (рациональный диалект Фортрана). В качестве
host-языка мы будем использовать язык Си. Сведения об
использовании в качестве host-языка Ратфор выделены в
отдельный параграф.
В каталоге /usr/lib/lex имеется файл-заготовка ncform,
который используется Lex-генератором для построения лекси-
ческого анализатора. Этот файл является уже готовой прог-
раммой лексического анализа, но в нем не определены дейст-
вия, которые необходимо выполнить при распознавании лексемы,
отстутствуют и сами лексемы, не сформированы рабочие массивы
и т.д.
lex на основе Lex-программы достраивает файл ncform. В
результате мы получаем файл со стандартным именем lex.yy.c,
который является текстом Си-программы, осуществляющей лекси-
ческий анализ.
Lex-программа имеет следующий формат:
определения
%%
правила
%%
подпрограммы, составленные
пользователем
Любой из этих разделов может быть пустым. Простейшая Lex-
программа имеет вид:
%%
Здесь нет никаких определений и никаких правил.
Все разделы Lex-программы мы подробно рассмотрим ниже.
Сейчас целесообразно рассмотреть, что представляют собой
правила.
Правило состоит из двух частей:
РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
По регулярным выражениям, содержащимся в левой части правил,
lex строит детерминированный конечный автомат. Этот автомат
осуществляет интерпретацию, а не компиляцию. Количество пра-
вил и их сложность не влияют на скорость лексического ана-
лиза, если только правила не требуют слишком большого объема
повторных просмотров входной последовательности символов.
Однако, с ростом числа правил и их сложности растет размер
конечного автомата, интерпретирующего их и, следовательно,
растет размер Си-программы, реализующей этот конечный авто-
мат.
5
Рассмотрим в качестве примера следующую 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("Август"); }
[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-программы - это
вывод русского значения найденного английского слова. В
качестве оператора, выполняющего действие, используется биб-
лиотечная функция языка Си.
6
Пара фигурных скобок определяет блок (в смысле языка
Си), который может содержать любое количество строк. Если
действие содержит всего одну строку Си, то можно ее указать
без фигурных скобок, как обычно. Единственное условие - она
должна начинаться в той же строке, где указано регулярное
выражение.
В программе содержится только раздел правил, их всего
19. Регулярное выражение каждого правила определяет английс-
кое слово, написанное маленькими или большими латинскими
символами. Например "May" (Май) определен как
"[mM][aA][yY]". По этому регулярному выражению будет выде-
лена во входном потоке символов лексема "May", а по действию
этого правила будет выведено "Май". Наличие большой и малой
буквы в квадратных скобках обеспечивает распознавание слова
"May", написанного любыми латинскими символами.
Таким образом, данная Lex-программа строит Си-
программу, которая переводит на русский язык имена месяцев и
дней недели.
Допустим, Lex-программа размещена в файле source.l,
тогда, чтобы получить лексический анализатор на Си, необхо-
димо выполнить следующий набор команд:
% 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. Если необходимо получить самостоятельную
программу, как в данном случае, подключение библиотеки
7
обязательно, поскольку тогда из нее подключается головной
раздел main. В противном случае, если имеется необходимость
включить анализатор в качестве функции в другую программу
(например, в программу грамматического разбора), эту библио-
теку необходимо вызвать уже при сборке и тогда, если main
определен в вызывающей лексический анализатор программе,
редактор связей не будет подключать раздел main из библио-
теки lex.
Если необходимо получить файл с именем, отличным от
lex.yy.c, можно воспользоваться флагом -t :
% lex -t source.l >> file
По этому флагу результат поступает в файл file.
2. Регулярные выражения в Lex-правилах
Регулярные выражения определяют лексему. Регулярное
выражение может содержать символы латинского и русского
алфавитов в верхнем и нижнем регистрах, другие символы
(цифры, знаки препинания и т.д.) и символы-операторы.
Операторы позволяют осуществлять различные действия над
выделенной цепочкой символов. Операторы также обозначаются
символами.
2.1. Обозначения символов в выражениях
В выражении можно использовать любой символ. Символ
можно указывать в двойных кавычках. В этом случае это всегда
просто символ - его специальное значение отменяется. Напри-
мер:
"abc"
abc
эти последовательности символов идентичны.
. точка означает любой символ, кроме символа новой строки
"\n";
\восьмеричный_код_символа
указание символа его восьмеричным кодом (как в Си);
\n символ новой строки;
\t символ табуляции;
\b возврат курсора на один шаг назад;
8
пробел
любой символ пробела в выражении, если он не находится
внутри квадратных скобок, необходимо заключать в двой-
ные кавычки. Это необходимо, так как пробел и табуляция
используются lex в качестве разделителя между определе-
нием и действием в правиле.
2.2. Операторы регулярных выражений
Операторы обозначаются символами-операторами, к ним
относятся:
\ ^ ? * + | $ / %
[] {} () <<>>
Каждый из этих символов или пар скобок в регулярном выраже-
нии играет роль оператора. Если необходимо отменить специ-
альное значение символа, обозначающего оператор, перед ним
нужно поставить символ \ или указать его в двойных кавычках.
Например:
abc+ - символ "+" - оператор;
abc\+ - символ "+";
abc"+" - символ "+".
2.3. Оператор выделения классов символов
Квадратные скобки задают классы символов, которые в них
заключены.
[abc]
означает либо символ "a", либо "b", либо символ "c";
Знак - используется для указания любого символа из лек-
сикографически упорядоченной последовательности:
[A-z]
означает любой латинский символ;
[А-Я]
любая прописная русская буква;
[+-0-9]
все цифры и знаки "+" и "-".
2.4. Повторители
Когда необходимо указать повторяемость вхождения сим-
вола в регулярном выражении, используют операторы-
повторители * и +.
9
Оператор * означает любое (в том числе и 0) число вхож-
дений символа или класса символов. Например:
x* любое число вхождений символа "x";
abc* любое число вхождений цепочки "abc";
[A-z]*
любое число вхождений любой латинской буквы;
[A-ZА-Яa-zа-я_0-9]*
любое вхождение русских и латинских букв, знака подчер-
кивания и цифр.
Оператор + означает одно и более вхождений. Например:
x+ одно или более вхождений "x";
[0-9]+
одно или более вхождений цифр;
abc+ одно или более вхождений цепочки abc;
[A-z]+
одно или более вхождений любой латинской буквы.
2.5. Операторы выбора
Операторы:
/ | ? $ ^
управляют процессом выбора символов.
Оператор /:
ab/cd
"ab" учитывается только тогда, когда за ним следует
"cd".
Опeратор |:
ab|cd
или "ab", или "cd".
Опeратор ?:
x? означает необязательный символ "x".
_?[A-Za-z]*
означает, что перед цепочкой любого количества латинс-
ких букв может быть необязательный знак подчеркивания.
10
-?[0-9]+
выделит любое целое число с необязательным минусом впе-
реди.
Оператор $:
x$ означает выбрать символ "x", если он является последним
в строке. Стоит перед символом "\n"!
abc$ означает выбрать цепочку "abc", если она завершает
строку.
Оператор ^:
^x означает выбрать символ "x", если он является первым
символом строки;
^abc означает выбрать цепочку символов "abc", если она начи-
нает строку.
[^A-Z]*
означает все символы, кроме прописных латинских букв.
Когда символ ^ стоит перед выражением или внутри [], он
выполняет операцию дополнение. Внутри квадратных скобок
символ ^ должен обязательно стоять первым у открывающей
скобки!
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])*.
11
yytext - это внешний массив символов программы
lex.yy.c, которую строит lex. yytext формируется в процессе
чтения входного файла и содержит текст, для которого уста-
новлено соответствие какому-либо выражению. Этот массив дос-
тупен пользовательским разделам Lex-программы.
Оператор printf выводит каждый идентификатор на новой
строке.
Правило ".|\n ;" используется для того, чтобы
пропустить (не выводить) все цепочки символов, которые не
соответствуют регулярному выражению {ИДЕНТИФИКАТОР}.
2.7. Оператор <<>>. Служебные слова START и BEGIN
Раздел правил Lex-программы может содержать активные и
неактивные правила. Активные правила выполняются всегда.
Неактивные выполняются только в тех случаях, когда выполня-
ется некоторое начальное условие.
Начальные условия Lex-программы помещаются в раздел
определений, а неактивные правила помечаются соответствую-
щими условиями. Оператор START позволяет указать список
начальных условий Lex-программы, а оператор BEGIN позволяет
активировать правила, помеченные начальными условиями.
Активные правила имеют следующий синтаксис:
РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
Неактивные правила имеют следующий синтаксис:
<<МЕТКА_УСЛОВИЯ>>РЕГ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
ВАЖНО: любое правило должно начинаться с первой позиции
строки, пробелы и табуляции недопустимы - они используются
как разделители между регулярным выражением и действием в
правиле!
Рассмотрим пример:
12
%START COMMENT
КОММ_НАЧАЛО "/*"
КОММ_КОНЕЦ "*/"
%%
{КОММ_НАЧАЛО} { ECHO;
BEGIN COMMENT;};
[\t\n]* ;
<COMMENT>[^*]* ECHO;
<COMMENT>[^/] ECHO;
<COMMENT>{КОММ_КОНЕЦ} {
ECHO;
printf("0);
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-программа начинается
строкой
%START AA BB CC DD
то это означает, что она управляет четырьмя начальными сос-
тояниями анализатора. В каждое из этих начальных состояний
анализатор можно перевести, используя оператор BEGIN.
13
Каждое правило, перед которым указан оператор типа
"<<МЕТКА>>", мы будем называть помеченным правилом. Метка фор-
мируется так же, как и метка в Си.
Количество помеченных правил не ограничивается. Кроме
того, разрешается одно правило помечать несколькими метками,
например:
<<МЕТКА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, распозна-
вая, с аргументами она или без них, распознавать метки.
Лексический анализатор не выводит ничего, кроме сообщений о
выделенных лексемах.
14
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})*
Имя - как обычно, любая последовательность букв и цифр,
начинающаяся с буквы. Трансляция - это регулярное выражение
(или его часть), которое будет подставлено всюду там, где
указано имя (смотрите третью строку этого примера).
15
ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя спо-
собами:
- в виде "пробел фрагмент";
- в виде:
%{
строки
фрагмента
программы
пользователя
%}
Такая форма включения пользовательского фрагмента
необходима для ввода, например, макроопределений Си,
которые должны начинаться в первой колонке строки.
Все строки фрагмента пользовательской программы, раз-
мещенные в разделе определений, будут являться внеш-
ними для любой функции программы lex.yy.c
ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде:
%T
целое_число строка_символов
.........
целое_число строка_символов
%T
Сгенерированная программа lex.yy.c осуществляет ввод-вывод
символов посредством библиотечных функций lex с именами
input, output, unput. Таким образом, lex помещает в yytext
символы в представлении, используемом в этих библиотечных
функциях. Для внутреннего использования символ представля-
ется целым числом, значение которого образовано набором
битов, представляющих символ в конкретной ЭВМ. Пользователю
предоставляется возможность менять представление символов
(целых констант) с помощью таблицы наборов символов. Если
таблица символов присутствует в разделе определений, то
любой символ, появляющийся либо во входном потоке, либо в
правилах, должен быть определен в таблице символов. Символам
нельзя назначать число 0 и число, большее числа, выделенного
для внутреннего представления символов конкретной ЭВМ.
Пример:
16
%T
1 Aa
2 Bb
3 Cc
.
.
.
26 Zz
27
28 +
29 -
30 0
31 1
.
.
.
39 9
%T
В этом примере символы верхнего и нижнего регистров перево-
дятся в числа 1-26, символ новой строки в 27, "+" и "-"
переводятся в числа 28 и 29, а цифры - в числа 30-39.
ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме:
%x число
число - новый размер массива;
x - одна из букв:
p - позиции;
n - состояния;
e - узлы дерева;
a - упакованные переходы;
k - упакованные классы символов;
o - массив выходных элементов.
lex имеет внутренние таблицы, размеры которых ограничены.
При построении программы лексического анализа может прои-
зойти переполнение любой из этих таблиц, о чем lex сообщает
при построении лексического анализатора. Пользователю пре-
доставляется возможность изменить размеры таблиц (сокращая
размеры одних и увеличивая размеры других) таким образом,
чтобы они не переполнялись. Естественно, эти изменения воз-
можны лишь в пределах той памяти, которая выделяется под
процесс.
Ниже перечислены размеры таблиц, которые устанавлива-
ются по умолчанию:
17
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.
Число перед символом "/" указывает сколько элементов массива
занято, а число за символом "/" указывает установленный раз-
мер массива.
КОММЕНТАРИИ в разделе определений задаются в форме
host-языка и должны начинаться не с первой колонки строки.
3.2. Раздел правил
Все, что указано после первой пары %% и до конца Lex-
программы или до второй пары %%, если она указана, относится
к разделу правил. Раздел правил может содержать правила и
фрагменты программ. Фрагменты программ, содержащиеся в раз-
деле правил, становятся частью функции yylex файла lex.yy.c,
в которой осуществляется выполнение действий активных пра-
вил. Фрагмент программы указывается следующим образом:
%{
строки
фрагмента
программы
%}
Например:
%%
%{
#include file.h
%}
.
.
.
18
Здесь строка "#include file.h" станет строкой функции
yylex().
Раздел правил может включать список активных и неактив-
ных (помеченных) правил. Активные и неактивные правила
могут быть указаны в любом порядке, в том числе быть "пере-
мешанными" в списке. Активные правила выполняются всегда,
неактивные только по ссылке на них оператором BEGIN.
Активное правило имеет вид:
ВЫРАЖЕНИЕ ДЕЙСТВИЕ
Неактивное правило имеет вид:
<МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
или
<СПИСОК_МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ
где СПИСОК_МЕТОК имеет вид:
метка1,метка2,...
В качестве первого правила раздела правил может быть правило
вида:
BEGIN МЕТКА;
В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым действием в
разделе правил будет активизация помеченных правил. Для
возвращения автомата в исходное состояние можно использовать
действие:
BEGIN 0;
Важно отметить следующее. Если Lex-программа содержит актив-
ные и неактивные правила, то активные правила работают
всегда. Оператор "BEGIN МЕТКА;" просто расширяет список
активных правил, активируя помеченные меткой МЕТКА. А опера-
тор "BEGIN 0;" удаляет из списка активных правил все поме-
ченные правила, которые до этого были активированы. Кроме
того, если из помеченного и активного в данный момент вре-
мени правила осуществляется действие BEGIN МЕТКА, то из
помеченных правил активными останутся только те, которые
помечены меткой МЕТКА.
3.2.1. Действия в правилах Lex-программы
Действие можно представлять либо как оператор lex, нап-
ример, "BEGIN МЕТКА;", либо как оператор Си. Если имеется
необходимость выполнить достаточно большой набор преобразо-
ваний, то действие оформляют как блок Си-программы (он
19
начинается открывающей фигурной скобкой и завершается закры-
вающей фигурной скобкой), содержащий необходимые фрагменты.
Действие в правиле указывается через не менее, чем один
пробел или табуляцию после выражения (обязательно в той же
строке, где и выражение), а его продолжение может быть ука-
зано в следующих строках только в том случае, если действие
оформлено как блок Си-программы.
Область действия переменных, объявленных внутри блока,
распространяется только на этот блок. Внешними переменными
для всех действий будут являться только те переменные, кото-
рые объявлены в разделе определений Lex-программы.
Действия в правилах Lex-программы выполняются, если
правило активно, и если автомат распознает цепочку символов
из входного потока как соответствующую регулярному выражению
данного правила. Однако, одно действие выполняется всегда -
оно заключается в копировании входного потока символов в
выходной. Это копирование осуществляется для всех входных
строк, которые не соответствуют правилам, преобразующим эти
строки. Комбинация символов, не учтенная в правилах и поя-
вившаяся на входе, будет напечатана на выходе. Можно ска-
зать, что действие - это то, что делается вместо копирования
входного потока символов на выход. Часто бывает необходимо
не копировать на выход некоторую цепочку символов, которая
удовлетворяет некоторому регулярному выражению. Для этой
цели используется пустой оператор Си, например:
[ 0 ;
Это правило игнорирует (запрещает) вывод пробелов, табуляций
и символа новая строка. Запрет выражается в том, что на
указанныe символы во входном потоке осуществляется действие
";" - пустой оператор Си, и эти символы не копируются в
выводной поток символов.
Существует возможность для нескольких регулярных выра-
жений указывать одно действие. Для этого используется символ
"|", который указывает, что действие данного правила совпа-
дает с действием для следующего, например:
" " |
|
;
Результат будет тот же, что и в примере, указанном выше.
Когда необходимо вывести или преобразовать текст, соот-
ветствующий некоторому регулярному выражению, используется
внешний массив символов, который формирует lex. Называется
он yytext и доступен в действиях правил. Например:
20
[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;}
Здесь ведется подсчет числа распознанных слов и количества
символов во всех словах.
3.2.2. Порядок действия активных правил
Список правил Lex-программы может содержать активные и
неактивные правила, размещенные в любом порядке в разделе
правил. В процессе работы лексического анализатора список
активных правил может видоизменяться за счет действий опера-
тора BEGIN. В процессе распознавания символов входного
потока может оказаться так, что одна цепочка символов будет
удовлетворять нескольким правилам и, следовательно, возни-
кает проблема: действие какого правила должно выполняться?
Для разрешения этого противоречия можно использовать
квантование (разбиение) регулярных выражений этих правил
Lex-программы на такие новые регулярные выражения, которые
дадут, по возможности, однозначное распознавание лексемы.
Однако, когда это не сделано, lex использует определенный
детерминированный механизм разрешения такого противоречия:
- выбирается действие того правила, которое распознает
наиболее длинную последовательность символов из вход-
ного потока;
21
- если несколько правил распознают последовательности
символов одной длины, то выполняется действие того
правила, которое записано первым в списке раздела
правил Lex-программы.
Рассмотрим пример:
.
.
.
[Мм][Аа][Йй] ECHO;
[А-Яа-я]+ ECHO;
.
.
.
Слово "Май" распознают оба правила, однако, выполнится пер-
вое из них, так как и первое, и второе правило распознали
лексему одинакового размера (3 символа). Если во входном
потоке будет, допустим, слово "майский", то первые 3 символа
удовлетворяют первому правилу, а все 7 символов удовлетво-
ряют второму правилу, следовательно, выполнится второе пра-
вило, так как ему удовлетворяет более длинная последователь-
ность символов.
3.3. Раздел программ пользователя
Все, что размещено за вторым набором %%, относится к
разделу программ пользователя. Содержимое этого раздела
копируется в выходной файл lex.yy.c без каких-либо измене-
ний. В файле lex.yy.c строки этого раздела рассматриваются
как функции в смысле Си. Эти функции могут вызываться в
действиях правил и, как обычно, передавать и возвращать зна-
чения аргументов.
3.4. Комментарии Lex-программы
Комментарии можно указывать во всех разделах Lex-
программы. Формат комментариев должен соответствовать фор-
мату комментариев host-языка. Однако, в каждом разделе Lex-
программы комментарии указываются по разному. В разделе
определений комментарии должны начинаться не с первой пози-
ции строки. В разделе правил комментарии можно указывать
только внутри блоков, принадлежащих действиям. В разделе
программ пользователя комментарии указываются как и в host-
языке.
3.5. Примеры Lex-программ
Пример1.
22
%Start KOMMENT
/*
* Программа записывает в
* стандартный файл вывода
* комментарии Си-программы.
* Обратите внимание на то, что
* здесь строки комментариев указаны
* не с первой позиции строки!
*/
КОММ_НАЧАЛО "/*"
КОММ_КОНЕЦ "*/"
%%
{КОММ_НАЧАЛО} { ECHO;
BEGIN KOMMENT;}
[0* ;
<KOMMENT>[^*]* ECHO;
<KOMMENT>[^/] ECHO;
<KOMMENT>{КОММ_КОНЕЦ} {
ECHO;
printf("0);
/*
* Здесь приведен пример
* использования комментариев в
* разделе правил Lex-программы.
* Обратите внимание на то, что
* комментрий указан внутри блока,
* определяющего действие правила.
*/
BEGIN 0;}
%%
/*
* Здесь приведен пример комментариев
* в разделе программ пользователя.
*/
Пример 2.
23
%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 [ 0*
%%
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 );
24
<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 );
<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>[ 0] ;
%%
x( s )
char *s ;
{
25
printf("%-15.15s 177> %s <1770,
s, yytext ) ;
}
4. Структура файла lex.yy.c
lex строит программу - лексический анализатор на языке
Си, которая размещается в файле со стандартным именем
lex.yy.c. Эта программа содержит две основных функции и нес-
колько вспомогательных. Основные - это:
функция yylex()
Она содержит разделы действий всех правил, которые
определены пользователем;
функция yylook()
Она реализует детерминированный конечный автомат, кото-
рый осуществляет разбор входного потока символов в
соответствии с регулярными выражениями правил Lex-
программы.
Вспомогательные функции, которые являются подпрограм-
мами ввода-вывода. К ним относятся:
input()
читает и возвращает символ из входного потока символов;
unput(c)
возвращает символ обратно во входной поток для повтор-
ного чтения;
output(c)
выводит в выходной поток символ c.
Эти функции определены как макроподстановки следующим
образом:
input -
fprintf( fout, "%s%d%s0,
"#define input() (((yytchar=yysptr>yysbuf
ctable['0],
"?(yylineno++,yytchar):yytchar)==EOF?0:yyt
unput -
26
#define unput(c){
yytchar = (c);
if( yytchar == '\n' ) yylineno--;
*yysptr++ = yytchar;
}
output -
#define output(c) putc(c,yyout)
Эти функции можно изменить, указав им те же имена и
разместив в разделе программ пользователя.
При сборке программы лексического анализа редактор
связи ld по флагу -ll подключает головную функцию main, если
она не определена. Ниже приведен текст этой функции из биб-
лиотеки /usr/lib/libl.a
# include "stdio.h"
main(){
yylex();
exit(0);
}
5. Функция yywrap()
Функция yywrap используется для определения конца
файла, из которого лексический анализатор читает поток сим-
волов. Если yywrap возвращает 1, лексический анализатор
прекращает работу. Однако, иногда имеется необходимость
начать ввод данных из другого источника и продолжить работу.
В этом случае пользователь должен написать свою подпрограмму
yywrap, которая организует новый входной поток и возвращает
0, что служит сигналом к продолжению работы анализатора. По
умолчанию yywrap всегда возвращает 1 при завершении входного
потока символов.
В Lex-программе невозможно записать правило, которое
будет обнаруживать конец файла. Единственный способ это сде-
лать - использовать фунцию yywrap. Эта функция также удобна,
когда необходимо выполнить какие-либо действия по завершению
входного потока символов, определив в разделе программ поль-
зователя новый вариант функции yywrap. Пример:
27
%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++; }
%%
yywrap(){
if( b1 == 0 && b2 == 0 )
printf("В программе\
отсутствует функция main.\n");
if( b1 >= 1 && b2 >= 1 ){
printf("Многократное\
определение функции main.\n");
} else {
if(b1 == 1 )
printf("Функция main\
28
с аргументами.\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, то это приводит к бесконечному
циклу.
6. Функция REJECT
Обычно lex разделяет входной поток, не осуществляя
поиск всех возможных соответствий каждому выражению. Это
означает, что каждый символ рассматривается один и только
один раз. Предположим, что мы хотим подсчитать все вхождения
цепочек she и he во входном тексте. Для этого мы могли бы
записать следующие правила:
she s++;
he h++;
. |
\n ;
Так как she включает в себя he, анализатор не распознает те
вхождения he, которые включены в she, так как, прочитав один
раз she, эти символы он не вернет во входной поток.
Иногда желательно переопределить этот выбор. Действие
функции REJECT означает "выбрать следующую альтернативу".
Это приводит к тому, что каким бы ни было правило, после
него необходимо выполнить второй выбор. Соответственно изме-
нится и положение указателя во входном потоке:
29
she { s++; REJECT; }
he { h++; REJECT; }
. |
\n ;
Здесь после выполнения одного правила символы возвращаются
назад во входной поток, и выполняется другое правило.
Функция REJECT полезна в том случае, когда она применя-
ется для определения всех вхождений какого-либо объекта,
причем вхождения могут перекрываться или включать друг
друга. Предположим, необходимо получить из одного потока
таблицу всех двухбуквенных сочетаний, которые обычно перек-
рываются, например, слово the содержит как th, так и he.
Допустим, имеется двумерный массив digram, тогда:
%%
[a-z][a-z] {
digram[yytext[0]][yytext[1]]++;
REJECT;
}
\n ;
Здесь REJECT используется для выделения буквенных пар, начи-
нающихся на каждой букве, а не на каждой следующей.
7. Функции yyless и yymore
В обычной ситуации содержимое yytext обновляется всякий
раз, когда на входе появляется следующая строка. Напомним,
что в yytext всегда находятся символы распознанной последо-
вательности. Иногда возникает необходимость добавить к теку-
щему содержимому yytext следующую распознанную цепочку сим-
волов. Для этой цели используется функция yymore. Формат
вызова этой функции:
yymore()
В некоторых случаях возникает необходимость использовать не
все символы распознанной последовательности в yytext, а
только необходимое их число. Для этой цели используется
функция yyless. Формат ее вызова:
yyless(n)
где n указывает, что в данный момент необходимы только n
символов строки в yytext. Остальные найденные символы будут
возвращены во входной поток.
Пример использования фунцкии yymore:
30
.
.
.
\"[^"]* {
if( yytext[yyleng - 1] == '\\'){
yymore();
}else{
/*
* здесь должна быть часть
* программы, обрабатывающая
* закрывающую кавычку.
*/
}
}
.
.
.
В этом примере распознаются строки симвoлов, взятые в двой-
ные кавычки, причем символ двойная кавычка внутри этой
строки может изображаться с предшествующей косой чертой.
Анализатор должен распознавать кавычку, ограничивающую
строку, и кавычку, являющуюся частью строки, когда она изоб-
ражена как \".
Допустим, на вход поступает строка "абв\"где". Сначала
будет распознана цепочка "абв\ и, так как последним символом
в этой цепочке будет символ "\", выполнится вызов yymore().
В результате к цепочке "абв\ будет добавлено "где, и в
yytext мы получим: "абв\"где, что и требовалось.
Пример использования фунции yyless:
.
.
.
=-[A-ZА-Яa-zа-я] {
printf("Oператор (=-) двусмысленный.\n");
yyless(yyleng - 2);
/*
* здесь необходимо указать
* действия для случая "=-"
*/
}
.
.
.
В этом примере разрешается двусмысленность выражения "=-
31
буква" в языке Си. Это выражение можно рассматривать как
"=- буква" (равносильно "-=" )
или
"= -буква"
Предположим, что желательно эту ситуацию рассматривать как
"= -буква" и выводить пердупреждение. Указанное в примере
правило распознает эту ситуацию и выводит предупреждение.
Затем, в результате вызова "yyless(yyleng - 2);" два сим-
вола "-буква" будут возвращены во входной поток, а знак "="
останется в yytext для обработки, как в нормальной ситуации.
Таким образом, при продолжении чтения входного потока уже
будет обрабатываться цепочка "-буква", что и требовалось.
8. Совместное использование lex и yacc
yacc требует указание лексическому анализатору имени
yylex(). Именно поэтому эта функция так называется в lex.
Известно, что yacc строит выходной файл y.tab.c .
Основной в файле y.tab.c является функция yyparse, реализую-
щая алгоритм грамматического разбора. Функция yyparse содер-
жит многократное обращение к функции лексического анализа
yylex.
Для обеспечения корректной работы грамматического ана-
лизатора функция yylex должна быть согласована с конкретной
спецификацией грамматики и удовлетворять определенным требо-
ваниям.
Пользователь при описании грамматики решает, какие
конструкции целесообразнее непосредственно выделять из вход-
ного текста на этапе лексического анализа.
Сложность лексического анализатора зависит от того,
какие структурные единицы взяты за основу при описании грам-
матических правил. Детализовав грамматику до отдельных сим-
волов, можно обойтись простейшим лексическим анализатором.
Однако, в этом случае число правил растет, а грамматический
разбор оказывается менее эффективным. Поэтому пользователь
обычно должен найти некоторый компромисс при выборе набора
лексем.
Заметим, что ключевые слова описываемого входного языка
часто бывает удобно считать лексемами. Имена лексем могут
совпадать с этими ключевыми словами, недопустимым является
лишь совпадение имен лексем с зарезервированными словами
языка Си.
Основная задача функции yylex состоит во вводе из вход-
ного потока ряда очередных символов до выявления конструк-
ции, соответствующей одной из лексем, и возвращении номера
32
типа этой лексемы и, когда это необходимо, значения этой
лексемы.
Все виды лексем, кроме литералов, обозначаются некото-
рыми именами и под этими именами фигурируют в Yacc-
программе, где объявление имен лексем осуществляется дирек-
тивой token:
%token <список имен лексем>
Благодаря объявлению имен лексем в директиве token, yacc
отличает имена лексем от имен нетерминальных символов.
Пример объявления имен лексем в Yacc-программе:
%token IDENT CONST ЗНАК IF THEN GOTO
При первом появлении лексемы или литерала в секции объявле-
ний Yacc-программы за каждым из них может следовать неотри-
цательное целое число, рассматриваемое как номер_типа лек-
семы.
По умолчанию номера типов всех лексем определяются yacc
следующим образом:
- для литерала номером типа лексемы считается числовое
значение данного литерального символа, рассматривае-
мого как однобайтовое целое число;
- лексемы, обозначенные именами, в соответствии с оче-
редностью их объявления получают последовательные
номера, начиная с 257.
Для каждого имени лексемы независимо от того, переопре-
делен ли ее номер пользователем, yacc генерирует в выходном
файле y.tab.c оператор препроцессора:
#define <имя_лексемы> <номер_типа>
Значение, возвращаемое функцией yylex, является номером типа
лексемы. Таким образом, список лексем и номера их типов ука-
зываются в Yacc-программе, а определения этих лексем в Lex-
программе. Возникает проблема соответствия номеров типов
лексем в файлах y.tab.c и lex.yy.c, котороя разрешается сле-
дующим образом:
- при вызове yacc с флагом -d последовательность опера-
торов #define помещается в файл y.tab.h.;
- этот файл посредством оператора #include включается в
Lex-программу.
33
В процедуре лексического анализа кроме выделения лексем
можно предусмотреть некоторую обработку лексем определенных
типов, в частности, запоминание конкретных значений лексем.
Примером значения лексемы могут служить числовое значе-
ние символа - цифры, вычисленное значение константы, адрес
идентификатора в таблице имен (построение таблицы имен осу-
ществляет lex). Кроме того, эти значения обычно требуется
передать грамматическому анализатору. С этой целью нужное
значение должно быть присвоено внешней переменной целого
типа с именем yylval. Если функция yylex находится в отдель-
ном файле, то эта переменная должна быть объявлена:
extern int yylval;
Уточним, что значением_лексемы будем называть значение,
присвоенное при ее распознавании переменной yylval. Заметим,
что в yylval всегда должно находится значение последней
выделенной лексемы.
Допустим, мы располагаем Yacc-программой в файле
source.y и Lex-программой в файле source.l, которые необхо-
димо собрать в работающую программу. Существует два способа
сборки:
- сборка Lex- и Yacc-программы с созданием файла
y.tab.h;
- сборка Lex- и Yacc-программы без создания файла
y.tab.h.
Рассмотрим первый способ сборки.
Ниже приведен пример makefile для программы make, кото-
рая осуществляет последовательную обработку и сборку эих
программ и размещает результат в файле program:
34
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.
35
%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; }
|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-программа лексичского
анализатора для этого калькулятора:
36
%{
#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 выглядит следующим образом:
37
%token DIGIT LETTER
%left '|'
%left '&'
%left '+' '-'
%left '*' '/' '%'
%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 выглядит следующим образом:
38
%{
extern int yylval;
%}
%%
^\n ;
[ \t]* ;
[A-Za-z] {
yylval = yytext[yyleng-1] - 'a';
return(LETTER);}
[0-9] {
yylval = yytext[yyleng-1] - '0';
return(DIGIT);}
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] - это последний полученный
из входного потока символ.
10. Флаги Lex
-t поместить результат в стандартный файл вывода, а не в
файл lex.yy.c;
-v вывести размеры внутренних таблиц;
-f ускорить работу, не упаковывая таблицы (только для
небольших программ);
39
-n не выводить размеры таблиц (устанавливается по умолча-
нию);
-d используется при отладке lex.
Имеется возможность собрать анализатор для диагностики.
Для этого необходимо компиляцию файла lex.yy.c осуществлять
с подключением разделов диагностики:
cc -d -DLEXDEBUG lex.yy.c
При работе полученного таким образом анализатора будет выво-
диться диагностика действий. Флаг -d, кроме того, позволяет
проверить текст программы lex.yy.c с помощью текстового
отладчика cdeb.
40
СОДЕРЖАНИЕ
. Аннотация ......................................... 2
1. Введение .......................................... 3
2. Регулярные выражения в Lex-правилах ............... 8
2.1. Обозначения символов в выражениях ............... 8
2.2. Операторы регулярных выражений .................. 9
2.3. Оператор выделения классов символов ............. 9
2.4. Повторители ..................................... 9
2.5. Операторы выбора ................................ 10
2.6. Оператор {} ..................................... 11
2.7. Оператор <>. Служебные слова START и BEGIN ...... 12
3. Структура Lex-программы ........................... 15
3.1. Раздел определений Lex-программы ................ 15
3.2. Раздел правил ................................... 18
3.2.1. Действия в правилах Lex-программы ............. 19
3.2.2. Порядок действия активных правил .............. 21
3.3. Раздел программ пользователя .................... 22
3.4. Комментарии Lex-программы ....................... 22
3.5. Примеры Lex-программ ............................ 22
4. Структура файла lex.yy.c .......................... 26
5. Функция yywrap() .................................. 27
6. Функция REJECT .................................... 29
7. Функции yyless и yymore ........................... 30
8. Совместное использование lex и yacc ............... 32
9. Использование Ратфора ............................. 39
10. Флаги Lex ......................................... 39
41
Популярность: 1, Last-modified: Mon, 29 Jun 1998 14:01:55 GmT