А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 45
Текст из файла (страница 45)
Из этой точки мы должны выполнить откат по пройденной последовательности состояний и, как только при откате будет встречено принимающее состояние ДКА, выполняется действие, соответствуюшее шаблону этого состояния. Пример 3.29. Предположим, что ДКА на рис. 3.54 передана входная строка абба. В этом случае последовательность состояний ДКА, через которую мы проходим, — 0137, 247, 58, 68 и для последнего а во входной строке из состояния 68 перехода нет.
Теперь мы рассматриваем полученную последовательность от конца к началу и обнаруживаем, что первым принимающим состоянием является 68, соответствуюшее шаблону рз = аЬЬ. а 3.8.4 Реализация прогностического оператора Вспомним, что в разделе 3.5.4 мы столкнулись с тем, что иногда в шаблоне 1ех гз/гз необходимо использовать прогностический оператор /, поскольку для корректной идентификации лексемы шаблону гз некоторого токена может требоваться дополнительный контекст гз.
При преобразовании гз/гз в НКА мы рассматриваем /, как если бы это было е, так что в действительности мы не ишем / во входной строке. Однако, если НКА распознает префикс ху во входном буфере как соответствующий данному регулярному выражению, конец лексемы находится не там, где НКА входит в принимающее состояние. Конец лексемы находится в состоянии и, таком, что 1) и имеет с-переход для (воображаемого) символа /; 227 3.8. Разработка генератора лексических анализаторов Тупиковые состояния в ДКА Технически автомат на рис. 3.54 — не совсем ДКА. Причина этого в том, что ДКА имеет переход из каждого состояния для каждого входного символа алфавита. Здесь же мы опустили переходы в тупиковое состояние и и, соответственно, переходы из тупикового состояния в него же для любого входного символа. Предыдущие примеры преобразования НКА в ДКА не имели путей из начального состояния в о, однако в случае НКА на рис.
3.52 такой путь имеется. Однако при построении ДКА для использования в лексическом анализаторе очень важно рассматривать тупиковое состояние отдельно, поскольку мы должны знать, когда все возможности распознавания более длинной лексемы исчерпаны. Таким образом, мы предлагаем всегда как опускать переходы в тупиковое состояние, так и удалять само тупиковое состояние.
В действительности проблема сложнее, чем кажется, поскольку построение ДКА из НКА может привести к нескольким состояниям, из которых невозможно достичь ни одного принимающего состояния, и мы должны знать, когда при моделировании окажется достигнуто одно из этих состояний. В разделе 3.9.6 рассматривается обьединение всех таких состояний в одно тупиковое, так что их идентификация становится очень простой.
Интересно также заметить, что при построении ДКА из регулярного выражения с использованием алгоритмов 3.20 и 3.23 получающийся автомат не имеет ни одного состояния, кроме О, из которого нельзя попасть в принимающее состояние. 2) существует путь из начального состояния НКА в состояние а, который соответствует строке т; 3) существует путь из состояния я в принимающее состояние, который соответствует строке у; 4) строка х имеет наибольшую длину среди всех возможных ху, удовлетворяющих условиям 1 — 3. Если в НКА имеется ровно одно состояние с е-переходом для воображаемого /, то конец лексемы, как проиллюстрировано в следующем примере, определяется последним входом в это состояние.
Если в НКА больше одного состояния с епереходом для воображаемого /, то поиск корректного состояния а существенно усложняется. Пример 3.30. На рис. 3.55 показан НКА для шаблона с прогностическим оператором, соответствующего 1Г в языке программирования РогГгап из примера 3.13. 228 Глава 3. Лексический анализ Обратите внимание, что е-переход из состояния 2 в состояние 3 представляет прогностический оператор.
Состояние 6 указывает наличие ключевого слова 1Р. Однако сама лексема 1Р определяется обратным сканированием от состояния 6 к последнему вхождению в состояние 2. о ппу мп г е (г'1 г ( ) 1 !евег г~~ О ! 2 3 — 4 5 ~6) Рис. 3.55. НКА, распознающий ключевое слово 1Е 3.8.5 Упражнения к разделу 3.8 Упражнение 3.8.1. Предположим, имеется два токена: 1) ключевое слово хй и 2) идентификаторы, которые представляют собой строки из букв, отличные от ай.
Постройте для этих токенов а) НКА; б) ДКА. Упражнение 3.8.2. Повторите упражнение 3.8.1 для токенов, представляющих собой 1) ключевое слово пгЬх2е, 2) ключевое слово иЬеп и 3) идентификаторы, представляющие собой строки из букв и цифр, начинающиеся с буквы. ! Упражнение 3.8.3. Предположим, мы изменили определение ДКА так, что из каждого состояния для каждого входного символа может быть нуль или один переход (в отличие от ровно одного перехода в стандартном определении ДКА). В этом случае некоторые регулярные выражения будут иметь меньшие по размеру "ДКК', чем при стандартном определении. Приведите пример такого регулярного выражения.
!! Упражнение 3.8.4. Разработайте алгоритм для распознавания шаблонов с прогностическим оператором вида гг /гз, где гг и гз представляют собой регулярные выражения. Покажите, как ваш алгоритм работает со следующими шаблонами: а) 1аЬсй ~ аЬс)/д; б) 1а ~ аЬ)/Ьа; в) аа'/а*. 3.9. Оптимизация распознавателей иа основе ДКА 3.9 Оптимизация распознавателей на основе ДКА В зтом разделе будут представлены три алгоритма, использующиеся для реализации и оптимизации построенных на основе регулярных выражений распознавателей шаблонов.
1. Первый алгоритм используется в компиляторе Ьех, поскольку он строит ДКА непосредственно из регулярного выражения, без создания промежуточного НКА. Получающийся в результате ДКА имеет меньшее количество состояний, чем ДКА, строящийся на основании НКА. 2. Второй алгоритм минимизирует количество состояний любого ДКА путем объединения состояний, которые имеют одно и то же поведение.
Этот алгоритм сам по себе достаточно эффективен; время его работы — О (и 1ок п), где и — количество состояний ДКА. 3. Третий алгоритм дает более компактное представление таблиц переходов по сравнению со стандартной двумерной таблицей. 3.9.1 Важные состояния НКА Перед тем как приступить к рассмотрению непосредственного перехода от регулярных выражений к ДКА, сначала следует исследовать построение НКА при помощи алгоритма 3.23 и рассмотреть роли, которые играют различные состояния автоматов. Будем называть состояние НКА важным, если оно имеет исходящий не-е-переход. Заметим, что в процессе построения подмножеств (алгоритм 3.20) используются только важные состояния в множестве Т при вычислении г-с!озиге (то~е (Т, а)), множества состояний, достижимых из Т при входном символе а.
Таким образом, множество состояний тоге(а,а) непустое, только если состояние з — важное. В процессе построения подмножеств два множества состояний НКА могут отождествляться, т.е. рассматриваться как единое множество, если они 1) имеют одни и те же важные состояния; 2) либо оба содержат принимающие сосгояния, либо оба их не содержат. При построении НКА из регулярных выражений при помощи алгоритма 3.23 единственными важными состояниями являются те, которые созданы базисом алгоритма в качестве начальных для конкретных символов в регулярных выражениях; т.е.
каждое важное состояние соответствует некоторому операнду в регулярном выражении. 23О Глава 3. Лексический анализ Построенный НКА имеет только одно принимающее состояние, но это состояние, у которого нет исходящих переходов, важным не является. Добавляя к регулярному выражению г справа уникальный ограничитель №г, мы даем принимающему состоянию для г переход по символу №, делая зто состояние важным в НКА для (г) з!~. Другими словами, используя расширенное (ацбтеп!ед) регулярное выражение (г) ф, можно забыть о принимающих состояниях при построении подмножеств; когда построение будет завершено, любое состояние с переходом по символу № должно быть принимающим.
Важные состояния НКА соответствуют позициям в регулярном выражении, в которых хранятся символы алфавита. Как мы увидим, это удобно для представления регулярного выражения его синтаксическим деревам, в котором листья соответствуют операндам, а внутренние узлы — операторам. Внутренний узел называется сат-узлом, ог-узлом или лтаг-узлом, если он помечен соответственно оператором юнкатенации (.), объединения (!) или звездочкой (*). Синтаксическое дерево для регулярного выражения может быть построено так же, как для арифметического выражения в разделе 2.5Л.
Пример 3.31. На рис. 3.56 показано синтаксичесюе дерево для регулярного выражения для нашего текущего примера регулярного выражения. Саьузлы представлены кружками. !з Г~ 6 5 4 з Г~ ! г Рнс. 3.56. Синтаксическое дерево для (а ! Ь)' аЬЬ4 Листья синтаксического дерева помечаются символом е или символами алфавита.
Каждому листу, не помеченному с, приписывается целое значение, уникаль- Зтот символ уникален в том смысле, что лс встречается во входном потоке. — Прим. ряд. 231 3.9. Оптимизация распознавателей на основе ДКА ное в пределах дерева. Оно используется, как позиция листа, а также как позиция его символа. Заметим, что символ может иметь несколько позиций; например, на рис. 3.56 а имеет позиции 1 и 3. Позиции в синтаксическом дереве соответствуют важным состояниям построенного НКА.
Пример 3.32. На рис. 3.57 показан НКА для того же регулярного выражения, что и на рис. 3.56. Важные состояния пронумерованы, остальные представлены буквами. Пронумерованные состояния в НКА и позиции в синтаксическом дереве связаны друг с другом способом, который будет рассмотрен ниже. и Рнс.
3.57. НКА, построенный алгоритмом 3.23 для (а ~ Ь)* аЬЬ| 3.9.2 Функции, вычисляемые на синтаксическом дереве Для построения ДКА непосредственно из регулярного выражения мы строим его синтаксическое дерево, а затем вычисляем четыре функции ниПаЫе, бгз~роз, 1нюроз и 1оПонроз, определяемые следующим образом (каждое определение использует синтаксическое дерево для расширенного регулярного выражения (г) ф).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
