А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 44
Текст из файла (страница 44)
Дополнительная стоимость перехода от регулярного выражения к ДКА, таким образом, по существу, представляет собой стоимость выполнения алгоритма 3.20 над НКА (можно непосредственно перейти от регулярного выражения к ДКА, но при этом, по сути, выполняется то же количество работы). Если обработка строк выполняется многократно, как в случае лексического анализа, то преобразование в ДКА стоит того.
Однако в других приложениях обработки строк, таких как дгер, в которых пользователь определяет одно регулярное выражение и один или несколько файлов, в которых выполняется поиск шаблона этого выражения, может оказаться более эффективным опустить построение ДКА и непосредственно моделировать работу НКА. Рассмотрим стоимость преобразования регулярного выражения г в НКА при помощи алгоритма 3.23. Ключевым шагом является построение дерева разбора для г.
В главе 4 приводится несколько методов построения этого дерева за линейное время, т.е. за время 0 (~г)), где )г) означает ризмер г — сумму количества операторов и операндов в г. Легко также убедиться, что все базовые и индуктивные построения алгоритма 3.23 требуют константного времени, так что общее время, необходимое для преобразования регулярного выражения в НКА, составяет 0(~г)). Кроме того, как мы выяснили в разделе 3.7.4, строящийся НКА имеет не более 2 (г~ ~состояний и не более 4 ~г~ переходов, те. в терминах анализа из раздела 3.7.3 п < ~г! и т < 2)г). Таким образом, моделирование этого НКА для входной строки ш потребует времени 0()г( х )х().
Это время является доминирующим по отношению ко времени построения НКА, 0(~г~), так что мы можем сделать вывод, что для данных регулярного выражения г и строки х можно выяснить, принадлежит ли т. языку Х,(т), за время 0((г( х (х~). 22О Глава 3. Лексический анализ Время, требующееся для построения подмножеств, сильно зависит от количества состояний в получающемся ДКА. Для начала заметим, что при построении подмножеств на рис. 3.32 ключевой шаг, построение множества состояний У на основе множества состояний Т и входного символа а, очень похож на построение нового множества состояний из старого множества при моделировании работы НКА в алгоритме 3.22.
Но мы уже выяснили, что при корректной реализации этот шаг требует времени, не более чем пропорционального количеству состояний и переходов в НКА. Предположим, что мы начинаем работу с регулярным выражением г и преобразуем его в НКА. Этот НКА имеет не более 2(г( состояний и не более 4 ~г( переходов. Кроме того, имеется не более ~г~ входных символов. Таким образом, для каждого создаваемого состояния ДКА мы должны построить не более ~г~ новых состояний, и каждое из них требует не более чем 0 ()г)+ 2 ~г)) времени.
Таким образом, время, необходимое для построения ДКА с я состояниями,— О(/з !~ а). В распространенном случае, когда а примерно равно ~г~, построение подмножеств занимает время 0(~г~з). Однако в наихудшем случае, как в примере 3.25, это время оказывается равным 0(~г~ 2~'~). На рис. 3.48 приведена информация г о разных вариантах построения распознавателя для выяснения принадлежности одной или нескольких строк к языку Ь (т).
АВТОМА НКА ДКА: типичный ДКА: наихудши Рис. 3.48. Стоимость начального построения и обработки одной строки различных методов распознавания языка регулярного выражения Если доминирует стоимость обработки одной строки, как в случае построения лексического анализатора, очевидно, что следует предпочесть ДКА. Однако в программах наподобие дгер, в которых автомат работает только с одной строкой, обычно предпочтительнее использовать НКА. Пока ~х~ не становится порядка ~г~~, нет смысла даже думать о преобразовании в ДКА. Существует, однако, составная стратегия, которая оказывается столь же хорошей, как наилучшая из стратегий НКА и ДКА для каждого регулярного выражения т и строки т.
Начнем с моделирования НКА„но по мере вычисления будем запоминать состояния НКА (пе., по сути, состояния ДКА) и их переходы. Перед обработкой текушего множества состояний НКА и сходного символа сначала проверим, не был ли уже вычислен соответствующий переход, и, если был вычислен, воспользуемся уже готовой информацией. 221 3.8.
Разработка генератора лексических анализаторов 3.7.6 Упражнения к разделу 3.7 Упражнение 3.7.1. Преобразуйте в ДКА НКА, приведенный на а) рис. 3.26; б) рис. 3.29; в) рис. 3.30. Упражнение 3.7.2. Воспользуйтесь алгоритмом 3.22 для моделирования НКА, приведенного на а) рис. 3.29; б) рис. 3.30, для входной строки ааЪЪ. Упражнение 3.7.3. Преобразуйте приведенные ниже регулярные выражения в де- терминированные конечные автоматы с использованием алгоритмов 3.23 и 3.20: а) (а!Ь); б) (а* / Ь*)*; в) Ис / а) Ь')*; г) (а / Ь)*аЬЬ (а ! Ь)*. 3.8 Разработка генератора лексических анализаторов В этом разделе мы применим представленные в разделе 3.7 методы для того, чтобы разобраться в архитектуре генераторов лексических анализаторов, таких как 1 ех. Мы рассмотрим два подхода, основанных на НКА и ДКА; последний из них, по сути, и является реализацией т.ех.
3.8.1 Структура генерируемого анализатора На рис. 3.49 приведена архитектура лексического анализатора, генерируемого 1,ех. Программа, служащая в качестве лексического анализатора, включает фиксированную программу, моделирующую автомат; пока что мы оставим открытым вопрос о том, какой именно автомат — детерминированный или недетерминированный — моделируется. Остальная часть лексического анализатора состоит из компонентов, которые создаются самим 7 ех из программы 1ех. Эти компоненты следующие. 222 Глава 3. Лексический анализ Входной буфер Программе Ьех Рнс. ЗА9.
Программа 1.ех превращается в таблицу переходов н действия, используемые имитатором конечного автомата 1. Таблица переходов автомата. 2. Функции, которые передаются непосредственно на выход генератора (см. раздел 3.5.2). 3. Действия из входной программы, которые представляют собой фрагменты кода, вызываемые имитатором автомата в соответствующие моменты времени. Построение автомата начнем с поочередного превращения регулярных выражений из программы 2,ех в недетерминированные конечные автоматы с использованием алгоритма 3.23. Нам нужен один автомат, который будет распознавать лексемы, соответствующие любому шаблону в программе, так что мы объединим все НКА в один, вводя новое начальное состояние с г-переходами в каждое из стартовых состояний НКА Ху для шаблона рр Эта конструкция показана на рис.
3.50. Пример 3.26. Проиллюстрируем эти идеи на следующем простом абстрактном примере: а ( действие А1 для шаблона р| 1 аЬЬ ( действие Аз для шаблона рз 1 а*Ь+ ( действие Аз для шаблона рз 1 Обратите внимание на наличие конфликтов„о которых мы говорили в разделе 3.5.3. В частности, строка аЬЬ соответствует как второму, так и третьему шаблону, но ее следует рассматривать как лексему для шаблона рз, поскольку этот 223 3.8. Разработка генератора лексических анализаторов Рнс.
3.50. НКА, построенный на основе программы 1.ех шаблон указан в приведенной программе тех первым. Далее, входные строки наподобие аабМ . имеют много префиксов, соответствующих третьему шаблону. Правило 1,ех гласит, что должен быть выбран самый длинный префикс, так что чтение 6 должно продолжаться до тех пор, пока не встретится а, после чего можно сообщить о том, что найдена лексема из начальных а, за которыми следуют б в обнаруженном количестве. На рис. 3.51 показаны три НКА, распознающие указанные трн шаблона. Третий представляет собой упрощенную версию автомата, полученного при применении алгоритма 3.23. На рис. 3.52 показан комбинированный НКА, полученный путем добавления начального состояния 0 и трех с-переходов. о 3.8.2 Распознавание шаблонов на основе НКА Если лексический анализатор моделирует НКА, такой как на рис.
3.52, то он начинает чтение входного потока с точки, которую мы обозначаем как 1ехетеВеВ1н. Прн перемещении указателя 1огниЫ по входному потоку при помощи алгоритма 3.22 выполняется вычисление множества состояний для каждой точки потока. В конечном счете моделирование НКА достигает точки входного потока, для которой нет следующего состояния. Очевидно, что в этот момент не приходится рассчитывать на то, что некоторый более длинный префикс приведет НКА в принимающее состояние; более того, множество состояний всегда будет пустым. Таким образом, в этот момент обнаружен наиболее длинный префикс, представляющий собой лексему, соответствуюшую некоторому шаблону.
224 Глава 3. Лексический анализ а ь 1'ис. 3.51. НКА для а, аЬЬ и а'Ь+ ь '© Рис. 3.52. Комбинированный НКА Далее выполняется откат но последовательности состояний, пока не будет найдено множество, которое включает одно или несколько принимающих состояний. Если в таком множестве имеется несколько принимающих состояний, выбирается то из них, которое связано с наиболее ранним шаблоном р, в списке программы ?ех. Указатель |огнам перемещается назад к концу лексемы и выполняется действие Ао связанное с шаблоном рь Пример 3.27. Предположим, что у нас есть шаблоны из примера 3.26 и входная строка, начинающаяся с ааЬа. На рис.
3.53 показаны множества состояний НКА, приведенного на рис. 3.52, в которые мы попадаем, начиная с е-с(озиге для 225 3.8. Разработка генератора лексических анализаторов а ь а Ц Е И Рис. 3.53. Последовательность множеств состояний при обработке входной строки ваЬа Таким образом, мы должны вернуться назад в поисках множества состояний, в которое входит принимающее состояние.
Заметим, что, как показано на рис. 3.53, после чтения а мы оказываемся в множестве состояний, которое включает состояние 2 и, следовательно, указывает на соответствие шаблону а. Однако после чтения ааЬ мы попадаем в состояние 8, указывающее на соответствие шаблону а*Ь~; префикс ааб — самый длинный префикс, приводящий нас в принимающее состояние. Таким образом, мы выбираем ааЬ в качестве лексемы и выполняем действие Аз, которое должно включать возврат синтаксическому анализатору указания о том, что найден токен, шаблон которого — рз = а"Ь+.
3.8.3 ДКА для лексических анализаторов Другая архитектура использует преобразование НКА для всех шаблонов в эквивалентный ДКА с использованием построения подмножеств по алгоритму 3.20. В каждом состоянии ДКА при наличии в нем одного или нескольких принимающих состояний НКА определяется первый шаблон программы 1ех, представленный принимающим состоянием, и этот шаблон является выходом данного состояния ДКА. Пример 3.28. На рис. 3.54 показана диаграмма переходов, основанная на разработанном при помощи метода построения подмножеств ДКА, соответствующем НКА на рис. 3.52. Принимающие состояния помечены шаблонами, идентифицируемыми этими состояниями. Например, состояние 16, 8) содержит два принимакнцих состояния, соответствующих шаблонам аЬЬ и а*Ь+. Поскольку шаблон аЬЬ указан в программе 3.ех первым, именно он является шаблоном, связанным с состоянием 16, 81.
П ДКА в лексическом анализаторе используется практически так же, как и НКА. Мы моделируем работу ДКА до тех пор, пока не окажемся в некоторой точке, начального состояния 0 (представляющего собой множество 10, 1, 3, 71), и через которые следуем при обработке указанной входной строки. После чтения четвер- того входного символа мы оказываемся в пустом множестве состояний, поскольку из состояния 8 на рис. 3.52 для входного символа и переходов нет. 226 Глава 3. Лексический анализ а'ь а'ь Рис. 3.54. Граф переходов для ДКА, обрабатывающего шаблоны а, аЬЬ и а'Ь у которой нет следующего состояния (или, строго говоря, у которой следуюшее состояние — йз, лзуликовое состояние (беар а1аге), соответствуюшее пустому множеству состояний НКА).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
