The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование в Linux" / Оглавление документа
next up previous contents
Next: Секция пользовательских подпрограмм LEX-программы Up: Структура LEX-программы Previous: Секция определений LEX-программы   Contents

Секция правил LEX-программы

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

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

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

регулярное_выражение действие
Активные правила выполняются всегда. По регулярным выражениям (regular expressions), содержащимся в левой части правил, LEX строит детерминированный конечный автомат. Этот автомат осуществляет интерпретацию, а не компиляцию, и переходит из одного состояния в другое. Количество правил и их сложность не влияют на скорость лексического анализа, если только правила не требуют слишком большого объема повторных просмотров входной последовательности символов. Однако с ростом числа правил и их сложности растет размер конечного автомата, интерпретирующего их, и, следовательно, растет размер Си-программы, реализующей этот конечный автомат.

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

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

Каждое правило здесь определяет действие (оно взято в фигурные скобки). Открывающая фигурная скобка стоит в той же строке, что и правило, - это требование LEX. Действие в каждом правиле данной LEX-программы - это вывод русского значения найденного английского слова. В качестве оператора, выполняющего действие, используется библиотечная функция языка Си. Пара фигурных скобок определяет блок (в смысле языка Си), который может содержать любое количество строк. Если действие содержит всего одну строку Си, то можно ее записать без фигурных скобок, как обычно. Единственное условие - она должна начинаться в той же строке, где и регулярное выражение. В программе содержится только раздел правил, их всего 19. Регулярное выражение каждого правила определяет английское слово, написанное строчными или прописными латинскими символами. Например, ``may'' (май) определен как mMaAyY. По этому регулярному выражению будет выделена во входном потоке лексема ``may'', а по действию этого правила будет выведено ``Май''. Наличие строчной и прописной буквы в квадратных скобках обеспечивает распознавание слова ``may'', написанного любым способом. После запуска на выполнение ЛА получим:

May
Май
MONDAY
Понедельник
. . .
Ctrl-c
Действие (action) можно представлять либо как специальное действие LEX, либо как оператор Си. Если имеется необходимость выполнить достаточно большой набор преобразований, то действие
оформляют как блок Си-программы (он начинается открывающей фигурной скобкой и завершается закрывающей), содержащий необходимые фрагменты. Действие в правиле записывается не менее чем через один пробел или табуляцию после регулярного выражения (начинается обязательно в той же строке), а его продолжение может быть в следующих строках только в том случае, если действие оформлено как блок Си-программы. Область действия переменных, объявленных внутри блока, распространяется только на этот блок. Внешними переменными для всех действий будут только те переменные, которые объявлены в секции определений. Действия в правилах LEX-программы выполняются, если правило активно, т.е., если ЛА распознает цепочку символов из входного потока как соответствующую регулярному выражению данного правила. Однако если входная цепочка символов не распознана, то она просто копируется из входного потока в выходной. Комбинация символов, не учтенная в правилах и появившаяся на входе, будет напечатана на выходе. Можно сказать, что копирование осуществляется ``по умолчанию'', а действие - это то, что делается вместо копирования в случае успешного распознавания лексемы. Таким образом, ЛА, построенный на основе только простейшей LEX-программы и соответственно файла-заготовки ncform, будет просто копировать входной поток в выходной. Часто бывает необходимо избавиться от подобного копирования. Для этой цели используется пустой оператор Си. Например, правило

[ \t\n] ;
запрещает вывод пробелов, табуляций и символов ``новая строка''. Запрет выражается в том, что для указанных символов во входном потоке осуществляется действие ; - пустой оператор Си, и эти символы не копируются в выводной поток символов.

Как отмечалось выше, в качестве действий могут выступать специальные действия языка LEX:

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

" " |
\t |
\n ;
Специальное действие BEGIN имеет следующий формат:

BEGIN метка;
Если LEX-программа содержит активные и неактивные правила, то активные правила работают всегда. Специальное действие BEGIN просто расширяет список активных правил, активизируя помеченные меткой неактивные правила. BEGIN 0; удаляет из ``списка активных'' все помеченные правила, которые до этого были активизированы, и тем самым возвращает ЛА в самое начальное состояние. Кроме того, если из помеченного и активного в данный момент времени правила осуществляется специальное действие BEGIN, то из помеченных правил активными останутся либо станут только те, которые помечены меткой, указанной в этом специальном действии. Например, в качестве первого правила секции правил может быть:

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

Когда необходимо вывести или преобразовать текст, соответствующий некоторому регулярному выражению, используется внешний массив символов yytext, который формирует LEX и доступен в действиях правил. Например, по правилу

[A-Z]+ printf("%s",yytext);
распознается и выводится на экран слово, содержащее прописные латинские буквы. Операция вывода распознанного выражения используется очень часто, поэтому имеется сокращенная форма записи этого действия, выражающаяся специальным действием ECHO:

