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

Программа Lex имеет следующий вид:

Объявления %%

Правила трансляции %%

Вспомогательные функции

Раздел объявлений включает объявления переменных, именованные константы (manifest constant - идентификаторы констант, например имена токенов) и регу­лярные определения в стиле раздела 3.3.4.

Правила трансляции имеют вид

Шаблон { Действие }

Каждый шаблон является регулярным выражением, которое может использовать регулярные определения из раздела объявлений. Действия представляют собой фрагменты кода, обычно написанные на языке программирования С, хотя созданы многие разновидности Lex для других языков программирования. Внутри действий в правилах можно использовать некоторые специальные конструкции и функции Lex'а:

yytext – указатель на отождествленную цепочку символов, оканчивающуюся нулем;

yyleng – длина этой цепочки;

yyless(n) – вернуть последние n символов цепочки обратно во входной поток;

yymore() – считать следующие символы в буфер yytext после текущей цепочки;

yyunput(c) – поместить байт c во входной поток;

ECHO – копировать текущую цепочку в yyout;

yylval – еще одно возвращаемое значение.

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

Лексический анализатор, созданный Lex, работает во взаимодействии с син­таксическим анализатором. При вызове синтаксическим анализатором лексиче­ский анализатор считывает по одному символу оставшийся непрочитанным вход­ной поток, пока не будет найден самый длинный префикс входного потока, соот­ветствующий одному из шаблонов Р_i. Затем лексический анализатор выполняет связанные с ним действия A_i. Обычно A_i содержит возврат в синтаксический ана­лизатор, но если это не так (например, если P_i описывает пробельные символы или комментарии), то лексический анализатор продолжает поиск дополнитель­ных лексем, пока одно из соответствующих действий не приведет к возврату из функции лексического анализатора в синтаксический анализатор. Лексический анализатор возвращает синтаксическому анализатору единственное значение, имя токена, но использует при этом совместно используемую целочисленную пере­менную yylval для передачи при необходимости дополнительной информации о найденной лексеме.

Пример 3.11. На рис. 3.23 приведена программа Lex, которая распознает токены, представленные на рис. 3.12, и возвращает найденный токен синтаксическому анализатору. Рассмотрение приведенного кода поможет нам изучить многие важ­ные возможности Lex.

В разделе объявлений мы встречаем пару специальных скобок — %{ и %}. Все, что заключено в эти скобки, копируется непосредственно в lex. уу.с и не рассматривается как регулярное определение. Обычно здесь помещаются опре­деления именованных констант с использованием конструкции #def ine языка программирования С для назначения каждой именованной константе уникального целочисленного кода. В нашем примере мы перечислили в комментарии имено­ванные константы LT, IF и другие, но не привели определения, назначающие им конкретные числовые значения.[2]

%{

/* Определения именованных констант LT, LE, EQ, NE, GT, GE,

IF, THEN, ELSE, ID, NUMBER, RELOP */

%}

/* Регулярные определения */

delim [ \t\n]

ws {delim}+

letter [A-Za-z]

digit [0-9]

id {letter)({letter}|{digit})*

number {digit}+(\.{digit}+)?(E[+-]?{digit}+)?

%%

{ws} {/* Нет действий и выхода из функции */}

if {return(IF);}

then {return(THEN);}

else {return(ELSE);}

{id} {yylval = (int) installID(); return(ID);}

{number} {yylval = (int) installNum(); return(NUMBER);}

"<" {yylval = LT; return(RELOP);}

"<=" {yylval = LE; return(RELOP);}

"=" {yylval = EQ; return(RELOP);}

"<>" {yylval = NE; return(RELOP);}

">" {yylval = GT; return(RELOP);}

">=" {yylval = GE; return(RELOP);}

%%

int installID() {/* Функция для внесения лексемы (на первый символ которой указывает указатель yytext и длина которой равна yyleng) в таблицу символов. Возвращает указатель на соответствующую запись таблицы символов */

}

