А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 41
Текст из файла (страница 41)
го1 3.6. Конечные автоматы Пример 3.14. На рис. 3.24 показан граф переходов НКА, распознающего язык регулярного выражения (а ~ Ь)* аЬЬ. Этот абстрактный язык, распознающий строки из а и Ь, заканчивающиеся подстрокой аЬЬ, будет использоваться в этом разделе и далее. Кстати, он похож на регулярные выражения, описывающие реальные языки, например на выражение, описывающее все файлы, имена которых заканчиваюгся на . с — апу*.с, где апу обозначает любой печатный символ. а иап ( Рнс. 3.24. Недетерминированный конечный автомат В соответствии с принятыми соглашениями для диаграмм переходов двойной крухюк вокруг состояния 3 указывает, что это — допускающее состояние.
Единственный способ попасть из состояния О в допускающее — проследовать по некоторому пути, который некоторое время остается в состоянии О, а затем проходит по состояниям 1, 2 и 3, считывая из входного потока символы аЬЬ. Таким образом, в допускающее состояние ведут только те строки, которые заканчиваются на аЬЬ.
и 3.6.2 Таблицы переходов НКА можно также представить в виде таблицы переходое (1гапа)боп 1аЫе), строки которой соответствуют состояниям, а столбцы — входным символам и е. Запись для некоторого состояния и входного символа представляет собой значение функции переходов для данных аргументов.
Если функция переходов не содержит информации о некоторой паре "состояние — входной символ", в таблице в этом месте помещается Я. Пример 3.15. На рис. 3.25 приведена таблица переходов для НКА, показанного на рис. 3.24. о 3.6.3 Принятие входной строки автоматом НКА допускает, или принимает (ассер1), входную строку х тогда и только тогда, когда в графе переходов существует некоторый путь от начального состояния к одному из допускающих, такой, что метки дуг вдоль этого пути соответствуют строке т.
Заметим, что метки е на этом пути игнорируются, поскольку не вносят никакого вклада в рассматриваемую строку. 2О2 Глава 3. Лексический анализ Рис. 3.25. Таблица переходов лля НКА, показанного на рис. 3.24 Пример 3.16. Строка ааЬЬ принимается НКА на рис. 3.24. Путь, помеченный как ааЬЬ, из состояния О в состояние 3 демонстрирует этот факт; а а ь ь 1 Заметим, что может быть несколько путей для одной и той же строки, приводящих в разные состояния.
Например, ь о й а представляет собой еще один путь из состояния О, помеченный строкой ааЬЬ. Этот путь приводит в состояние О, не являющееся допускающим. Вспомним, однако, что НКА принимает строку, если существует некоторый путь, помеченный этой строкой, из начального состояния в допускающее. Существование других путей, приводящих в непринимающие состояния, не имеет значения. о Пример 3.17. На рис. 3.26 показан НКА, принимающий Т, (аа* ) ЬЬ").
Строка ааа принимается этим автоматом в силу существования пути Е а И » 2 а 2 Обратите внимание, что е при конкатенация "исчезает", так что метка всего пути— ааа. П Язык, определяемый (или допускаемый) НКА, представляет собой множество строк, помечающих некоторые пути от стартового состояния до допускающего. Как уже упоминалось, НКА на рис. 3.24 определяет тот же язык, что и регулярное выражение (а ~ Ь)* аЬЬ, те. все строки из алфавита )а,Ь), заканчивающиеся на аЬЬ.
Для обозначения языка, принимаемого автоматом А, будем использовать обозначение Т,(А). 283 3.6. Конечные автоматы лап Рис. 3.26. НКА, принимающий аа' ~ ЬЬ* 3.6.4 Детерминированный конечный автомат Детерминированный конечный автомат (ДКА) представляет собой частный случай НКА, в котором а) нет переходов для входа г; б) для каждого состояния з и входного символа а имеется ровно одна дуга, выходящая из а и помеченная а.
Если воспользоваться для представления ДКА таблицей переходов, то каждая запись в ней будет являться единственным состоянием (так что его можно указывать без фигурных скобок, означающих множество). В то время как НКА — это абстрактное представление алгоритма для распознавания строк некоторого языка„ДКА является простым, конкретным алгоритмом распознавания строк.
К счастью, каждое регулярное выражение и каждый НКА могут быть преобразованы в ДКА, принимающий тот же язык. Мы говорим "к счастью", поскольку при построении лексического анализатора реализуется или моделируется именно детерминированный конечный автомат. Приведенный далее алгоритм показывает применение ДКА к строке. Алгоритм 3.18. Моделирование ДКА Вход: входная строка х, завершенная символом конца файла ео1, и детерминированный конечный автомат Р с начальным состоянием зо, принимающими состояниями г и функцией переходов тоге.
Выход: ответ "да", если Р принимает х, и "нет" в противном случае. Мвтод: применение алгоритма, приведенного на рис. 3.27, ко входной строке л. Функция тоге(а,с) дает состояние, в которое из состояния а ведет дуга при 204 Глава 3. Лексический анализ входном символе с. Функция лехгСЬаг возвращает очередной символ из входной строки х.
и в=во,' с = лехгСЬаг(); ч Ьйе ( с!= ео1' ) ( в = тоне(в,с); с = лех1СЬагО; Ы ( з Е Г ) гетпгп "да"; е!ае ге1пгп "нет"; Рнс. 3.27. Моделирование ДКА Пример 3.19. На рис. 3.28 показан граф ДКА, принимающий язык (а ~ Ь)* аЬЬ, тот же, что и в случае НКА на рис. 3.24. Для данной входной строки аЬаЬЬ этот ДКА проходит последовательность состояний О, 1, 2, 1, 2, 3 и возвращает "да". о Рнс. 3.28. ДКА, принимающий язык (а ~ Ь)* аЬЬ 3.6.5 Упражнения к разделу 3.6 Упражнение 3.6.1.
На рис. 3.19 приведен алгоритм вычисления функции отказа для алгоритма КМП. Покажите, как на базе данной функции отказа построить для ключевого слова 61 Ьз... Ь„ДКА с п + 1 состояниями для распознавания .*616з... 6„, где точка означает "произвольный символ". Кроме того, ДКА должен быть построен за время О (и). Упражнение 3.6.2. Разработайте конечные автоматы (детерминированные или не- детерминированные) для каждого из языков из упражнения 3.3.5. Упражнение 3.6.3.
Укажите все пути, помеченные как ааЬЬ, для НКА на рис. 3.29. Принимает ли этот НКА строку ааЬЬ? 205 3.7. От регулярных выражений к автоматам а,Ь а,Ь а,Ь Рис. 3.29. НКА к упражнению 3.6.3 Рис. 3.30. НКА к упражнению 3.6.4 Упражнение 3.6.4. Повторите упражнение 3.6.3 для НКА на рис. 3.30. Упражнение 3.6.5. Приведите таблицы переходов для НКА а) из упражнения 3.6.3; б) нз упражнения 3.6.4; в) на рис. 3.26.
3.7 От регулярных выражений к автоматам Регулярное выражение представляет собой способ описания лексических анализаторов и другого программного обеспечения для работы с шаблонами. Однако реализация этого программного обеспечения требует моделирования ДКА (см. алгоритм ЗПЗ) или, возможно, моделирования НКА.
Поскольку при работе с НКА часто приходится делать выбор перехода для входного символа (например, на рис. 3.24 в состоянии 0 для символа а) или для е (например, на рис. 3.26 в состоянии 0) либо даже выбор между переходом для реального входного символа или для г, его моделирование существенно сложнее, чем моделирование ДКА. Таким образом, оказывается очень важной задача конвертации НКА в ДКА, который принимает тот же язык. гоб Глава 3. Лексический анализ В этом разделе сначала будет показано, как конвертировать недетерминированные конечные автоматы в детерминированные.
Затем мы воспользуемся методикой под названием "построение подмножеств" для получения практичного алгоритма для непосредственного моделирования недетерминированных конечных автоматов в ситуациях (отличных от лексического анализа), когда преобразование НКА в ДКА требует больше времени, чем непосредственное моделирование.
Затем мы покажем, как преобразовывать регулярные выражения в недетерминированные конечные автоматы, из которых при желании могут быть построены детерминированные конечные автоматы. Завершится раздел обсуждением компромиссов между потреблением памяти и временем работы, присущих различным методам реализации регулярных выражений, и выяснением, как выбрать подходящий метод для конкретного приложения. 3.7.1 Преобразование НКА в ДКА Общая идея, лежащая в основе построения подмножеств, заключается в том, что каждое состояние строящегося ДКА соответствует множеству состояний НКА. После чтения входной строки а1аз...
а„ДКА находится в состоянии, соответствующем множеству состояний, которых может достичь из своего стартового состояния НКА по пути, помеченному а1аз... а„. Возможна ситуация, когда количество состояний ДКА экспоненциальио зависит от количества состояний НКА, что может привести к сложностям при реализации такого ДКА. Однако одно из преимуществ применения подхода к лексическому анализу на основе автоматов заключается в том, что для реальных языков НКА и ДКА имеют примерно одинаковое количество состояний, без экспоненциального поведения. Алгоритм 3.20. Построение подмножества (зцЬзе1 сопз1гисбоп) ДКА из НКА Вход: НКА Аг. Выход: ДКА Р, принимающий тот же язык, что и Х.
Мдтод: алгоритм строит таблицу переходов Рггал для Р. Каждое состояние Р представляет собой множество состояний НКА, н Рпжп строится таким образом, чтобы "параллельно" моделировать все возможные переходы, которые АГ может выполнить для данной входной строки. Наша первая проблема — в корректной обработке в-переходов Х. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
