А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 43
Текст из файла (страница 43)
От регулярных выражений к автоматам О-обозначения Выражение наподобие 0 (и) представляет собой сокращение для "не более чем некоторая константа, умноженная на и.". Технически мы говорим, что некоторая функция 7" (и) (вероятно, время работы некоторого алгоритма) представляет собой О (д (и)), если существуют константы г и ио, такие, что для всех и > ио выполняется соотношение ) (и) < гд (и).
Полезная идиома 0(1) означает "некоторая константа". Использование таких 0-обозначений позволяет не вдаваться в детальный подсчет времени выполнения, ограничиваясь указанием скорости роста времени выполнения алгоритма. по сути, представляет собой действия с рис. 3.39, ко~да а)атгагез содержит единственное состояние вс.
Строки 2, 7 и 8 требуют 0 (1) времени каждая. Таким образом, время выполнения корректно реализованного алгоритма 3.22 составляет 0 (к(и+ т)), т.е. пропорционально произведению длины входной строки на размер (количество узлов плюс количество дуг) графа переходов. 3.7.4 Построение НКА из регулярного выражения Приведем теперь алгоритм для преобразования произвольного регулярного выражения в НКА, определяющий тот же язык.
Этот алгоритм синтаксически управляемый, в том смысле, что он рекурсивно работает с деревом разбора регулярного выражения. Для каждого подвыражения алгоритм строит НКА с единственным принимающим состоянием. Алгоритм 3.23. Алгоритм Мак-Нотона — Ямалы-Томпсона (МсХацйп1оп-УашадаТЬотраоп) для преобразования регулярною выражения в НКА ВхОд: регулярное выражение г над алфавитом Е.
Выход: НКА Х, принимающий Т, (г). Мвтод: начнем с разбора г на составляющие подвыражения. Правила построения НКА состоят из базисных правил для обработки подвыражений без операторов и индуктивных правил для построения ббльших НКА из НКА для непосредственных подвыражений данного выражения. БАЗйС: для выражения е строим НКА. Здесь г — новое состояние, представляющее собой начальное состояние НКА, а г — другое новое состояние, являющееся принимающим состоянием НКА.
214 Глава 3. Лексический анализ Для любого подвыражения а из Е строим НКА Здесь также г и 1 — новые состояния, являющиеся соответственно начальным и принимающим. Обратите внимание, что в обоих базовых случаях мы строим отдельные НКА с новыми состояниями для каждого е и некоторого а, являющихся подвыражением г. Индукция: предположим, что Ж (а) и Ю (г) — недетерминированные конечные автоматы для регулярных выражений а и 1 соответственно. а) Пусть г = а ~ 1. Тогда Ю (г), НКА для г, строится так, как показано на рис. 3.40. Здесь г и г" — новые состояния, являющиеся соответственно начальным и принимающим состояниями Ж (г). Имеются также г-переходы от 1 к стартовым состояниям АГ (а) и Аг ф и е-переходы от каждого из их принимающих состояний в г".
Обратите внимание, что принимающие состояния Ж (а) и Х (г) не являются таковыми в Ж (г). Поскольку любой путь из 1 в г" должен пройти либо исключительно по Х (а), либо исключительно по Ю (1) и поскольку метки пути не изменяются при добавлении к ним г при выходе из ~ и входе в Г", можно заключить, что Ю (г) принимает язык Ь (а) О Ь (т), который представляет собой не что иное, как язык Т, (г). Таким образом, на рис. 3.40 представлено корректное построение НКА для оператора объединения.
Рис. 3.40. НКА лля объединения двух регулярных выражений б) Пусть г = М. В этом случае построим М (г) так, как показано на рис. 3.41. Начальное состояние % (а) становится начальным состоянием Х (г), а принимающее состояние Ж(1) — единственным принимающим состоянием Х (г). Принимающее состояние М (а) и начальное состояние Ю (г) объединяются в одно состояние со всеми входящими и исходящими переходами обоих состояний. Путь от г к г на рис.
3,41 должен сначала пройти через Х 1а), так что его метка начинается с некоторой строки из Т, 1'а). Затем путь 215 3.7. От регулярных выражений к автоматам проходит через Ж (!), так что его метка заканчивается строкой из Ь (г). Как будет показано, принимающие состояния не имеют исходяших дуг, а начальные состояния — входящих, так что после того, как путь покинул Х (в), он не может вновь войти в него.
Таким образом, % (г) принимает исключительно строки из Т, (в) Х, (!) и является корректным НКА для г = в!. ва Рис. 3.4!. НКА для конкатенации двух регулярных выражений в) Пусть г = в*. Тогда для г НКА Х (г) строится так, как показано на рис. 3.42. Здесь ! и ! — новые начальное и принимаюшее состояния Л (г). Для достижения ! из г необходимо либо пройти по пути с меткой е, соответствующему строке Т (в), либо перейти к начальному состоянию М (в), пройти по этому НКА и вернуться из его принимающего состояния в начальное нуль или несколько раз.
Эта возможность позволяет Ж (г) принимать все строки Л (в), Ь (в) и так далее, так что полное множество строк, принимаемое 1 2 Ж (г), представляет собой Ь (в*). Рис. 3.42. НКА для замыкания регулярного выражения г) Наконец, пусть г —. (в). Тогда Е (г) — 2, (в) и можно использовать НКА Аг(в) как Х(г). а Описание алгоритма 3.23 содержит указания о том, почему корректны индуктивные построения. Мы не даем формального доказательства их корректности, но перечислим некоторые свойства построенных НКА в дополнение к тому главному факту, что Х (г) принимает язык Е (г). Эти свойства интересны как сами по себе, так и с точки зрения использования в формальном доказательстве.
!. Количество состояний в Х (г) не более чем в два раза превышает количество операторов и операндов в г. Эта граница следует из того факта, что каждый шаг алгоритма создает не более двух новых узлов. 217 3.7. От регулярных выражений к автоматам Рис. 3.44. НКА лля гз Рис. 3.45. НКА для гв НКА для г4 = (гз) имеет тот же вид, что и для гз. Конечный автомат для гз =- (гз)* приведен на рис. 3.45. Для его получения из НКА на рис. 3.44 было использовано построение, показанное иа рис.
3.42. Рассмотрим теперь подвыражение ге, представляющее собой а. Для него мы опять воспользуемся базисным построением, но с новыми состояниями. Мы не можем повторно использовать НКА для гы несмотря на то, что г~ и ге представляют собой одно и то же выражение. НКА для ге имеет следующий вид: Для получения НКА для гт = гага мы применяем построение, показанное на рис.
3.41. Мы объединяем состояния 7 и 7', что дает НКА, показанный на рис. 3.46. Продолжая работу с новым НКА для двух подвыражений Ь вЂ” гв и г~е, — в конечном счете мы построим НКА для регулярного выражения (а ~ Ь)* аЬЬ, с которым уже встречались на рис. 3.34. о 218 Глава 3.
Лексический анализ Рнс. 3.46. НКА для гт 3.7.5 Эффективность алгоритма обработки строк Мы уже знаем, что алгоритм 3.18 обрабатывает строку х за время 0(1х~), а в разделе 3.7.3 мы выяснили, что можно смоделировать работу НКА за время, пропорциональное произведению ~х~ на размер графа переходов НКА. Очевидно, что моделирование работы ДКА выполняется быстрее, чем НКА, так что у вас может возникнуть вопрос — какой вообще смысл в моделировании НКА? Одна из причин в том, что построение подмножеств для НКА в наихудшем случае может вызвать экспоненциальный рост количества состояний. Хотя, в принципе, количество состояний ДКА не влияет на время работы алгоритма 3.18, оно может оказаться столь велико, что не будет помещаться в основной памяти, а это приведет к необходимости дисковых операций и существенному снижению эффективности. Пример 3.28.
Рассмотрим семейство языков, описываемое регулярными выражениями вида 2„= (а ~ Ь)* а (а ~ Ь)", те. каждый язык т,„состоит из строк из а и 6, таких, что п-й символ, считая от правого конца строки, равен а. Легко построить НКА с и + 1 состояниями. Конечный автомат может при любых входных символах как находиться в начальном состоянии, так и при входном символе а переходить в состояние 1. Из состояния 1 при любом входном символе НКА переходит в состояние 2, и так далее, пока не будет достигнуто состояние п.
Данный НКА показан на рис. 3.47. Однако любой ДКА для языка Х„должен иметь как минимум 2" состояний. Мы не будем доказывать этот факт, но основная идея заключается в том, что любой ДКА для этого выражения должен отслеживать как минимум п символов входного потока; в противном случае может быть получен неверный ответ. Ясно, что для отслеживания всех возможных последовательностей из и символов а и 6 требуется по крайней мере 2" состояний.
К счастью, как уже упоминалось, такого 219 3.7. От регулярных выражений к автоматам Рис. 3.47. НКА, имеющий существенно меньшее количество состояний, чем наименьший эквивалентный ДКА рода выражения встречаются в приложениях лексического анализа не так часто, так что вряд ли вам придется на практике встретиться с таким ДКА с огромным количеством состояний. и Однако генераторы лексических анализаторов и другие системы обработки строк часто начинают работу с регулярного выражения. Мы оказываемся перед выбором — преобразовывать регулярные выражения в ДКА или в НКА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
