Страница:
Производственно-внедренческий кооператив
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/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
"И Н Т Е Р Ф Е Й С"
Диалоговая Единая Мобильная
Операционная Система
Демос/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