А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 39
Текст из файла (страница 39)
3.19. Из любого состояния могут иметься несколько переходов для ряда символов, как, например, переходы для е и 1 из состояния ! на рис. 3.21. Любой из этих переходов может привести в состояние, которое представляет самый длинный суффикс, являющийся также префиксом. Упражнение 3.4.11. Постройте лучи н вычислите функцию отказа для следующих множеств ключевых слов: а) ааа, аЬааа н аЬаЬааа; б) а11, га11, йаса1, 11аша и 1ате; в) р1ре, рек, 1сет, сешрег и регреспа1. ! Упражнение 3.4.12.
Покажите, что разработанный вами алгоритм нз упражнения 3.4.!О будет выполняться за время, линейно пропорциональное сумме длин ключевых слов. 3.5 Генератор лексических анализаторов Ьех В зтом разделе мы познакомимся с программным инструментом под названием Ьех (или, в более поздних реализациях, Р1ех), который позволяет определить лексический анализатор, указывая регулярные выражения для описания шаблонов токенов. Входные обозначения для 1 ех обычно называют языком 1ех, а сам инструмент — компилятором Аех.
Компилятор 1.ех преобразует входные шаблоны в диаграмму переходов н генерирует код (в файле с именем 1ех. уу. с), имитирующий данную диаграмму переходов. Механизм преобразования регулярных выражений в диаграммы переходов является темой следующих разделов данной главы; здесь же мы остановимся на языке Ьех. 3.5.1 Использование 1 ех На рис. 3.22 показана схема использования Ьех. Входной файл 1ех. 1 написан на языке 1.ех н описывает генерируемый лексический анализатор. Компилятор Ьех преобразует 1ех . 1 в программу на языке программирования С в файле с именем 1ех. уу.
с. Этот файл компилируется компилятором С в файл с названием 192 Глава 3. Лексический анализ а . опс, как обычно. Выход компилятора С представляет собой работающий лексический анализатор, который может получать поток входных символов и выдавать поток токенов. Исходнвв программа ьех 1ех.1 1ех.уу.с 1ех.уу.с Компилятор ° е, опт С Входной поток а . опт , Паследоввтельность токенов 1 Рис.
3.22. Создание лексического анализатора с помощью мех Обычно скомпилированная программа на языке С, которая на рис. 3.22 показана как а. она, используется в качестве подпрограммы синтаксического анализатора. Это функция на языке программирования С, которая возвращает целое число, представляющее собой код одного из возможных имен токенов. Значение атрибута, которое может быть другим числовым кодом, указателем на запись таблицы символов или просто отсутствовать, помещается в глобальную переменную уу1тга11, которая совместно используется лексическим и синтаксическим анализаторами. Этот метод позволяет вернуть из функции как имя токена, так и значение его атрибута.
3.5.2 Структура программ 1 ех Программа Ьех имеет следующий вид: Объявления ЪЪ Правила трансляции %Ъ Вспомогательные функции Раздел объявлений включает объявления переменных, именованные констанпзы (тап1гез1 сопз1ап1 — идентификаторы констант, нитример имена токенов) и регулярные определения в стиле раздела 3.3.4. 'Кстати, сочетвние уу, встречвющееся в уу1ча1 и 1ех. уу.
с, связано с генератором синтвксических анализаторов тасс, который будет рассматриваться в разделе 4.9 и который обычно используется в связке с 1 ех. 193 15. Генератор лексических анализаторов Ьех Правила трансляции имеют вид Шаблон ( Действие ) Каждый шаблон является регулярным выражением, которое может использовать регулярные определения из раздела объявлений. Действия представляют собой фрагменты кода, обычно написанные на языке программирования С, хотя созданы многие разновидности Ъех для других языков программирования.
Третий раздел содержит различные дополнительные функции, используемые в действиях. Эти функции могут также компилироваться отдельно и загружаться лексическим анализатором во время работы. Лексический анализатор, созданный Ьех, работает во взаимодействии с синтаксическим анализатором. При вызове синтаксическим анализатором лексический анализатор считывает по одному символу оставшийся непрочитанным входной поток, пока не будет найден самый длинный префикс входного потока, соответствующий одному из шаблонов Р;.
Затем лексический анализатор выполняет связанные с ним действия Аь Обычно А, содержит возврат в синтаксический анализатор, но если это не так (например, если Р, описывает пробельные символы или комментарии), то лексический анализатор продолжает поиск дополнительных лексем, пока одно из соответствующих действий не приведет к возврату из функции лексического анализатора в синтаксический анализатор. Лексический анализатор возвращает синтаксическому анализатору единственное значение, имя токена, но использует при этом совместно используемую целочисленную переменную уу1зга1 для передачи при необходимости дополнительной информации о найденной лексеме.
Пример 3.11. На рис. 3.23 приведена программа 1ех, которая распознает токены, представленные на рис. 3.12, и возвращает найденный токен синтаксическому анализатору. Рассмотрение приведенного кода поможет нам изучить многие важные возможности Ьех. В разделе объявлений мы встречаем пару специальных скобок — Ъ( и Ъ |. Все, что заключено в эти скобки, копируется непосредственно в 1ех. уу. с и не рассматривается как регулярное определение. Обычно здесь помещаются определения именованных констант с использованием конструкции Фбеййпе языка программирования С для назначения каждой именованной константе уникального целочисленного кода. В нашем примере мы перечислили в комментарии именованные константы ЬТ, 1Р и другие, но не привели определения, назначающие им конкретные числовые значения." 'Если ьах используется вместе с тасс, то обычно константы определяются в программе тасс и используются в программе Ьех без опрсдслсний.
Поскольку файл Хех. уу.с компилирустся совместно с выходом тасс, зти константы окажутся доступными действиям в программе Ьех. Глава 3. Лексический анализ $( /* Определения именованных констант 1Т, 1Е, ЕЯ, НЕ, ОТ, ОЕ, 1Р, ТНЕН, ЕЬЯЕ, 1Р, НРМВЕВ, ВЕЬОР */ /* Регулярные определения */ с(е11щ [ 1~Лп] юз (с(е11щ) + 1еккег [а-Еа-г] с(191Г [0-9] 1с) (1есгег)((1екгег))(с(191Г))* ппюЬег (г(191Г)+(~.(с(191т)+)?(Е[+-]?(с(191г)+)? функции */) Ьпс Ьпзга111Р() (/* Функция для внесения лексемы (на первый символ которой указывает указатель уусехг и длина которой равна уу1епд) в таблицу символов. Возвращает указатель на соответствующую запись таблицы символов */ Ьпг Ьпзса11Нцт() (/* Аналогична функции Ьпзса111Р, но помещает числовые константы в отдельную таблицу */ Рнс.
3.23. Программа Ьех лля распознавания гогенов на рис. 3.12 (из) 11 гЬеп е1ве (Ьг)) ( ~пипЬе т ) "<" "<=" "<>" ~>! "> (/* Нет (гегптп (гекпгп (гекпгп (уу1ча1 (уу1ча1 (уу1ча1 (уу1ча1 (уу1ча1 (уу1ча1 (уу1ча1 (уу1ча1 действий и выхода из (1Р);) (ТНЕУ)г) (ЕЬЯЕ)г) (1пк) Ьпзка111Р(); (Ьпк) 1пвка11Нпт() = ЬТ; тесигп(ВЕЬОР); = ЬЕ; гетпгп(ВЕЬОР)г = ЕЯ; гетптп(ВЕЬОР)г = ИЕг гетпгп(ВЕЬОР)г = СТг гетпгп(ВЕЬОР); = СЕг гесптп(ВЕЬОР)г гекигп(1Р);) тегцтп(ЬПЗМВЕВ)г) ) ) ) 3.5. Генератор лексических анализаторов Ьех 195 Кроме того, в разделе объявлений имеется последовательность регулярных определений.
Они используют расширенную запись регулярных выражений, описанную в разделе 3.3.5. Регулярные определения, используемые в следующих за ними определениях или шаблонах правил трансляции, помещаются в фигурные скобки. Так, например, с(е(Ьл определено как сокращение для класса символов, состоящего из пробела, символа табуляции и символа новой строки (последние два символа представлены, как во всех командах (ЛЧ)Х, при помощи обратной косой черты, за которой следует соответственно буква ~ или п). Затем из определено как один или несколько разделителей при помощи регулярного выражения (г(е11в)+.
Обратите внимание, что в определениях М и литЬег скобки используются в качестве метасимволов группирования и не обозначают сами себя. Напротив, буква Е в определении питЬег означает саму себя. Если мы хотим использовать один из метасимволов ).ех, такой как любая скобка,, +, * или?, так, чтобы он обозначал сам себя, то его следует предварить обратной косой чертой. Например, в определении литЬе«имеется последовательность |., представляющая обычную точку, поскольку просто точка в регулярных выражениях является метасимволом, представляющим "любой символ", как это принято в регулярных выражениях (Лч(Х. В разделе вспомогательных функций имеются функции 1пака1110 ( ) и 1пвГа11Ицаз( ). Так же, как и часть раздела объявлений, находящаяся между % (...
Ъ ), все, что находится во вспомогательном разделе, просто копируется в файл 1ех. уу . с, но может использоваться в действиях. Наконец, рассмотрим некоторые из шаблонов и правил в среднем разделе на рис. 3.23. Первым указан идентификатор жз, объявленный в первом разделе и связанный с пустым действием. Если встречается пробельный символ, то выполняется не возврат в синтаксический анализатор, а поиск новой лексемы. Второй токен имеет простой шаблон регулярного выражения Ей. Если во входном потоке встречаются две буквы 1й, за которыми не следует другая буква или цифра (в зтом случае мы имеем дело с более длинным префиксом входной строки, соответствующим шаблону для Ы), лексический анализатор выбирает эти символы из входного потока и возвращает имя токена 1Р, т.е.
целое число, которому соответствует именованная константа 1Р. Ключевые слова К)зеп и е1ве обрабатываются аналогично. Пятый токен имеет шаблон, определенный при помощи Ы Заметим, что, хотя ключевые слова наподобие 1й соответствуют как своему шаблону, так и данному, Ъек в ситуации, когда наибольший префикс соответствует двум или большему количеству шаблонов, выбирает первый из них. Действие при обнаружении соответствия шаблону Ы включает следующее. 19б Глава 3. Лексический анализ !. Вызывается функция ТпвСа111() ( ), которая помещает найденную лексему в таблицу символов. 2. Эта функция возвращает указатель на запись в таблице символов, который сохраняется в глобальной переменной уу1ча1 и может быть использован синтаксическим анализатором или другим компонентом компилятора.
Функция 1пвса11?О( ) имеет доступ к двум переменным, которые автоматически устанавливаются генерируемым Ьех лексическим анализатором: а) указатель уусехс на начало лексемы -- аналог указателя 1ехевеВедтп на рис. 3.3; б) целочисленная переменная уу1епд, содержащая длину найденной лексемы. 3. Синтаксическому анализатору возвращается имя токена 1)э. При обнаружении лексемы, соответствующей шаблону питБег, выполняются аналогичные действия, но с использованием вспомогательной функции 1пвса11)чшв(). о 3.5.3 Разрешение конфликтов в Ьех Следует упомянуть о двух правилах, которыми руководствуется Ьех при выборе лексемы в случае, когда несколько префиксов входной строки соответствуют одному или нескольким шаблонам.
!. Предпочтение всегда отдается более длинному префиксу. 2. Если наибольший возможный префикс соответствует двум и более шаблонам, предпочтение отдается шаблону, указанному в программе Ьех первым. Пример 3.12. Первое правило гласит, что необходимо продолжать чтение букв и цифр лля поиска наиболыпего префикса из этих символов, который и будет представлять собой искомый идентификатор. Оно же гласит, что <= следует рассматривать как единую лексему, а не как две лексемы, < и =. Второе правило делает ключевые слова зарезервированными, если они перечислены до и( в программе Ьех.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