int installNum() {/* Аналогична функции installlD, но помещает числовые константы в отдельную таблицу */

}

Рис. 3.23. Программа Lex для распознавания токенов на рис. 3.12

Кроме того, в разделе объявлений имеется последовательность регулярных определений. Они используют расширенную запись регулярных выражений, опи­санную в разделе 3.3.5. Регулярные определения, используемые в следующих за ними определениях или шаблонах правил трансляции, помещаются в фигурные скобки. Так, например, delimопределено как сокращение для класса символов, состоящего из пробела, символа табуляции и символа новой строки (последние два символа представлены при помощи обратной косой черты, за которой следует соответственно буква t или n). Затем ws опреде­лено как один или несколько разделителей при помощи регулярного выражения {delim}+.

Обратите внимание, что в определениях id и number скобки используются в качестве метасимволов группирования и не обозначают сами себя. Напротив, буква Е в определении number означает саму себя. Если мы хотим использовать один из метасимволов Lex, такой как любая скобка,., +, * или?, так, чтобы он обозначал сам себя, то его следует предварить обратной косой чертой. Например, в определении number имеется последовательность \., представляющая обычную точку, поскольку просто точка в регулярных выражениях является метасимволом, представляющим "любой символ", как это принято в регулярных выражениях UNIX.

В разделе вспомогательных функций имеются функции installID() и installNum(). Так же, как и часть раздела объявлений, находящаяся меж­ду %{...%}, все, что находится во вспомогательном разделе, просто копируется в файл lex. уу. с, но может использоваться в действиях.

Наконец, рассмотрим некоторые из шаблонов и правил в среднем разделе на рис. 3.23. Первым указан идентификатор ws, объявленный в первом разделе и связанный с пустым действием. Если встречается пробельный символ, то выпол­няется не возврат в синтаксический анализатор, а поиск новой лексемы. Второй токен имеет простой шаблон регулярного выражения if. Если во входном пото­ке встречаются две буквы if, за которыми не следует другая буква или цифра (в этом случае мы имеем дело с более длинным префиксом входной строки, соот­ветствующим шаблону для id), лексический анализатор выбирает эти символы из входного потока и возвращает имя токена IF, т.е. целое число, которому соответ­ствует именованная константа IF. Ключевые слова then и else обрабатываются аналогично.

Пятый токен имеет шаблон, определенный при помощи id. Заметим, что, хотя ключевые слова наподобие i f соответствуют как своему шаблону, так и данному, Lex в ситуации, когда наибольший префикс соответствует двум или большему количеству шаблонов, выбирает первый из них. Действие при обнаружении соот­ветствия шаблону id включает следующее. 1. Вызывается функция installlD(), которая помещает найденную лексе­му в таблицу символов.

2. Эта функция возвращает указатель на запись в таблице символов, который сохраняется в глобальной переменной yylval и может быть использо­ван синтаксическим анализатором или другим компонентом компилятора. Функция installlD() имеет доступ к двум переменным, которые ав­томатически устанавливаются генерируемым Lex лексическим анализато­ром:

а) указатель yytext на начало лексемы — аналог указателя lexemeBegin на рис. 3.3;

б) целочисленная переменная yyleng, содержащая длину найденной лексемы.

3. Синтаксическому анализатору возвращается имя токена ID.

При обнаружении лексемы, соответствующей шаблону number, выполняются аналогичные действия, но с использованием вспомогательной функции installNum().3.5.3 Разрешение конфликтов в Lex

Следует упомянуть о двух правилах, которыми руководствуется Lex при вы­боре лексемы в случае, когда несколько префиксов входной строки соответствуют одному или нескольким шаблонам.

1. Предпочтение всегда отдается более длинному префиксу.

2. Если наибольший возможный префикс соответствует двум и более шабло­нам, предпочтение отдается шаблону, указанному в программе Lex первым.