[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;}
Здесь ведется подсчет числа распознанных слов и количества символов во всех словах.

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

she s++;
he h++;
. |
\n ;
Поскольку she включает в себя he, ЛА не распознает те вхождения he, которые включены в she, так как прочитав один раз she, эти символы он не вернет во входной поток. Иногда нужно изменить подобную ситуацию. Специальное действие REJECT означает - ``выбрать следующую альтернативу''. Это приводит к тому, что, каким бы ни было правило, после него необходимо выполнить второй выбор. Соответственно изменится и положение указателя во входном потоке:

she {s++; REJECT;}
he {h++; REJECT;}
. |
\n ;
Здесь после выполнения одного правила символы возвращаются во входной поток и выполняется другое правило. Слово the содержит как th, так и he. Если имеется двухмерный массив digram, тогда:

%%
[a-z][a-z] {
digram[yytext[0]][yytext[1]]++;
REJECT;
}
\n ;
Здесь REJECT используется для выделения буквенных пар, начинающихся на каждой букве, а не на каждой следующей. Как видно, REJECT полезно применять для определения всех вхождений, причем вхождения могут перекрываться или включать друг друга.

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

<метка> регулярное_выражение действие
или

<метка1,метка2,...> регулярное_выражение действие
Неактивные правила выполняются только в тех случаях, когда выполняется некоторое начальное условие. Количество помеченных
правил не ограничивается. Кроме того, разрешается одно правило помечать несколькими метками. Начальные условия LEX-программы помещаются в секцию определений. С помощью START вводится список начальных условий как список меток соответствующих состояний автомата (states). Метка формируется так же, как и метка в Си. Неактивные правила помечаются начальными условиями, а специальное действие BEGIN позволяет активизировать правила, помеченные начальными условиями, т.е. автомат переходит в соответствующее состояние. Пример:

%Start КОММ
КОММ_НАЧАЛО "/*"
КОММ_КОНЕЦ "*/"
%%
{КОММ_НАЧАЛО} {
ECHO;
BEGIN КОММ;
};
[\t\n]* ;
<КОММ>[\^*]* ECHO;
<КОММ>\*/[^/] ECHO;
<КОММ>{КОММ_КОНЕЦ} {
ECHO;
printf("\n");
BEGIN 0;
};
LEX строит ЛА, который выделяет комментарии в Си-программе и записывает их в стандартный файл вывода. Программа начинается с ключевого слова START (можно записывать и как Start), за которым поставлена метка начального условия КОММ. В данном случае оператор <КОММ>x означает учет x, если ЛА находится в начальном условии КОММ. Специальное действие BEGIN КОММ; переводит ЛА в состояние, соответствующее начальному условию КОММ. После этого ЛА уже находится в новом состоянии КОММ, и теперь разбор входного потока будет осуществляется и теми правилами, которые начинаются с <КОММ>. Например, правилом

<КОММ>[\^*]* ECHO;
теперь будет записываться в стандартный файл вывода любое число (включая и ноль) символов, отличных от символа *. Оператор BEGIN 0; переводит ЛА в исходное состояние.

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

%Start AA BB CC DD
, то это означает, что она управляет четырьмя начальными состояниями ЛА. В каждое из этих начальных состояний ЛА можно перевести, используя BEGIN. Пример с несколькими начальными условиями:

%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-программа управляет тремя начальными условиями, в соответствии с которыми активизируются помеченные правила. Здесь представлен ЛА, который будет распознавать в Си-программе строки макропроцессора Си-компилятора, выделять функцию main, распознавая с аргументами она или без них, распознавать метки. ЛА не выводит ничего, кроме сообщений о выделенных лексемах.

Таким образом, в процессе работы ЛА список активных правил может ``видоизменяться'' за счет действий оператора BEGIN. В процессе распознавания лексем во входном потоке может оказаться так, что одна цепочка символов удовлетворяет нескольким правилам и, следовательно, возникает проблема: действие какого правила должно выполняться? Для разрешения этого противоречия можно использовать ``разбиение'' регулярных выражений этих правил LEX-программы на такие новые регулярные выражения, которые дадут однозначное распознавание лексем. Однако, если это не сделано, LEX использует определенный детерминированный механизм разрешения такого противоречия:

Пример:

[Мм][Аа][Йй] ECHO;
[А-Яа-я]+ ECHO;
Слово ``Май'' распознают оба правила, однако выполнится первое из них, так как и первое и второе правила распознали лексему одинакового размера (3 символа). Если во входном потоке будет слово ``майский'', то первые 3 символа удовлетворяют первому правилу, а все 7 символов удовлетворяют второму правилу и, следовательно, выполнится второе правило, так как ему соответствует более длинная последовательность.

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

%{
фрагмент
%}
Пример:

%%
%{
#include file.h
%}
Здесь строка include file.h станет строкой функции yylex.



2004-06-22



Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру