lex_doc (1119420), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Имя - как обычно, любая последовательность букв и цифр,

начинающаяся с буквы. Трансляция - это регулярное выражение

(или его часть), которое будет подставлено всюду там, где

указано имя (смотрите третью строку этого примера).

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

- если несколько правил распознают последовательности

символов одной длины, то выполняется действие того

Характеристики

Список файлов учебной работы