А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 47
Текст из файла (страница 47)
3.62. Построение ДКА непосредственно нз регулярною выражения Пример 3.37. Соберем воедино все ранее рассмотренные примеры и построим ДКА для регулярного выражения г = (а ] Ь)* аЬЬ. Синтаксическое дерево для (г) тг показано на рнс. 3.56. Мы уже знаем, что функция пи!!аЬ!е имеет значение тгие только в в!аг-узле. Функции Ига!роз и !аз!рок показаны на рис.
3.59, а значения !ЬИонроя — на рис. 3.60. Значение функции2згя1роз в корне равно (1, 2, 3), так что это множество является начальным состоянием Р. Обозначим это множество через А. Мы должны вычислить Р1гап [А, а] и Рггап [А, Ь]. Среди позиций А символу а соответствуют позиции 1 н 3, символу Ь вЂ” позиция 2. Таким образом, Р1гап [А, а] = !ЬИонроз(1)О !.! 7оИозгроз(3) = (1,2,3,4), а Рггап [А,Ь] = ГоИонроз(2) = (1,2,3).
Последнее состояние представляет собой состояние А, так что его не надо добавлять в Рз1агез, но состояние В = (1, 2, 3, 4) является новым, так что мы добавляем его в Ря1агез и вычисляем его переходы. Полностью ДКА показан на рис. 3.63. д 237 3тк Оптимизация распознавателей на основе ДКА Рис. 3.63. ДКА для регулярного выражения г = (а ! Ь)" аЬЬ 3.9.6 Минимизация количества состояний ДКА Один и тот же язык могут распознавать разные ДКА. Например, оба автомата, показанные на рнс.
3.36 и 3.63, распознают язык В ((а ~ Ь)* аЬЬ). Такие автоматы могут иметь не только состояния с разными именами, но и разное количество состояний. При реализации лексического анализатора при помощи ДКА в общем случае предпочтительно иметь конечный автомат с минимально возможным количеством состояний, поскольку каждое состояние требует наличия записей в таблице, описывающей лексический анализатор. Имена состояний значения не имеют.
Мы будем говорить, что два автомата одинаковы с точностью до имен состояний, если один из них может быть получен из другого простым переименованием состояний. Однако существует тесная взаимосвязь между состояниями каждого из автоматов. Состояния А и С на рис. 3.36 в действительности эквивалентны, в том смысле что ни одно из них не является принимающим, и любой входной символ приводит к одинаковым переходам— в состояние В для входного символа а и в состояние С для входного символа 6.
Кроме тою, и состояние А, и состояние С ведут себя так же, как и состояние 123 на рис. 3.63. Аналогично состояние В на рис. 3.36 ведет себя так же, как состояние ! 234 на рис. 3.63, состояние Р— как состояние 1235, а состояние Е— как 1236. Оказывается, для любого регулярного языка всегда существует единственный (с точностьк1 до имен состояний) ДКА с минимальным количеством состояний.
более того, этот ДКА с минимальным количеством состояний может быть построен из любо~о ДКА для того же самого языка путем объединения множеств эквивалентных состояний. В случае языка В((а ~ Ь)*аЬЬ) ДКА с минимальным количеством состояний представлен на рис. 3.63, и он может быть получен из ДКА на рис. 3.36 путем группирования состояний следующим образом: (А, С) (В) (Р) (Е). Чтобы понять, как работает алгоритм преобразования ДКА в эквивалентный ДКА с минимальным количеством состояний, нам надо рассмотреть, как входные строки отличают одно состояние от другого. Мы говорим, что строка х отличает (Йзг(пяц(зй) состояние в от состояния 1, если ровно одно из состояний, дости- 238 Глава 3.
Лексический анализ жимых из в и г по пути с меткой х, является принимающим, а другое — нет. Состояние з отличимо от состояния 1, если существует некоторая строка, которая отличает их. Пример 3.38. Пустая строка отличает любое принимающее состояние от непринимающего. На рис. 3.36 строка ЬЬ отличает состояние А от состояния В, поскольку ЬЬ приводит из А в непринимающее состояние С, а из  — в принимающее состояние Е. а Алгоритм, минимизирующий количество состояний, работает путем разбиения состояний ДКА на группы неотличимых состояний. Каждая группа состояний затем объединяется в одно состояние ДКА с минимальным количеством состояний. Алгоритм работает с разбиением, группы которого представляют собой множества состояний, отличие которых друг от друга пока что не установлено.
Если никакая группа разбиения не может быть разделена на меньшие группы, мы получаем ДКА с минимальным количеством состояний. Изначально разбиение состоит из двух групп: принимающие состояния и не- принимающие. Основной шаг состоит в том, чтобы взять некоторую группу состояний, скажем, А = (вы вз,..., зь1, и некоторый входной символ а и посмотреть, может ли а использоваться для отличия некоторых состояний в группе А. Мы рассматриваем переходы из каждого из состояний вы аз,..., яь для данного входного символа а, и если состояния переходят в две или более групп текущего разбиения, то А разделяется на набор групп таким образом, чтобы гч и а оказывались в одной группе тогда и только тогда, когда они переходят в одну и ту же группу при данном входном символе а.
Этот процесс повторяется до тех пор, пока не окажется ни одной группы, которая могла бы быть разделена некоторым входным символом. Эга идея формализована в следующем алгоритме. Алгоритм 3.39. Минимизация количества состояний ДКА Вход: ДКА Р с множеством состояний Я, входным алфавитом Е, начальным состоянием ав и множеством принимающих состояний Ь'. Выход: ДКА Р', принимающий тот же язык, что и Р, и имеющий наименьшее возможное количество состояний. Мцтод: 1.
Начинаем с разбиения П на две группы, Г и Я вЂ” Г, состоящие из принимающих и не принимающих состояний Р. 2. Применяем процедуру, приведенную на рис. 3.64, для построения нового разбиения Ппею. 3. Если П„,„= П, принимаем Пя ~ = П и переходим к шагу 4. В противном случае переходим к шагу 2, заменяя П на П„,„.
239 3ть Оптимизация распознавателей на основе ДКА Изначально П„= П; аког ( каждая группа С из П ) ( Разбиваем С на подгруппы, такие, что два состояния, е и г, находятся в одной подгруппе тогда и только тогда, когда для всех входных символов а состояния в и 1 имеют переходы по этому символу в состояния, принадлежащие одной и той же группе разбиения П; /* В худшем случае подгруппа состоит из одного состояния *! Заменяем С в П„,„множеством образованных подгрупп; Рнс. 3.64.
Построение П„,„ 4. Выбираем одно из состояний из каждой группы Пввм в качестве представителя этой группы. Представители будут состояниями ДКА с минимальным количеством состояний Р'. Остальные компоненты Р' строятся следующим образом. а) Начальным состоянием Р' является представитель группы, содержащей стартовое состояние Р. б) Принимающими состояниями Р' являются принимающие состояния групп, содержащих принимающие состояния Р. Заметим, что каждая группа содержит либо только принимающие состояния, либо только не принимающие, поскольку мы начинаем работу с отделения этих классов состояний друг от друга, а процедура на рис.
3.64 всегда образует новые группы, которые являются подгруппами ранее построенных. в) Пусть е — представитель некоторой группы С в Пням и пусть переход для входного символа а в автомате Р ведет из состояния в в состояние 1. Пусть г — представитель группы Н, в которую входит г. Тогда в Р' имеется переход из в в г для входного символа а. Заметим, что в Р каждое состояние из группы С должно перейти при входном символе а в некоторое состояние из группы Н, поскольку иначе группа С должна была бы быть разделена процедурой на рис. 3.64.
и Пример 3.40. Обратимся еще раз к ДКА на рис. 3.36. Начальное разбиение состоит из двух групп, (А, В, С, Р) (Е), состоящих соответственно из не принимающих и принимающего состояний. Для построения П„,„процедура на рис. 3.64 рассматривает обе группы и входные символы а и 6. Группа (Е) не может быть разделена, поскольку она состоит из одного состояния, так что в П„,„она остается неизменной. 240 Глава 3.
Лексический анализ Почему работает алгоритм минимизации количества состояний Нам требуется доказать две вещи: что состояния, остающиеся в одной и той же группе Па 1, не отличимы никакой строкой, и что состояния, оказавшиеся в разных группах, отличимы. Первое следует из доказательства по индукции по г того факта, что если после г-й итерации шага 2 алгоритма 3.39 з и С находятся в одной и той же группе, то не существует строки длиной не более ~, которая могла бы отличить их друг от друга. Детальное доказательство остается читателю в качестве упражнения.
Второе следует из доказательства по индукции по г того факта, что если состояния а и С помещаются в разные группы на г-й итерации шага 2, то существует строка, отличающая их. Базис индукции доказывается просто: если при начальном разделении а и 1 принадлежат разным группам, то одно из них является принимающим, а другое нет; как известно, пустая строка е отличает такие состояния друг от друга.
Далее, раз состояния в и С помещаются в разные группы, должен существовать символ а и состояния р и д, такие, что в и С при входном символе а переходят соответственно в состояния р и д, причем р и д должны к этой итерации находиться в разных группах. Тогда, в соответствии с гипотезой индукции, существует некоторая строка х, которая отличает р от д. Следовательно, строка ах отличает з от ~. Устранение тупикового состояния Алгоритм минимизации количества состояний иногда приводит к ДКА с одним тупиковым состоянием — состоянием, не являющимся принимающим и для каждого входного символа переходящим само в себе. Такое состояние технически необходимо, поскольку ДКА по определению должен иметь переходы из каждого состояния для каждого входного символа.
Однако, как говорилось в разделе 3.8.3, нам зачастую требуется знать, когда все возможности достичь принимающего состояния исчерпаны, чтобы определить, что корректная лексема уже была найдена. Таким образом, мы можем захотеть устранить тупиковое состояние и использовать автомат, в котором отсутствуют некоторые переходы. Такой автомат имеет на одно состояние меньше, чем ДКА с минимальным количеством состояний, но, строго говоря, он не является детерминированным конечным автоматом из-за отсутствия переходов в тупиковое состояние.
241 Зтх Оптимизация распознавателей на основе ДКЛ Группа (А, В, С, Р) может быть разделена, так что мы должны рассмотреть воздействие на нее каждого входного символа. Прн входном символе а все состояния группы переходят в состояние В, так что отличить эти состояния при помощи строки, начинающейся с а, невозможно.
При входном символе б состояния А, В и С переходят в состояния, являющиеся членами группы (А, В, С, Р), в то время как состояние Р переходит в Š— член другой группы. Таким образом, в П„, группа (А, В, С, Р) разбивается на (А, В, С) (Р), и П„,„на этой итерации представляет собой (А, В, С) (Р) (Е). На следующей итерации мы можем разбить (А, В,С) на (А,С) (В), поскольку и А, и С переходят при входном символе Ь в состояния, являющиеся членами группы (А, В, С), в то время как состояние В для этого входного символа переходит в состояние из другой группы — (Р).
Итак, после второй итерации П„,„= (А, С) (В) (Р) (Е). На третьей итерации мы не можем разделить единственную оставшуюся группу с более чем одним состоянием, поскольку и А, и С переходят в одно н то же состояние (а следовательно, в одну и ту же группу) при любом входном символе. Таким образом, мы делаем вывод, что Па„м = = (А, С) (В) (Р) (Е). Теперь мы должны построить ДКА с минимальным количеством состояний. Он имеет четыре состояния, соответствующие четырем группам Па„м, и в качестве представителей мы выбираем А, В, Р и Е. Начальным является состояние А, а единственным принимающим — состояние Е. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
