А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 38
Текст из файла (страница 38)
3.18. Набросок реализации диаграммы переходов лля ге1ор Типичное поведение состояния можно увидеть на примере состояния О. Функция пехсСЬаг ( ) получает очередной символ из входного потока и присваивает его локальной переменной с. Затем выполняется проверка соответствия с трем ожидаемым символам, и в каждом случае выполняется переход в состояние„определяемое диаграммой переходов на рис. 3.13.
Напрнмср, сслн считанный символ— =, выполняется переход в состояние 5. Если считанный символ не принадлежит к множеству символов, с которых может начинаться оператор сравнения, вызывается функция йа11 ( ) . Какие именно действия выполняет эта функция, зависит от глобальной стратегии лексического анализатора по восстановлению после ошибок. Она должна сбросить указатель йогиагс( в значение 1ехешеВедуп для того, чтобы дать возможность применить другую диаграмму переходов к началу необработанной части входного потока. Затем она может изменить значение переменной зевке на стартовое состояние для другой диаграммы переходов, которая будет заниматься поиском другого токе- 38б Глава 3.
Лексический анализ на. Или, если оставшихся неиспользованными диаграмм переходов больше нет, функция йах1() может инициализировать фазу исправления ошибок, которая попытается исправить входной поток и найти лексему так, как это описано в разделе 3.1.4. На рнс. 3.18 показаны также действия для состояния 8. Поскольку состояние 8 помечено звездочкой, требуется вернуть указатель входного потока на одну позицию назад (т.е. вернуть с назад во входной поток). Эта задача решается вызовом функции пег.касС ( ).
Поскольку состояние 8 представляет распознанную лексему >, второй компонент (с именем агскзЬц1е) возвращаемого объекга устанавливается равным ЯТ, коду для данного оператора. и Давайте рассмотрим, каким образом код наподобие приведенного на рис. 3.18 может быть встроен в лексический анализатор. !. Можно последовательно испытывать диаграммы переходов для каждого токена. В таком случае функция йаз3.
() из примера 3.10 при вызове сбрасывает значение указателя йокмагд и приступает к новой диаграмме переходов. Этот метод позволяет нам использовать диаграммы переходов для отдельных ключевых слов наподобие диаграммы, предложенной на рис. 3.15. Однако, чтобы ключевые слова были зарезервированными, мы должны использовать их диаграммы переходов до диаграммы переходов для (й. 2. Можно работать с разными диаграммами переходов "параллельно", передавая очередной считанный символ им всем и выполняя соответствующий переход в каждой из диаграмм переходов.
При использовании этой стратегии нужно быть очень осторожным в ситуации, когда одна диаграмма переходов находит лексему, соответствующую ее шаблону, но при этом другая диаграмма (или даже несколько) все еще способна обрабатывать входной поток. Обычно используемая стратегия состоит в выборе самого длинного префикса входного потока, соответствующего какому-либо из шаблонов.
Это правило вынуждает, например, предпочесть идентификатор сЬепех1 ключевому слову с(теп, а оператор -> — оператору —. 3. Предпочтительный подход — и именно он будет использован в последующих разделах — состоит в объединении всех диаграмм переходов в одну. Эта диаграмма переходов считывает символы до тех пор, пока возможные следующие состояния не оказываются исчерпаны. После этого выбирается наибольшая лексема, соответствующая некоторому шаблону (правило, рассматривавшееся в предыдущем пункте). В нашем примере такое объединение выполняется достаточно просто, поскольку никакие два токена не начинаются с одного и того же символа, так что первый же символ сразу говорит нам, какой токен мы ищем.
Таким образом, можно просто 3.4. Распознавание токенов объединить состояния О, 9, 12 и 22 в одно стартовое состояние, оставив все остальные состояния без изменений. Однако, как мы вскоре увидим, в общем случае задача объединения диаграмм переходов для нескольких токенов сушественно более сложная.
3.4.5 Упражнения к разделу 3.4 Упражнение 3.4.1. Разработайте диаграммы переходов для распознавания язы- ков, определяемых регулярными выражениями в упражнении 3.3.2. Упражнение 3.4.2. Разработайте диаграммы переходов для распознавания языков из условия упражнения 3.3.5. Следующие упражнения, по 3.4.!2 включительно, знакомят читателей с алгоритмом Ахо — Корасик (А)10 — Согаз1ск) для распознавания набора ключевых слов в текстовой строке за время, пропорциональное длине текста и сумме длин ключевых слов.
В этом алгоритме используются диаграммы переходов специального вида, которые называются лучами (пте)2. Луч представляет собой диаграмму переходов с древовидной структурой с различными метками на дугах, ведущих от узла к дочерним по отношению к нему узлам. Листья луча представляют распознанные ключевые слова.
Кнут (Кппгй), Моррис (Могпз) и Пратт (Ргап) представили алгоритм (алгоритм Кнута — Морриса — Пратта, КМП) для распознавания одного ключевого слова 6162... 6п в текстовой строке. Здесь луч представляет собой диаграмму переходов с и состояниями, от О до п. Состояние Π— начальное, а состояние п — допускающее„т.е. представляющее распознанное ключевое слово. Для каждого состояния л от О до п — 1 имеется переход в состояние л+ 1, помеченный символом 6, ь1.
Например, луч для ключевого слова аЬаЬаа имеет вид а ь а ь о а 0 1 2 3 4 ® Для быстрой обработки текстовой строки и поиска в ней ключевого слова можно для ключевого слова 6162... 6„и позиции л в нем (соответствуюшей состоянию л в луче) определить функцию отказа (Га11пге йзпс1юп) Г" (и), вычисляемую так, как показано на рис. 3.19. Смысл этой функции в том, что 6162... 67(,) представляет собой наибольший истинный префикс строки 6162...
6„который одновременно является суффиксом 6162... 6,. Причина, по которой функция Г" (л) так важна, заключается в том, что если мы попытаемся сопоставить текстовую строку слову 6162... 6п и в первых л позициях будет обнаружено совпадение, 'Здесь использован перевод этого термина иэ книги Кнут Д. Искусство программировании. ХЗ. — Мл Издательский дом "Вильяме", 2000 (раздел 6.3, с. 527). — Прим. лер. 188 Глава 3. Лексический анализ а в следующей позиции — несовпадение (т.е. очередной символ текстовой строки не будет совпадать с 6,+!), то 7' (а) — самый длинный префикс слова 6|6з...
6„, который может соответствовать текстовой строке до текущей точки. Само собой разумеется, следующий символ текста при этом должен быть 6~(,)+,, иначе проблема несовпадения останется и придется рассматривать более короткий префикс, 6у(71,)Р !) !=О„' 2) Д1) =О; 3) !ог (а = 1! я ( и; а++) ( 4) ий!1е (! ) О Йй 6,н ' = 6ьн) г = У(!)' 5) И(6.~.~ — — — 6н~~) ( 6) 1=!+1; 7) 7(а+ 1) = 1; 8) е!яе !'(а+1) = О; Рис. 3. !9.
Алгоритм для вычисления функции отказа для ключевого слова 6~ 6з... 6„ В качестве примера приведем функцию отказа для луча, построенного ранее для слова аЬаЬаа: Например, состояния 3 и 1 представляют префиксы аЬа и а соответственно. )'(3) = 1, поскольку а является самым длинным истинным префиксом аЬа, который одновременно является суффиксом аЬа. 7" (2) = О, поскольку самый длинный префикс аЬ, являющийся одновременно ее суффиксом, — пустая строка.
Упражнение 3.4.3. Постройте функцию отказа для следующих строк: а) аЬаЬаЬааЬ; б) аааааа; в) аЪЬааЪЬ. ! Упражнение 3.4.4. Докажите по индукции по а, что алгоритм на рис. 3.19 кор- ректно вычисляет функцию отказа. !! Упражнение 3.4.5. Покажите, что присваивание ! = )'(1) в строке 4 алгоритма на рис. 3.19 выполняется максимум и раз. Покажите, что, следовательно, весь алгоритм требует О (и) времени для обработки ключевого слова длиной п. 189 3.4. Распознавание токеиов Вычислив функцию отказа для ключевого слова бзбг... би, мы можем сканировать строку а1аг...
а в поисках данного кпючевого слова за время 0(т). Алгоритм, приведенный на рис. 3.20, перемещает ключевое слово вдоль строки, сравнивая символы ключевого слова с символами текстовой строки. Если происходит несовпадение после соответствия в символов, то алгоритм смещает ключевое слово вправо на в — ~ (в) позиций, так что рассматриваются как совпадающие со строкой только первые 1' (в) символов ключевого слова. !) в=О; 2) 1ог(1=1;г<т;(-н-)( 3) зч$ийе (в > 0 вссс а, ! = Ь,з.1) в = Дв); 4) 11 (а, == Ь,ч 1) в = в + 1; 5) 11(в = — п) гегигп "уев"; 6) гегпгп "по"; Рис. 3.20.
Алгоритм КМП для проверки наличия в строке а1аг...а ключевого слова б1бг...б„в качестве подстроки за время О (т + и) Упражнение 3.4.6. Примените алгоритм КМП к проверке вхождения ключевого слова аЬаЬаа в качестве подстроки в а) аЬаЬаЬааЬ; б) аЬаЬаЬЬаа. !! Упражнение 3.4.7. Покажите, что алгоритм на рис. 3.20 корректно определяет, является ли ключевое слово подстрокой данной строки. Указание: примените индукцию по г. Покажите, что для всех 1 значение в после строки 4 представляет собой длину наибольшего префикса ключевого слова, являющегося суффиксом строки а1аг...
а,. !! Упражнение 3.4.8. Покажите, что время работы алгоритма на рис. 3.20 составляет О (т+ п), в предположении, что функция ( уже вычислена и ее значения хранятся в массиве, проиндексированном в. Упражнение 3.4.9. Строки Фибоначчи определяются следующим образом. !. в1=Ь. 2. вг = а. 3. вь=вь 1вь гприй>2. 190 Глава 3. Лексический анализ Например, аз = аЬ, а4 = аЬа, аа = аЬааЬ. а) Какова длина строки а„? б) Постройте функцию отказа для ав.
в) Постройте функцию отказа для ат. 1! г) Покажите, что функция отказа для любой строки а„может быть выражена следующим образом: ! (1) = ! (2) = О, а для 2 < з < )а„) значения функции У (у) = 3 — ~аь ~~, где (с — наибольшее целое число, такое, что !аь~ <3+ 1. !! д) Чему равно наибольшее число последовательных применений функции отказа в алгоритме КМП при попытке определить, входит ли ключевое слово аь в текстовую строку аьч ~? Ахо (Або) и Корасик (Согаз(ск) обобщили алгоритм КМП для распознавания любого множества ключевых слов в текстовой строке. В этом случае луч является истинным деревом с ветвлением в корне.
Имеется по одному состоянию для каждой строки, которая является префиксом (не обязательно истинным) некоторого ключевого слова. Родительским по отношению к состоянию, соответствующему строке Ь|Ьз... Ьы является состояние, соответствукпцее Ь,Ьз... Ьь и Состояние является конечным, если оно соответствует полному ключевому слову. Например, на рис.
3.21 показан луч для ключевых слов Ье, вЬе, Ьйв и Ьегв. Рис. 3.2!. Луч лля ключевых слов Ье, йе, Ыа и Ьега Функция отказа для луча в общем случае определяется следующим образом. Пусть а — состояние, соответствующее строке 6~ Ьз... Ь„. Тогда 1" (а) — это состояние, соответствующее самому длинному истинному суффиксу Ь~Ьз... Ь„, который является также префиксом некоторого ключевого слова. Например, вот как выглядит функция отказа для луча на рис. 3.21: 191 3.5. Генератор лексических анализаторов Пех ! Упражнение 3.4.10. Модифицируйте алгоритм, приведенный на рис. 3.19, для вычисления функции отказа для лучей в общем случае. Указание: основное отличие заключается в том, что мы не можем просто проверить равенство или неравенство 6,,1 и !ь.ь1 в строках 4 и 5 на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