Пример 3.12. Первое правило гласит, что необходимо продолжать чтение букв и цифр для поиска наибольшего префикса из этих символов, который и будет представлять собой искомый идентификатор. Оно же гласит, что <= следует рас­сматривать как единую лексему, а не как две лексемы, < и =. Второе правило делает ключевые слова зарезервированными, если они перечислены до id в про­грамме Lex. Например, если наибольший префикс входной строки, соответству­ющий какому-либо из шаблонов — then, и при этом шаблон then в программе предваряет шаблон { id}, как на рис. 3.23, то лексический анализатор возвращает токен THEN, а не токен ID.

3.5.4 Прогностический оператор

Lex автоматически считывает один дополнительный символ за последним символом, образующим лексему, а затем выполняет возврат его во входной поток с тем, чтобы из потока была изъята только распознанная лексема. Однако иногда требуется, чтобы входная строка соответствовала определенному шаблону толь­ко тогда, когда за ней следуют некоторые (предопределенные) другие символы. В этом случае в шаблоне можно использовать символ косой черты, который ука­зывает конец той части шаблона, которой должна соответствовать лексема. Все, что следует за /, представляет собой дополнительный шаблон, которому должен соответствовать остаток входной строки после найденной лексемы, чтобы было принято решение о том, что найденная лексема соответствует рассматриваемому токену. Однако часть входной строки, соответствующая второй части шаблона, не входит в найденную лексему и остается во входном потоке для последующей обработки.

Пример 3.13. В Fortran и некоторых других языках ключевые слова не являются зарезервированными. Это создает много проблем. Так, например, в инструкции

IF(I,J) = 3

IF представляет собой имя массива, а не ключевое слово. В противоположность этому в инструкции вида

IF (condition) THEN...

IF представляет собой ключевое слово. К счастью, за ключевым словом IF все­гда следуют левая скобка, некоторый текст (условие), который может содержать скобки, правая скобка и буква. Таким образом, правило Lex для ключевого слова IF можно записать как

IF / \(.* \) {letter}

Это правило гласит, что лексема, соответствующая шаблону, состоит из двух букв IF. Косая черта указывает, что имеется и дополнительный шаблон, не соответ­ствующий лексеме. Первым символом этого шаблона является левая скобка. По­скольку скобка является метасимволом языка Lex, она должна быть предварена обратной косой чертой, указывающей, что имеется в виду буквальное значение данного символа. Точка со звездочкой означает "любая строка без символа нача­ла новой строки". Точка в языке Lex представляет собой метасимвол, который означает "любой символ, кроме символа начала новой строки". Далее следует правая скобка, предваренная обратной косой чертой, обозначающей буквальное значение следующего за ней метасимвола. Наконец, за правой скобкой следу­ет символ letter, который является регулярным определением, представляющим класс символов, состоящий из всех букв.

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

Предположим, например, что выясняется соответствие этого шаблона следу­ющему префиксу входной строки:

IF(A<(B+C)*D)THEN...

Первые два символа соответствуют IF, следующий — комбинации \(, девять символов после левой скобки — шаблону.*, а идущие за ними два символа соответствуют \) и letter. Обратите внимание на то, что первая правая скобка (после С) не рассматривается, поскольку за ней следует символ, не являющий­ся буквой. В результате мы делаем вывод, что буквы IF составляют лексему, являющуюся экземпляром токена if.

[1] Кстати, сочетание уу, встречающееся в yylval и lex.yy.c, связано с генератором син­таксических анализаторов Yacc, который обычно используется в связке с Lex для построения синтаксических анализаторов.

[2] Если Lex используется вместе с Yacc, то обычно константы определяются в программе Yacc и используются в программе Lex без определений. Поскольку файл lex.уу.с компилируется совместно с выходом Yacc, эти константы окажутся доступными действиям в программе Lex.

Дата добавления: 2015-07-12