Реферат: Проектирование трансляторов

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

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

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

умолчанию:

     p - позиций 1500;

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

     e - узлов 600;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     <МЕТКА>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

        или

     <СПИСОК МЕТОК>ВЫРАЖЕНИЕ ДЕЙСТВИЕ

     где СПИСОК_МЕТОК имеет вид:

     метка1,метка2,...

     В качестве первого правила раздела правил может быть  прави-

ло вида:

     BEGIN МЕТКА;

     В этом правиле отсутствует ВЫРАЖЕНИЕ, и первым  действием  в

разделе правил будет активизация помеченных правил. Для возвраще-

ния автомата в исходное состояние можно использовать действие:

     BEGIN 0;

     Важно отметить следующее. Если Lex-программа содержит актив-

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

Оператор "BEGIN МЕТКА;" просто расширяет список активных  правил,

активируя помеченные меткой МЕТКА. А оператор "BEGIN 0;"  удаляет

из списка активных правил все помеченные правила, которые до это-

го были активированы. Кроме того, если из помеченного и  активно-

го в данный момент времени правила осуществляется действие  BEGIN

МЕТКА, то из помеченных правил активными останутся только те, ко-

торые помечены меткой МЕТКА.

                Действия в правилах Lex-программы

     Действие можно представлять либо как оператор Lex, например,

"BEGIN МЕТКА;", либо как оператор Си. Если имеется  необходимость

выполнить достаточно большой набор  преобразований,  то  действие

оформляют как блок Си-программы (он начинается открывающей фигур-

ной скобкой и завершается закрывающей фигурной скобкой), содержа-

щий необходимые фрагменты.

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

бел или табуляцию после выражения (обязательно в той  же  строке,

где и выражение), а его продолжение может быть указано в  следую-

щих строках только в том случае, если действие оформлено как блок

Си-программы.

     Область действия переменных, об'явленных внутри блока,  рас-

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

действий будут являться только те переменные, которые об'явлены в

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

     Действия в правилах Lex-программы выполняются, если  правило

активно, и если автомат распознает цепочку символов  из  входного

потока как соответствующую регулярному выражению данного правила.

Однако, одно действие выполняется всегда - оно заключается в  ко-

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

осуществляется для всех входных строк, которые  не  соответствуют

правилам, преобразующим эти строки. Комбинация символов,  не  уч-

тенная в правилах и появившаяся на входе, будет напечатана на вы-

ходе. Можно сказать, что действие - это то, что  делается  вместо

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

     Когда необходимо вывести или преобразовать  текст,  соответ-

ствующий некоторому регулярному выражению,  используется  внешний

массив символов, который формирует Lex. Называется  он  yytext  и

доступен в действиях правил. Например:

     [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;}

     Здесь ведется подсчет числа распознанных слов  и  количества

символов во всех словах.

                Порядок действий активных правил

     Список правил Lex-программы может содержать  активные  иеак-

тивные правила, размещенные в любом порядке в разделе  правил.  В

процессе работы лексического анализатора список  активных  правил

может видоизменяться за счет действий оператора BEGIN. В  процес-

се распознавания символов входного потока  может  оказаться  так,

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

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

ла должно выполняться?

     Для разрешения этого противоречия можно использовать кванто-

вание (разбиение) регулярных выражений этих правил  Lex-программы

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

ти, однозначное распознавание лексемы. Однако, когда это не  сде-

лано, Lex использует определенный детерминированный механизм раз-

решения такого противоречия:

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

более длинную последовательность символов из входного потока;

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

лов одной длины, то выполняется действие  того  правила,  которое

записано первым в списке раздела правил Lex-программы.

                  Раздел программ пользователя

     Все, что размещено за вторым набором %%, относится к  разде-

лу программ пользователя. Содержимое этого раздела  копируется  в

выходной файл lex.yy.c без каких-либо  изменений.  В  файле  lex.

yy.c строки этого раздела рассматриваются как  функции  в  смысле

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

но, передавать и возвращать значения аргументов.

                    Комментарии Lex-программы

     Комментарии можно указывать во всех разделах Lex- программы.

Формат комментариев должен соответствовать  формату  комментариев

host-языка. Однако, в каждом разделе Lex-  программы  комментарии

указываются по разному. В разделе определений комментарии  должны

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

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

ствиям. В разделе программ пользователя  комментарии  указываются

как и в host-языке.

                     Структура файла lexyy.c

     Lex строит программу - лексический анализатор на  языке  Си,

которая размещается в файле со стандартным именем  lex.yy.c.  Эта

программа содержит две основных  функции  и  несколько  вспомога-

тельных. Основные - это:

     функция yylex()

     Она содержит разделы действий всех правил, которые определе-

ны пользователем;

     функция yylook()

     Она реализует детерминированный  конечный  автомат,  который

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

гулярными выражениями правил Lex программы.

     Вспомогательные  функции,  которые  являются  подпрограммами

ввода-вывода. К ним относятся:

     input() - читает и возвращает символ из входного потока сим-

волов;

     unput(c) -  возвращает символ обратно во входной  поток  для

повторного чтения;

     output(c) - выводит в выходной поток символ "c".

     Эти функции можно изменить, указав им те же имена и  размес-

тив в разделе программ пользователя.

     Кроме того имеются  функции  yywrap(),  reject(),yyless()  и

yymore().

     yywrap()

     Используется для определения конца файла, из которого лекси-

ческий анализатор читает поток символов. Если  yywrap  возвращает

1,  лексический  анализатор  прекращает  работу.  Однако,  иногда

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40