А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 42
Текст из файла (страница 42)
3.31 приведены определения некоторых функций, которые описывают базовые вычисления состояний Ю, необходимые для данного алгоритма. Здесь в — единственное состояние Ю, в то время как Т вЂ” множество состояний Х. Мы должны исследовать те множества состояний, в которых М может оказаться после обработки некоторой входной строки. Начнем с того, что перед прочтением первого символа Аг может находиться в любом из состояний в-с1овиге (вс), 207 3.7. От регулярных выражений к автоматам ОПЕРАЦИЯ е-с!охи«е (в) ОписАние Множество состояний НКА, достижимых из состояния в при одном е-переходе Множество состояний НКА, достижимых из состояния в из множества Т при одном е-переходе; = 13,гге-с!охиге (е) Множество состояний НКА, в которые имеется переход из некоторого состояния в Е Т при входном символе а с-с1озиге (Т) лгоге (Т, а) Рнс.
3.31. Операции над состояниями НКА где ео — начальное состояние. Предположим, что после чтения строки х автомат Аг может находиться в множестве состояний Т. Если следующий прочитанный символ — а, то Аг может перейти в любое из состояний иго~ е (Т, а). Однако после чтения а может быть выполнено несколько е-переходов; таким образом, после прочтения ха конечный автомат А! может быть в любом состоянии из множества е-с1озиге(нгоге (Т, а)). Построение множества состояний Рз!а!ее конечного автомата Р и его функции переходов Рггап в соответствии с этими идеями показано на рис. 3.32.
Изначально в Ржагее содержится только одно состояние, е-с1озиге (ео), и оно не помечено тгййе ( в Реги!ее имеется непомеченное состояние Т ) ( Пометить Т; аког ( каждый входной символ а ) ( У = е-с1озиге (гно~ е (Т, а)); Ы ( У ~ Рзгагез ) Добавить У в Рхги(ез как непомеченное состояние; Рггал (Т,а) = У„' Рнс.
3.32. Построение подмножества Стартовым состоянием Р является е-с!озиге (во), а принимакнцими состояниями Р являются те множества состояний Аг, которые включают как минимум одно принимающее состояние Аг. Для завершения описания построения подмножества требуется показать, как вычислить е-с1оеиге(Т) для произвольного множества состояний Т недетерминированного конечного автомата. Этот процесс показан на рис. 3.33 и представляет собой простой поиск в графе множества состояний. В данном случае представьте, что в графе имеются только ребра с метками е. и 208 Глава 3.
Лексический анализ Поместить все состояния Т в стек я!ас1г; Инициализировать е-с1озиге (Т) множеством Т; и Ьз!е ( з!ас/с не пуст ) ( Снять со стека я!ас!г верхний элемент 1; аког ( каждое состояние и с дугой из ! в и, помеченной е ) Ы ( и ф е-с1озиге (Т) ) ( Добавить и в а-с1озиге (Т); Поместить и в з!ас!с; Рис. 3.33. Вычисление е-с!озиге (Т) Пример 3.21. На рис. 3.34 показан еще один НКА, принимающий (а ~ Ь)* аЬЬ; это автомат, который позже будет построен непосредственно из регулярного выражения. Давайте применим алгоритм 3.20 к рис. 3.34.
Рис. 3.34. НКА Х для (а ~ Ь)' аЬЬ Стартовое состояние А эквивалентного ДКА — е-с1озиге (0), или А = (О, 1, 2, 4, 7), так как это именно те состояния, в которые можно перейти из состояния 0 по пути, у которого все ребра имеют метки е. Заметим, что путь может состоять из нуля дуг, так что состояние О достижимо само из себя по е-пути. Входной алфавит представляет собой (а, 6). Наш первый шаг состоит в том, чтобы пометить А и вычислить Р!гап[А, а'! = а-с1озиге(тоге(А, а)) н Р!гап(А, 6] = = е-с1озиге(моте(А, 6)).
Среди состояний О, 1, 2, 4 и 7 только 2 и 7 имеют переходы по а в состояния 3 и 8 соответственно. Таким образом, моте (А, а) = (3, 8). Далее, е-с1озиге ((3, 8)) = (1, 2, 3, 4, 6, 7, 8), так что мы можем найти Р!гап !А, а! = е-с!озиге (тоге(А,а)) = а-с1озиге((3,8)) = (1,2,3,4,6,7,8) 209 3.7. От регулярных выражений к автоматам Назовем это множество В, так что Р~гап )А, а] = В. Теперь мы должны вычислить Раап ~А, Ь).
Среди состояний А только 4 имеет переход по Ь, и это переход в состояние 5. Таким образом, Рй.ап ~А, Ь) = е-с1озиге Я 5) ) = 11, 2, 4, 5. 6, 7 ) Назовем это множество С, так что Ртгап [А, Ь) = С. Рис. 3.35. Таблица переходов Р~гал для ДКА 0 Если продолжить процесс с непомеченными состояниями В и С, в конечном счете мы достигнем точки, в которой все состояния ДКА будут помечены. Это заключение справедливо, потому что имеется "всего" 2" различных подмножеств множества из 11 состояний НКА.
Фактически мы построили пять различных состояний ДКА, которые соответствуют множеству состояний НКА. Соответствующая таблица переходов показана на рис. 3.35, а граф переходов Р— на рис. 3.36. Состояние А — начальное, а состояние Е, которое содержит состояние !0 НКА, является единственным принимающим состоянием ДКА Р. Рис. 3.36. Результат применения построения подмножеств к НКА нв рис.
3.34 Обратите внимание, что ДКА Р имеет на одно состояние больше, чем ДКА для того же языка на рис. 3.28. Состояния А и С имеют одну и ту же функцию 23О Глава 3. Лексический анализ переходов, так что их можно объединить. Минимизацию количества состояний ДКА мы рассмотрим в разделе 3.9.6.
и 3.7.2 Моделирование НКА Стратегия, использующаяся в ряде текстовых редакторов, заключается в построении НКА из регулярного выражения и его моделировании с использованием методики, сходной с построением подмножеств "на лету". Далее приведен набросок схемы такого моделирования.
Алгоритм 3.22. Моделирование НКА Вход: входная строка х с завершающим символом еой НКА Х с начальным состоянием вв, принимающими состояниями г и функцией переходов тоге. ВыхОд: ответ "да'*, если Х принимает х; ответ "нет" в противном случае. МЕТОД: алгоритм поддерживает множество текущих состояний й, которые достигаются из вв по пути, помеченному считанными символами входной строки. Если с — очередной входной символ, считанный функцией пех1Спаг (), то сначала вычисляется токе (й, с), а затем — замыкание с применением е-с1охиге (). Набросок алгоритма приведен на рис.
3.37. и !) Я = е-с)озиге(ао)' 2) с = пех~СйагО; 3) пйне(с!=еоГ) ( 4) Я = е-с1озиге(тоге(Б, с)); 5) с = пехтСйаг(); б) 7) и ( Я О г != О ) гетнгп "да"; 8) е!ае гегпгп "нет"; Рнс. 3.37. Моделирование НКА 3.7.3 Эффективность моделирования НКА При аккуратной реализации алгоритм 3.22 может быть достаточно эффективным. Поскольку используемые в нем идеи полезны для применения в ряде подобных алгоритмов, включая поиск в графах, мы детально рассмотрим эту реализацию. Нам требуются следующие структуры данных. 1.
Два стека, каждый из которых хранит множество состояний НКА. Один из стеков, оЫмагех, хранит "текущее" множество состояний, т.е. значение Я в правой части строки 4 на рис. 3.37. Второй стек, пенМа1ех, хранит 211 3.7. От регулярных выражений к автоматам "следующее" множество состояний — Я в левой части строки 4. Этот шаг не показан, но при переходе в цикле от строки 3 к строке 6 пеиМагев преобразуется в о1г1эгагев. 2. Булев массив а1геаг(уОл, проиндексированный состояниями НКА, для указания, какие именно состояния входят в леиМагев.
Хотя массив и стек хранят одну и ту же информацию, существенно быстрее опросить значение а1геайуОп [в[, чем выполнять поиск состояния в в стеке лен вегас)г. Оба представления поддерживаются только для повышения эффективности. 3. Двумерный массив гпоие [в, а[, хранящий таблицу переходов НКА. Записи этой таблицы, являющиеся множествами состояний, представлены связанными списками.
Для реализации строки 1 на рис. 3.37 нам надо установить все элементы массива а1геаЫуОл равными ГАЬЯЕ, затем для каждого состояния в в е-с1овиге (во) поместить в в оЫогагев и установить а1 еаг(уОп [в[ равным те11е. Реализация этой операции над состоянием в, а также реализация строки 4 облегчается при помощи вспомогательной функции аЫЯа1е (в). Эта функция вносит состояние в в пеи8ГаГев, устанавливает значение а1геаг(уОп [в[ равным ТЕ11Е и рекурсивно вызывает саму себя для состояний из гпоие [в, е[ для вычисления е-с1овиге (в). Чтобы избежать дублирования, функцию а~Ыогаге нельзя вызывать для состояния, которое уже находится в стеке леи эгагев.
Набросок этой функции приведен на рис. 3.38. 9) а~Ыогаге(в) ( 10) Внести в в пеиэгагев; 11) а1геаг(уОл[в[ = ТЛЕ; 12) 1ог (1 из гпоие[в,е[ ) 13) И' (!а1геаг(уОл(г) ) 14) асЫЯгаге(1); 15) Э Рнс. 3.38. Добавление нового состояния з, отсутствующего в пеиогагев Строка 4 на рис. 3.37 реализуется путем просмотра каждого состояния из о1еИагев.
Сначала мы находим множество состояний тоге [в, с[, где с — очередной входной символ, и к каждому из этих состояний, которое еще не входит в леиогагев, мы применяем функцию а~Ыогаге. Обратите внимание, что айБгаге вычисляет е-с1овиге и добавляет все найденные состояния в лен огагев, если они еще там не находятся. Набросок этих действий показан на рис. 3.39. Теперь предположим, что НКА Ю имеет п состояний и т переходов, т.е. т— сумма по всем состояниям количества символов (или е), для которых имеется 212 Глава 3. Лексический анализ 16) 1ог ( в Е оЫ5!агев ) 1 17) 1ог ( ! Е пкоге[в, с] ) 18) 1Г ( !а!геаауОп[г] ) 19) аййгаге(г); 20) Снять в со стека оИ5гакев; г!) ) 22) 1ог ( в Е пекгЯкагев ) 1 23) Снять в со стека пекг$ка!ев; 24) Поместить в в оЫЯагек; 25) а!геав!уОп[в] = ЕА1 ЯЕ; 26) ) Рис. 3.39.
Реализация шага 4 ва рис. 3.37 переход из данного состояния. Не учитывая вызов акЫо!а!е в строке 19 на рис. 3.39, мы находим, что время, затраченное на выполнение строк цикла 16-21, равно 0(п). Иными словами, мы можем выполнить цикл не более и раз, на каждой итерации выполняя постоянную работу, за исключением времени, затрачиваемого на вызов аИ8каш. То же самое можно сказать и о цикле в строках 22 — 26. При выполнении кода на рис. 3.39, т.е. шага 4 на рис. 3.37, вызов акЫ5!аге для каждо> о состояния возможен не более одного раза.
Причина этого в том, что, когда мы вызываем айИаге (в), в строке 11 на рис. 3.38 выполняется присваивание значения ТГк!7Е элементу массива а)геайуОп [в]. Это значение при проверках в строках 13 на рис. 3.38 и 18 на рис. 3.39 предотвращает повторные вызовы функции асЫ5гаке для одного и того же состояния. Время, затрачиваемое на один вызов аймаке, исключая рекурсивный вызов самой себя, равно 0 (1) для строк 10 и ! 1. Для строк 12 и 13 время зависит от количества с-переходов из состояния в.
Мы не знаем этого количества для данного состояния, но знаем, что общее количество переходов для всех состояний равно т, так что общее время, затраченное в строках !2 — 13 для всех вызовов акЫ5га!е в процессе одного выполнения кода на рис. 3.39, составляет О (т,). Общее время, затраченное на все остальные шаги агЫ8гаге, равно 0 (и), поскольку оно представляет собой константу для каждого вызова, а всего таких вызовов не больше и. Итак, можно сделать вывод, что при корректной реализации время, затрачиваемое на выполнение строки 4 на рис. 3.37, составляет О (и + т).
Остальные строки цикла кч)к1!е с 3 по 6 требуют 0 (1) времени на одну итерацию. Если входная строка х имеет длину )с, то общее время работы данного цикла — 0 (й (и + т)). Строка 1 на рнс. 3,37 может быть выполнена за время О (и+ из), поскольку она, 213 3.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
