В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 6

3.9:HI3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ31Здесь i – новое начальное состояние, а f – новое заключительное состояние.3.3.2Построение детерминированного конечногоавтомата по недетерминированномуРассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тотже язык.Алгоритм 3.2.

Построение детерминированного конечного автоматапо недетерминированному.Вход. НКА M = (Q, T, D, q0 , F ).Выход. ДКА M 0 = (Q0 , T, D0 , q00 , F 0 ), такой что L(M ) = L(M 0 ).Метод. Каждое состояние результирующего ДКА – это некотороемножество состояний исходного НКА.В алгоритме будут использоваться следующие функции:e-closure(R) (R ⊆ Q) – множество состояний НКА, достижимых изсостояний, входящих в R, посредством только переходов по e, т.е. множество[S={p|(q, e) `∗ (p, e)}q∈Rmove(R, a) (R ⊆ Q) – множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество[S={p|p ∈ D(q, a)}q∈RВначале Q0 и D0 пусты.

Выполнить шаги 1-4:(1) Определить q00 = e-closure({q0 }).(2) Добавить q00 в Q0 как непомеченное состояние.(3) Выполнить следующую процедуру:while (в Q0 есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T ){S = e-closure(move(R, a));if (S 6= ∅){if (S ∈/ Q0 )добавить S в Q0 как непомеченное состояние;определить D0 (R, a) = S;ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ32}}}(4) Определить F 0 = {S|S ∈ Q0 , S ∩ F 6= ∅}.Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.10.HHDHHEHHHDD$E%D&HDEDEDEE'E(EРис. 3.10:3.3.3Построение детерминированного конечногоавтомата по регулярному выражениюПриведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тот же язык [10].Пусть дано регулярное выражение r в алфавите T . К регулярномувыражению r добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным.

В процессе своей работы алгоритмбудет использовать пополненное регулярное выражение.3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ33Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (r)# , каждый лист которого помеченсимволом a ∈ T ∪{e, #}, а каждая внутренняя вершина помечена знакомодной из операций: · (конкатенация), | (объединение), ∗ (итерация).Каждому листу дерева (кроме e-листьев) припишем уникальный номер, называемый позицией, и будем использовать его, с одной стороны,для ссылки на лист в дереве, и, с другой стороны, для ссылки на символ,соответствующий этому листу. Заметим, что если некоторый символ используется в регулярном выражении несколько раз, он имеет несколькопозиций.Теперь, обходя дерево T снизу-вверх слева-направо, вычислим четыре функции: nullable, f irstpos, lastpos и f ollowpos.

Функции nullable,f irstpos и lastpos определены на узлах дерева, а f ollowpos – на множестве позиций. Значением всех функций, кроме nullable, является множество позиций. Функция f ollowpos вычисляется через три остальныефункции.Функция f irstpos(n) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуютпервым символам в подцепочках, генерируемых подвыражением с вершиной в n. Аналогично, lastpos(n) дает множество позиций, которымсоответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n.

Для узла n, поддеревья которого (т.е. деревья, у которых узел n является корнем) могут породить пустое слово,определим nullable(n) = true, а для остальных узлов nullable(n) = f alse.Таблица для вычисления функций nullable, f irstpos и lastpos приведена на рис. 3.11.узел nлист eлист i(не e)|/\uv·/\uv∗|vnullable(n)truef alsef irstpos(n)∅{i}lastpos(n)∅{i}nullable(u)orf irstpos(u) ∪ f irstpos(v) lastpos(u) ∪ lastpos(v)nullable(v)nullable(u)if nullable(u) thenif nullable(v) thenandf irstpos(u) ∪ f irstpos(v) lastpos(u) ∪ lastpos(v)nullable(v)else f irstpos(u)else lastpos(v)truef irstpos(v)lastpos(v)Рис.

3.11:Пример 3.7. Синтаксическое дерево для пополненного регулярного выражения (a|b)∗ abb# с результатом вычисления функций f irstpos и lastpos приведеноГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ34^ ` ‡ ^ `^ ` ‡ ^ `^ ` ^ `^ ` ‡ ^ ` ^ ` E ^ `^ ` ‡ ^ ` ^ ` E ^ `^ ` ^ ` ^ `D ^ `^ ` _ ^ `^ ` D ^ `^ ` E ^ `Рис. 3.12:позиция123456f ollowpos{1, 2, 3}{1, 2, 3}{4}{5}{6}∅Рис. 3.13:на рис. 3.12. Слева от каждого узла расположено значение f irstpos, справа от узла – значение lastpos. Заметим, что эти функции могут быть вычислены за одинобход дерева.Если i – позиция, то f ollowpos(i) есть множество позиций j таких,что существует некоторая строка ...

cd ..., входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует этому вхождению c, а позиция j – вхождению d.Функция f ollowpos может быть вычислена также за один обход дерева снизу-вверх по следующим двум правилам.1. Пусть n – внутренний узел с операцией · (конкатенация), u и v – егопотомки. Тогда для каждой позиции i, входящей в lastpos(u), добавляемк множеству значений f ollowpos(i) множество f irstpos(v).2.

Пусть n – внутренний узел с операцией ∗ (итерация), u – его потомок. Тогда для каждой позиции i, входящей в lastpos(u), добавляем кмножеству значений f ollowpos(i) множество f irstpos(u).3.3. АЛГОРИТМЫ ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ35Пример 3.8. Результат вычисления функции f ollowpos для регулярного выражения из предыдущего примера приведен на рис. 3.13.Алгоритм 3.3. Прямое построение ДКА по регулярному выражению.Вход.

Регулярное выражение r в алфавите T .Выход. ДКА M = (Q, T, D, q0 , F ), такой что L(M ) = L(r).Метод. Состояния ДКА соответствуют множествам позиций.Вначале Q и D пусты. Выполнить шаги 1-6:(1) Построить синтаксическое дерево для пополненного регулярноговыражения (r)#.(2) Обходя синтаксическое дерево, вычислить значения функцийnullable, f irstpos, lastpos и f ollowpos.(3) Определить q0 = f irstpos(root), где root – корень синтаксическогодерева.(4) Добавить q0 в Q как непомеченное состояние.(5) Выполнить следующую процедуру:while (в Q есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T , такого, чтов R имеется позиция, которой соответствует a){пусть символ a в R соответствует позициямSp1 , ...

, pn , и пусть S =f ollowpos(pi );1≤i≤nif (S 6= ∅){if (S ∈/ Q)добавить S в Q как непомеченное состояние;определить D(R, a) = S;}}}(6) Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #.Пример 3.9. Результат применения алгоритма 3.3 для регулярного выражения (a|b)∗ abb приведен на рис.

3.14.ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ36EDD^`ED^`DE^`E^`Рис. 3.14:3.3.4Построение детерминированного конечногоавтомата с минимальным числом состоянийРассмотрим теперь алгоритм построения ДКА с минимальным числомсостояний, эквивалентного данному ДКА [10].Пусть M = (Q, T, D, q0 , F ) – ДКА. Будем называть M всюду определенным, если D(q, a) 6= ∅ для всех q ∈ Q и a ∈ T .Лемма. Пусть M = (Q, T, D, q0 , F ) – ДКА, не являющийся всюду определенным. Существует всюду определенный ДКА M 0 , такой что L(M ) =L(M 0 ).Доказательство. Рассмотрим автомат M 0 = (Q∪{q 0 }, T, D0 , q0 , F ), где q 0 ∈/Q – некоторое новое состояние, а функция D0 определяется следующимобразом:(1) Для всех q ∈ Q и a ∈ T , таких что D(q, a) 6= ∅, определить D0 (q, a) =D(q, a).(2) Для всех q ∈ Q и a ∈ T , таких что D(q, a) = ∅, определить D0 (q, a) =q0 .(3) Для всех a ∈ T определить D0 (q 0 , a) = q 0 .Легко показать, что автомат M 0 допускает тот же язык, что и M .Приведенный ниже алгоритм получает на входе всюду определенный автомат.

Если автомат не является всюду определенным, его можносделать таковым на основании только что приведенной леммы.Алгоритм 3.4. Построение ДКА с минимальным числом состояний.Вход. Всюду определенный ДКА M = (Q, T, D, q0 , F ).Выход. ДКА M 0 = (Q0 , T, D0 , q00 , F 0 ), такой что L(M ) = L(M 0 ) и M 0содержит наименьшее возможное число состояний.Метод. Выполнить шаги 1-5:3.3.