Л.Е. Карпов - Системы программирования (1114903), страница 33
Текст из файла (страница 33)
Например, идентификаторынекоторого языка программирования, представляющие собой букву, за которой следуетнуль или несколько букв или цифр, можно определить с помощью регулярноговыражения таким образом:letter(letter|digit)*Правила построения лексических единиц такого языка можно записать так:letterdigitIdNum→→→→a | b | ... | z | A | B | ... | Z0 | 1 | 2 | ... | 9letter (letter | digit)*digit+Одним из лучших инструментов для автоматического построения лексическиханализаторов является программа Lex, осуществляющая построение программыанализатора на основе обработки спецификаций, использующих регулярныевыражения. Обработка ведется на основе концепции конечного автомата, диаграммасостояний которого описывается регулярными выражениями. Первоначально этапрограмма была создана как компонент операционной системы UNIX, однако сейчасимеется множество ее вариантов, работающих в различных операционных системах, втом числе, в системах MS-DOS и Microsoft Windows.Схема использования программы Lex представляет собой трехшаговыйалгоритм:Исходнаяпрограмма Lexlex.lКомпиляторLexlex.cКомпиляторСианализатораПрограммаанализатораПоследовательностьлексемпрограммыВходной потоксимволовпрограммыlex.cПрограммаНа первом шаге подготавливается спецификация лексического анализатора, тоесть на языке Lex записываются регулярные выражения, описывающие лексемыанализируемого языка (файл lex.l).
Эта программа обрабатывается компиляторомLex, в результате чего получается текст на языке программирования Си (в настоящеевремя существуют версии программы Lex, создающие выходные тексты на другихязыках, например, Си++, Паскаль, Java). Эта программа содержит табличноепредставление диаграммы переходов, построенной по регулярным выражениям изфайла lex.l. В нее также включается стандартная программа, использующаясозданную таблицу переходов для распознавания лексем.
Действия, которые связаны срегулярными выражениями в файле lex.l, представляют собой фрагментыпрограммы на языке Си, копируемые из файла lex.l в файл lex.c. Эти действия116обычно выполняются всяким лексическим анализатором в его работе, они могутсостоять, например, в создании записей в информационной таблице компилятора.На втором шаге программа lex.c компилируется с помощью компилятора Си,в результате чего создается окончательная программа анализатора исходного языка. Натретьем шаге эта программа в своей работе осуществляет ввод и лексический анализтекстов исходного языка.Программа Lex основана на анализе и преобразовании регулярных выражений,с помощью которых записываются лексические правила.
В программе Lex введенынесколько расширенные правила записи регулярных выражений, позволяющиеоптимизировать их. Для удобства записи регулярных выражений часто вводятся классысимволов. Запись [abc], где a, b и c – символы алфавита, означает регулярноевыражение a|b|c. Сокращенный класс символов типа [a-z] означает регулярноевыражение a|b|...|z. С использованием классов символов можно описатьидентификаторы как строки, заданные регулярным выражением [A-Za-z][A-Zaz0-9]. Символ ‘-’ используется для обозначения диапазона в классе символов,символ ‘.’ означает, что в классе символов на этом месте может стоять любой символ,кроме символа новой строки.
Чтобы в класс символов поместить непосредственно самсимвол ‘.’ (или ‘-’), перед ними следует ставить символ обратной косой черты,например, класс символов [\.\-] состоит из двух символов ‘.’ и ‘-’.В записи регулярных выражений программы Lex имеются также следующиеспособы указания повторений некоторых последовательностей символов:P* - итерация (повторение нуль или более раз)P+ - усеченная итерация (повторение один или более раз)P? – необязательное вхождение (нуль или один раз)Двойные кавычки используются для цитирования, то есть непосредственногоуказания последовательности символов:“a.+*” обозначает строку из четырех символов (без самих кавычек)Приведем примеры записи регулярных выражений, правильных с точки зренияпрограммы Lex:if[a-z][a-z0-9]*[0-9]*([0-9]+“.”[0-9]*)|([0-9]*“.”[0-9]+)(“—-”[a-z]*“\n”)|(“ ”|“\n”|“\t”)+./*/*/*/*/*/*идентификатор ifидентификаторчисловещественное числовид комментарияпроизвольный символ*/*/*/*/*/*/Программа lex.l состоит из трех разделов: объявлений, правил трансляции ивспомогательных процедур.
В файле lex.l эти разделы следуют друг за другомименно в тако м пор ядке, отделяясь друг от друга стр оками, состоящими из пар ныхсимволов процента ‘%%’.Раздел объявлений состоит из описаний переменных, именованных констант(идентификаторов, используемых для представления констант) и регулярныхопределений, которые используются в качестве компонентов регулярных выражений вправилах трансляции:117%{/* Определение именованных констант,обозначающих коды лексем, например,ID, NUMBER, DELIMITER*/%}/*delimspacesletterdigitidnumberРегулярные определения*/[ \t\n\b\v\r]{delim}+[A-Za-z][0-9]{letter}({letter}|{digit})*{digit}+%%Обычно описания переменных и констант записываются внутри скобок ‘%{’ и‘%}’. Все, что находится внутри таких скобок, непосредственно переписывается всоздаваемую программу лексического анализатора, не рассматривается как частьрегулярных определений или правил трансляции.
Так же обрабатываютсявспомогательные процедуры, входящие в третий раздел программы lex.l.Правила трансляции программы lex.l имеют видpi{действиеi}где каждое pi есть регулярное выражение, а каждое действиеi есть фрагментпрограммы, описывающий выполняемые лексическим анализатором действия, еслилексема соответствует регулярному выражению (шаблону) pi. Действия записываютсяна том же языке программирования, на котором должен быть сгенерирован анализатор(например, на том же языке Си):{spaces}{id}{number}“<”“<=”.{{{{{{/* Действия не определены, возврата нет */ }yylval = found_id (); return ID; }yylval = found_num (); return NUMBER; }yylval = LT; return RELATION; }yylval = LE; return RELATION; }/* Такое правило обычно ставится последним.Оно позволяет фиксировать ошибку,связанную с появлением символа, которыйне может начинать никакую лексему*/ }%%int found_id (void) {/* На первый символ идентификатора указывает переменная yytext.Длина идентификатора содержится в переменной yyleng.Процедура заносит лексему в таблицу анализатора*/}int found_num (void) {/* На первый символ числа указывает переменная yytext.Длина числа содержится в переменной yyleng.Процедура заносит лексему в таблицу анализатора*/}Третий раздел программы содержит различные вспомогательные процедуры,которые могут быть скомпилированы отдельно, но загружены должны быть вместе слексическим анализатором.Лексический анализатор, создаваемый программой Lex, работает ссинтаксическим анализатором по схеме однопроходного компилятора.
Главной118программой является синтаксический анализатор, который запрашивает лексемы улексического анализатора, начиная чтение оставшейся части исходного текстапосимвольно и продолжая его до тех пор, пока не будет найдена самая длиннаяпоследовательность, соответствующая одному из регулярных выражений pi (этопервое правило разрешения неоднозначностей при обработке регулярных выражений).Затем для найденного шаблона выполняется соответствующее действиеi. Чаще всегоэто действие возвращает управление синтаксическому анализатору (то естьзаканчивается оператором вида return Token).
Но так бывает не всегда. В этихслучаях лексический анализатор продолжает поиск лексем в тексте, пока действие,соответствующее одной из них, не возвратит управление синтаксическому анализатору.Такой поиск лексем позволяет осуществить обработку последовательностей пробелов икомментариев.Лексический анализатор возвращает синтаксическому только код обнаруженнойлексемы. В программе Lex предусмотрено, что дополнительные атрибуты лексемымогут содержаться в глобальной переменной yylval, текстовое представлениелексемы находится в переменной yytext, а длина лексемы в символах – в переменнойyyleng.Если какой-либо лексеме соответствуют сразу несколько шаблонов, товыбирается тот из них, который размещается в перечне шаблонов первым, поэтомучастные шаблоны следует ставить в этом перечне раньше общих (это второе правилоразрешения неоднозначностей при обработке регулярных выражений – порядокследования регулярных выражений имеет определяющее значение).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
