46023 (665330), страница 8

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

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

лексические анализаторы на языках Си и Ратфор (рациаональный диа-

лект Фортрана). В качестве 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-программа может содержать несколько помеченных на-

чальных условий.

Каждое правило, перед которым указан оператор типа "<МЕТ-

КА>", мы будем называть помеченным правилом. Метка формируется

также как и метка в Си.

Количество помеченных правил не ограничивается. Кроме того,

разрешается одно правило помечать несколькими метками, например:

x ДЕЙСТВИЕ

Запятая - обязательный разделитель списка меток !

Структура Lex-программы

Lex-программа включает разделы опредeлений, правил и пользо-

вательских программ. Рассмотрим подробнее способы оформления этих

разделов.

Все строки, в которых занята первая позиция, относятся к

Lex-программе. Любая строка, не являющаяся частью правила или

действия, которая начинается с пробела или табуляции, копируется

в сгенерированную программу lex.yy.c - результат работы Lex.

Раздел определений Lex-программы

Определения, предназначенные для Lex, помещаются перед пер-

вым %%. Любая строка этого раздела, не содержащаяся между %{ и %}

и начинающаяся в первой колонке, является определением строки

подстановки Lex. Раздел определений Lexпрограммы может включать:

- начальные условия;

- определения;

- фрагменты программы пользователя;

- таблицы наборов символов;

- указатели host-языка;

- изменения размеров внутренних массивов;

- комментарии в формате host-языка.

НАЧАЛЬНЫЕ УСЛОВИЯ задаются в форме:

%START имя1 имя2 ...

Если начальные условия определены, то эта строка должна быть

первой в Lex-программе.

ОПРЕДЕЛЕНИЯ задаются в форме:

имя трансляция

В качестве разделителя используется один или более пробелов

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

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

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

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

ФРАГМЕНТЫ ПРОГРАММЫ ПОЛЬЗОВАТЕЛЯ указываются двумя способами:

- в виде "пробел фрагмент";

- в виде %{ строки фрагмента программы пользователя %}

Такая форма включения пользовательского фрагмента необходи-

ма для ввода, например, макроопределений Си, которые должны начи-

наться в первой колонке строки. Все строки фрагмента пользова-

тельской программы, размещенные в разделе определений, будут яв-

ляться внешними для любой функции программы lex.yy.c

ТАБЛИЦА НАБОРОВ СИМВОЛОВ задается в виде:

%T

целое_число строка_символов

.........

целое_число строка_символов

%T

Сгенерированная программа lex.yy.c осуществляет ввод-вывод

символов посредством библиотечных функций Lex с именами input,

output, unput. Таким образом, Lex помещает в yytext символы в

представлении, используемом в этих библиотечных функциях. Для

внутреннего использования символ представляется целым числом,

значение которого образовано набором битов, представляющих сим-

вол в конкретной ЭВМ. Пользователю предоставляется возможность

менять представление символов (целых констант) с помощью таблицы

наборов символов. Если таблица символов присутствует в разделе

определений, то любой символ, появляющийся либо во входном пото-

ке, либо в правилах, должен быть определен в таблице символов.

Символам нельзя назначать число 0 и число, большее числа, выде-

ленного для внутреннего представления символов конкретной ЭВМ.

УКАЗАТЕЛЬ host-языка имеет вид:

%C для Си;

%R для Ратфора.

Если указатель host-языка отсутствует, то по умолчанию при-

нимается Си.

ИЗМЕНЕНИЯ РАЗМЕРА ВНУТРЕННИХ МАССИВОВ задаются в форме:

%x число

"число" - новый размер массива;

"x" - одна из букв p - позиции;

n - состояния;

e - узлы дерева;

a - упакованные переходы;

k - упакованные классы символов;

o - массив выходных элементов.

Lex имеет внутренние таблицы, размеры которых ограничены.

При построении программы лексического анализа может произойти пе-

реполнение любой из этих таблиц, о чем Lex сообщает при построе-

нии лексического анализатора. Пользователю предоставляется воз-

можность изменить размеры таблиц (сокращая размеры одних и увели-

чивая размеры других) таким образом, чтобы они не переполнялись.

Естественно, эти изменения возможны лишь в пределах той памяти,

которая выделяется под процесс.

Ниже перечислены размеры таблиц, которые устанавливаются по

умолчанию:

p - позиций 1500;

n - состояний 300;

e - узлов 600;

a - упакованных переходов 1500;

k - упакованных классов символов 1000;

o - выходных элементов 1500.

КОММЕНТАРИИ в разделе определений задаются в форме host-язы-

ка и должны начинаться не с первой колонки строки.

Раздел правил

Все, что указано после первой пары %% и до конца Lexпрограм-

мы или до второй пары %%, если она указана, относится к разделу

правил. Раздел правил может содержать правила и фрагменты прог-

рамм. Фрагменты программ, содержащиеся в разделе правил, стано-

вятся частью функции yylex файла lex.yy.c, в которой осущес-

твляется выполнение действий активных правил. Фрагмент прогрммы

указывается следующим образом:

%{ строки фрагмента программы %}

Раздел правил может включать список активных и неактивных

(помеченных) правил. Активные и неактивные правила могут быть

указаны в любом порядке, в том числе быть "перемешанными" в спис-

ке. Активные правила выполняются всегда, неактивные только по

ссылке на них оператором BEGIN.

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

ВЫРАЖЕНИЕ ДЕЙСТВИЕ

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

ВЫРАЖЕНИЕ ДЕЙСТВИЕ

или

ВЫРАЖЕНИЕ ДЕЙСТВИЕ

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

Список файлов реферата