ЛЕКЦИЯ 9
КРАТКИЕ СВЕДЕНИЯ О ГЕНЕРАТОРЕ ЛЕКСИЧЕСКИХ
АНАЛИЗАТОРОВ LEX
Лексический анализ - это распознавание лексем во входном
потоке символов. Предположим, что задано некоторое конечное мно-
жество слов (лексем) в некотором языке и некоторое входное
слово.Необходимо установить, какой элемент множества (если он су-
ществует) совпадает с данным входным словом.
Обычно лексический анализ выполняется так называемым лекси-
ческим анализатором. Применяется во многих случаях, например, для
построения пакетного редактора или в качестве распознавателя ди-
ректив в диалоговой программе и т.д. Наиболее важное применение
лексического анализатора - это использование его в компиляторе.
Здесь лексический анализатор выполняет функцию программы ввода
данных.
Лексический анализатор выполняет первую стадию компиляции -
читает строки компилируемой программы, выделяет лексемы и пере-
дает их на дальнейшие стадии компиляции (грамматический разбор,
кодогенерацию и т.д.).
Лексический анализатор распознает тип каждой лексемы и соот-
ветствующим образом помечает ее. Например, при компиляции
Си-программы могут быть выделены следующие типы лексем: число,
идентификатор, оператор, ограничитель и т.д.
Лексический анализатор должен не только выделить лексему, но
и выполнить некоторые преобразования. Например, если лексема
- число, то его необходимо перевести во внутреннюю (двоичную)
форму записи как число с плавающей или фиксированной точкой. А
если лексема - идентификатор, то его необходимо разместить в таб-
лице, чтобы в дальнейшем обращаться к нему не по имени, а по ад-
ресу в таблице.
Хотя лексический анализ по своей идее прост, тем не менее
эта фаза работы компилятора часто занимает больше времени, чем
любая другая. Частично это происходит из-за необходимости прос-
матривать и анализировать исходный текст символ за символом.
Иногда даже бывает необходимо вернуть прочитанный символ во вход-
ной поток с тем, чтобы повторить просмотр и анализ. Происходит
это потому, что часто бывает трудно определить, где проходят гра-
ницы лексемы. В тех случаях, когда выделение лексемы затруднено
либо по причине того, что одно регулярное выражение не позволяет
ее однозначно определить, либо из-за того, что лексема является
частью другой, приходится прибегать к контекстно-зависимым алго-
ритмам анализа с использованием левого и правого направлений
просмотра входной цепочки символов.
Lex - частично или полностью автоматизирует процесс написа-
ния программы лексического анализа. Lex - это программирующая
программа или генератор программ. Lex строит программу - лекси-
ческий анализатор на так называемом host-языке (или "главном"
языке). Это значит, что Lex-программа пишется на "языке" Lex, а
Lex-генератор, в свою очередь, генерирует программу лексического
анализа на каком-либо другом языке. Данная версия Lex генерирует
лексические анализаторы на языках Си и Ратфор (рациаональный диа-
лект Фортрана). В качестве host-языка мы будем использовать язык
Си.
Lex-программа имеет следующий формат:
определения %%
правила %%
подпрограммы, составленные пользователем
Любой из этих разделов может быть пустым. Простейшая
Lexпрограмма имеет вид:
%%
Здесь нет никаких определений и никаких правил. Правило сос-
тоит из двух частей:
РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
По регулярным выражениям, содержащимся в левой части правил,
Lex строит детерминированный конечный автомат. Этот автомат осу-
ществляет интерпретацию, а не компиляцию. Количество правил и их
сложность не влияют на скорость лексического анализа, если только
правила не требуют слишком большого об'ема повторных просмотров
входной последовательности символов. Однако, с ростом числа пра-
вил и их сложности растет размер конечного автомата, интерпрети-
рующего их и, следовательно, растет размер Си-программы, реали-
зующей этот конечный автомат. Lex всегда, если не указано другое,
строит выходной файл с именем lexyy.c - Си-программу - лексичес-
кий анализатор.
Если имеется необходимость получить файл с именем, отличным
от lexyy.c, то можно воспользоваться флагом "-t":
% lex -t source.l > file
По этому флагу результат поступает на стандартный вывод. Ре-
гулярные выражения в Lex-правилах определяют лексему. Они могут
содержать символы латинского и русского алфавитов в верхнем и
нижнем регистрах, другие символы (цифры, знаки препинания и
т.д.) и символы-операторы.
Операторы позволяют осуществлять различные действия над вы-
деленной цепочкой символов. Операторы также обозначаются символа-
ми.
Обозначения символов в выражениях. Можно использовать любой
символ. Символ можно указывать в двойных кавычках. В этом случае
это всегда просто символ - его специальное значение отменяется.
. - точка означает любой символ, кроме символа новой строки
"\n";
\восьмеричный_код_символа - указание символа его восьмерич-
ным кодом (как в языке Си);
\n - символ новой строки;
\t - символ табуляции;
\b - возврат курсора на один шаг назад;
Пробел - любой символ пробела в выражении, если он не нахо-
дится внутри квадратных скобок, необходимо заключать в двойные
кавычки. Это необходимо, так как пробел и табуляция используются
Lex в качестве разделителя между определением и действием в пра-
виле.
Операторы регулярных выражений
Операторы обозначаются символами-операторами, к ним относят-
ся:
\ ^ ? * + | $ / %
[] {} () <>
Каждый из этих символов или пар скобок в регулярном выраже-
нии играет роль оператора. Если необходимо отменить специальное
значение символа, обозначающего оператор, перед ним нужно поста-
вить символ "\" или указать его в двойных кавычках.
Оператор выделения классов символов.Квадратные скобки за-
дают классы символов, которые в них заключены.
[abc] означает либо символ "a", либо "b", либо символ "c";
Знак "-" используется для указания любого символа из лекси-
кографически упорядоченной последовательности: [A-z] означает лю-
бой латинский символ;
Повторители
Когда необходимо указать повторяемость вхождения символа в
регулярном выражении, используют операторы-повторители "*" и "+".
Оператор "*" означает любое (в том числе и 0) число вхожде-
ний символа или класса символов. Например: x* любое число вхожде-
ний символа "x"; Оператор "+" означает одно и более вхождений.
Например: x+ одно или более вхождений "x";
Операторы выбора
Операторы: / | ? $ ^ управляют процессом выбора символов.
Оператор "/": ab/cd "ab" учитывается только тогда, когда за
ним следует "cd".
Опeратор "|": ab|cd или "ab", или "cd".
Опeратор "?": x? означает необязательный символ "x".
_?[A-Za-z]* означает, что перед цепочкой любого количества
латинских букв может быть необязательный знак подчеркивания.
-?[0-9]+ выделит любое целое число с необязательным минусом
впереди.
Оператор "$": x$ означает выбрать символ "x", если он яв-
ляется последним в строке. Стоит перед символом "\n"! abc$ озна-
чает выбрать цепочку "abc", если она завершает строку.
Оператор "^": ^x означает выбрать символ "x", если он яв-
ляется первым символом строки; ^abc означает выбрать цепочку сим-
волов "abc", если она начинает строку. [^A-Z]* означает все сим-
волы, кроме прописных латинских букв. Когда символ "^" стоит пе-
ред выражением или внутри "[]", он выполняет операцию дополнение.
Внутри квадратных скобок символ "^" должен обязательно стоять
первым у открывающей скобки!
Оператор {} имеет два различных применения:
x{n,m} здесь n и m натуральные, m > n. Означает от n до m
вхождений x, например, x{2,7} - от 2 до 7 вхождений x;
{имя} вместо "{имя}" в данное место выражения будет подстав-
лено определение имени из области определений Lex-программы.
yytext - это внешний массив символов программы lex.yy.c,
которую строит Lex. yytext формируется в процессе чтения входно-
го файла и содержит текст, для которого установлено соответствие
какому-либо выражению. Этот массив доступен пользовательским раз-
делам Lex-программы.
Оператор <>. Служебные слова START и BEGIN
Раздел правил Lex-программы может содержать активные и неак-
тивные правила. Активные правила выполняются всегда. Неактивные
выполняются только в тех случаях, когда выполняется некоторое на-
чальное условие.
Начальные условия Lex-программы помещаются в раздел опреде-
лений, а неактивные правила помечаются соответствующими условия-
ми. Оператор Start позволяет указать список начальных условий
Lex-программы, а оператор BEGIN позволяет активировать правила,
помеченные начальными условиями.
Активные правила имеют следующий синтаксис:
РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
Неактивные правила имют следующий синтаксис:
<МЕТКА_УСЛОВИЯ>РЕГУЛЯРНОЕ_ВЫРАЖЕНИЕ ДЕЙСТВИЕ
ВАЖНО: любое правило должно начинаться с первой позиции
строки, пробелы и табуляции недопустимы - они используются как
разделители между регулярным выражением и действием в правиле.
Lex-программа может содержать несколько помеченных на-
чальных условий.
Каждое правило, перед которым указан оператор типа "<МЕТ-
КА>", мы будем называть помеченным правилом. Метка формируется
также как и метка в Си.
Количество помеченных правил не ограничивается. Кроме того,
разрешается одно правило помечать несколькими метками, например:
<МЕТКА1,МЕТКА2,МЕТКА3>x ДЕЙСТВИЕ
Запятая - обязательный разделитель списка меток !
Структура Lex-программы
Lex-программа включает разделы опредeлений, правил и пользо-