lex (813547), страница 11
Текст из файла (страница 11)
Вотличие от обычных правил, которые актуальны в любом в любом состоянии лексическогоанализатора, правила с предусловиями a priori не активны и не рассматриваются в процесселексического анализа входного потока, пока не установлены метки предусловий их регулярныхвыражений. Для управления активностью помеченных правил используется оператор BEGIN,который может устанавливать или сбрасывать метки предусловий. Он может применяться вдействиях правил, распознающих выполнение соответствующих предусловий, в одном из двухформатов:BEGIN STATE;илиBEGIN 0;В первом формате оператор BEGIN устанавливает состояние лексического анализатора,которое обозначено меткой STATE.
После его выполнения становятся активными все правила сметкой <STATE>в левом контексте их регулярных выражений. При этом аргументомоператора BEGIN может быть любая метка из списка предусловий, специфицированныхдирективой %Start секции описаний. В общем случае вызов оператора BEGIN с ненулевымаргументом в действии обычного правила позволяет расширить список активных правил,добавляя к нему правила, метка предусловия которых совпадает с аргументом оператораBEGIN. Однако если вызов оператора BEGIN осуществляется в действии помеченногоправила, то активность сохраняют только те правила, метка предусловия которых совпадает саргументом оператора BEGIN. Второй формат, когда вызов оператора BEGIN осуществляетсяс нулевым аргументом, позволяет удалить из списка активных правил все правила спредусловиями.
Это бывает необходимо для возврата лексического анализатора в исходноесостояние, где все помеченные правила неактивны.Различные форматы использования оператора BEGIN и правил с предусловиями иллюстрируетследующий пример спецификаций лексического анализатора четности или нечетностиколичества единиц в бинарной последовательности, состоящей из символов 0 и 1, которуюзавершает символ перевода строки:%Start EVEN ODD%%<EVEN>1BEGIN ODD; /* Переход в нечетное состояние из четного */<EVEN>\n{ /* Оценка четного состояния */puts(" Четное число единичных разрядов");BEGIN 0;}<ODD>1BEGIN EVEN; /* Переход в четное состояние из нечетного */<ODD>\n{ /* Оценка нечетного состояния */puts(" Нечетное число единичных разрядов");BEGIN 0;}1BEGIN ODD; /* Переход в нечетное состояние из исходного */\nputs(" Нулевое число единичных разрядов");.; /* Блокировка стандартного вывода */В данном примере лексический анализатор реализует конечный автомат с 3-мя состояниями, вкоторых он может находиться, когда из входного потока получено, соответственно, нулевое,нечетное и четное число единиц бинарной последовательности.
Состояния с четным инечетным числом единиц обозначены, соответственно, метками предусловий EVEN и ODD,которые декларированы директивой %Start секции описаний. Исходное состояние с нулевымчислом единиц не имеет метки и определено по принципу исключения двух других состояний.Переход между состояниями происходит при стандартном вводе символов единицы ('1') иперевода строки ('\n'). При этом, символ '1' вызывает переход в состояние, либо снечетным, либо с четным количеством единиц, в зависимости от текущего числа полученныхединиц бинарной последовательности, а символ перевода строки ('\n') означает возврат висходное состояние для анализа следующей бинарной последовательности.
Таблицу переходовмежду состояниями формализуют 6 лексических правил, по 2 на каждое состояние. Одноправило каждой пары определяет переход при вводе символа '1', а другое – при поступлениисимвола перевода строки ('\n').В частности, последняя пара указанных правил, которые не имеют предусловий, обслуживаетисходное состояние. Согласно этим правилам при вводе символа перевода строки в исходномсостояниилексическийанализатордиагностируетнулевуюилипустуюбинарнуюпоследовательность, отображая соответствующее информационное сообщение в потокестандартного вывода с помощью библиотечной функции puts системы программирования C.Ввод символа '1' в исходном состоянии вызывает переход в состояние с нечетным числомединиц, которое устанавливается оператором BEGIN с аргументом ODD в действие этогоправила.После этого становятся активными два средних правила с меткой предусловия ODD в левомконтексте регулярных выражений, которые обслуживают переходы из состояния с нечетнымчислом единиц.
По этим правилам при вводе символа перевода строки лексический анализатордиагностирует бинарную последовательность с нечетным числом единиц, отображаясоответствующее информационное сообщение в потоке стандартного вывода с помощьюбиблиотечной функции puts системы программирования C, и возвращается в исходноесостояние оператором BEGIN с нулевым аргументом. Ввод символа '1' в этом состояниивызывает переход в состояние с четным числом единиц, которое устанавливается операторомBEGIN с аргументом EVEN.
При этом метка предусловия ODD будет автоматически сброшена,потому что вызов оператора BEGIN осуществляется в действии правила с предусловием.После этого становятся активными два первых правила с меткой предусловия EVEN в левомконтексте регулярных выражений, которые обслуживают переходы из состояния с четнымчислом единиц, а средние правила с меткой предусловия ODD теперь неактивны. Согласноэтим правилам при вводе символа перевода строки лексический анализатор диагностируетбинарную последовательность с четным числом единиц, отображая соответствующееинформационное сообщение в потоке стандартного вывода с помощью библиотечной функцииputs системы программирования C, и возвращается в исходное состояние оператором BEGIN снулевым аргументом.
Ввод символа '1' в этом состоянии вызывает переход в состояние снечетным числом единиц, которое устанавливается оператором BEGIN с аргументом ODD вдействии этого правила. При этом метка предусловия EVEN будет автоматически сброшена,потому что вызов оператора BEGIN осуществляется в действии правила с предусловием. Послеэтого снова становятся активны два средних правила с предусловием ODD в левом контекстерегулярных выражений, а правила с меткой предусловия EVEN теперь опять неактивны.Таким образом, в начале лексического анализа все помеченные правила неактивны и обработкабинарной последовательности происходит по двум правилам исходного состояния. Затем привводесимвола'1'поочередностановятсяактивнымипарыпомеченныхправил,обслуживающих состояния с четным или нечетным числом единиц, и дальнейшая обработкабинарной последовательности осуществляется по активной паре помеченных правил.
При этомправила исходного состояния по-прежнему активны, но неактуальны, потому что ониподавляются эквивалентными активными правилами, которые расположены текстуально вышевсекцииправил.последовательности,Онистановятсякогдаприактуальнымистандартномвводепридостижениисимволаконцапереводабинарнойстрокипослесоответствующей диагностики, отображаемой с помощью библиотечной функции puts системыпрограммирования C, происходит возврат в исходное состояние, где все помеченные правиланеактивны,илексическийанализаторготовкобработкеследующейбинарнойпоследовательности из своего исходного состояния.В заключение следует отметить, что исходя из косметических соображений, кромерассмотренных правил, в конце секции правил включено еще правило с пустым действием.
Ононеобходимо для того, чтобы блокировать стандартный вывод любых символов входногопотока, которые отсутствуют в регулярных выражениях остальных правил и должныотображаться по умолчанию.НЕОДНОЗАЧНЫЕ ПРАВИЛАВ процессе лексического анализа входного потока может оказаться так, что входнаяпоследовательность символов соответствует регулярным выражениям нескольких правил. Вэтом случае возникает неоднозначность выбора действия при обработке входного потока.Чтобы разрешить указанную неоднозначность генератор LEX использует детерминированныймеханизм, который основан на следующих двух принципах.
Всегда выбирается действиеправила, распознающего наиболее длинную последовательность символов входного потока, аесли несколько правил распознают одинаковую входную последовательность равной длины, товыполняется действие первого из них в секции правил.
Указанные принципы разрешениянеоднозначности выбора действий иллюстрирует следующий пример двух правил, которыепересекаются по области определения своих регулярных выражений:%%[Mm]ake{/* Действие правила 1 */}[A-Za-z]+{/* Действие правила 2 */}Регулярному выражению первого правила соответствуют только слова Make и make.Регулярному выражению второго правила удовлетворяют любые последовательности строчныхи/или заглавных букв, в том числе содержащие фрагменты, которые соответствуютрегулярномувыражениюпервогоправила,например,илиMakefileилиmakefile.Автоматическое разрешение неоднозначности выбора действий в данном случае гарантируетобработку отдельных слов Make и make по первому правилу, в то время как все остальные словабудут распознаваться по второму правилу.В частности, хотя слово make удовлетворяет регулярным выражениям обоих правил, но онобудет обрабатываться по действию первого правила.
Так происходит потому, что в данномслучае оба правила распознают последовательность равной длины (4 символа), следовательно,приоритет имеет правило, которое расположено текстуально выше в секции правил. Однакоесли во входном потоке будет слово Makefile, то его обработка должна осуществляться всоответствии с действием второго правила. Так происходит потому, что в данном случаепервому правилу удовлетворяют только 4 начальные символа этого слова, в то время как все 8символов данного слова соответствуют второму правилу.
Следовательно, приоритет будетиметь второе правило, которому удовлетворяет более длинная последовательность символоввходного потока.Такимобразом,врассмотренномпримеремеханизмавтоматическогоразрешениянеоднозначности правил позволяет различать во входном потоке отдельные слова Make илиmake и все другие слова, где они могут присутствовать как фрагмент. Это может бытьпрактически важно, например, для подсчета количества повторений слов Make и make вовходном потоке без учета присутствия таких сочетаний в других словах. В этом случаедействие первого правила должно содержать счетчик повторений этих слов, а действие второгоправила может быть пустым.ФУНКЦИОНАЛЬНАЯ РЕАЛИЗАЦИЯ ПРАВИЛКак отмечалось выше, по файлу спецификации лексем генератор LEX должен формировать наязыке программирования C исходный текст лексического анализатора.
Он имеет определеннуюфункциональную структуру, основными компонентами которой являются функции yylook иyylex, автоматически формируемые по регулярным выражениям и действиям секции правилфайла спецификации лексем.Функцияyylookреализуетдетерминированныйконечныйавтомат,которыйдолженосуществлять разбор входного потока символов по регулярным выражениям секции правил.Формально этот конечный автомат задается таблицей переходов, которая строитсяавтоматически генератором LEX по регулярным выражениям секции правил и используетсястандартной заготовкой функции yylook для распознавания лексем. В ранних версияхгенератора LEX заготовка функции yylook предоставлялась в файле ncform, который обычнорасполагался в каталоге /usr/lib/lex файловой системы OS UNIX.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
