В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 10
Текст из файла (страница 10)
while (list не пуст) {выбрать первый элемент списка r и удалить его из списка;for (каждого состояния u c дугой от r в u, помеченной e)/ e − closure(R) ) {do if (u ∈добавить u к e-closure(R);поместить u в список list; } }44Глава 3. Лексический анализАлгоритм 3.2. Построение детерминированного конечного автоматапо недетерминированному.Вход.
НКА M = (Q, T , D, q0 , F ).Выход. ДКА M ′ = (Q′ , T , D′ , q0′ , F ′ ), такой, что L(M ) = L(M ′ ).Метод. Каждое состояние результирующего ДКА — это некоторое множество состояний исходного НКА.Вначале Q′ и D′ пусты. Выполнить шаги 1–4:1. Определить q0′ = e-closure({q0 }).2.
Добавить q0′ в Q′ как непомеченное состояние.3. Выполнить следующую процедуру:while (в Q′ есть непомеченное состояние R){пометить R;for (каждого входного символа a ∈ T ){S = e-closure(move(R, a));if (S 6= ∅){/ Q′ )if (S ∈добавить S в Q′ как непомеченноесостояние;определить D′ (R, a) = S ;}}}4. Определить F ′ = {S|S ∈ Q′ , S ∩ F 6= ∅}.Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.11.Рис. 3.113.4. Алгоритмы построения конечных автоматов453.4.3. Реализация на Java.
Алгоритм преобразования недерминированного конечного автомата в детермининрованный реализован в пакете Automata функцией NFAtoDFA(). Две основные структуры данных — это функция,отображающая имя состояния (номер) в подмножество состояний исходногоНКА, образующих данное состояние ДКА, и список непомеченных состояний.
Очередное состояние выбирается из списка непомеченных состояний.Когда в результате работы функции move формируется новое подмножество,оно проверяется на совпадение с каким-либо из имеющихся. Если такоеподмножество уже есть, переход делается в него.
Если нет — формируетсяновое состояние, оно попадает в список состояний и в список непомеченныхсостояний.3.4.4. Обоснование. Определим расширенную функцию переходов дляДКА рекурсивно следующим образом:для ДКАeDDFa ∈ T,A (q , a) = D(q , a),eeDDFA (q , wa) = DDF A (DDF A (q , w), a),для НКАeDNF A (q , w),w ∈ T +;w ∈ T ∗,— это множество состояний, в которых может оказаться автомат по прочтении цепочки w;eDNF A (q , e) = e-closure({q}).eЕсли w = ua, DNF A (q , u) = {p1 , p2 , .
. . pk }, то[eDN(q,w)=e-closure(DN F A (pi , a)) = e-closure(move(p1 , p2 , . . . pk , a)),FAipi ∈eDNF A (q , u).eeeeТеорема 3.1. DDFA (q0 , w) = DN F A (q0 , w), q0 =e-closure({q0 }).Д о к а з а т е л ь с т в о . Индукция по длине слова.eeБазис. Если |w| = 0, то w = e, DNF A (q0 , e) = e-closure({q0 }) = q0 =ee= DDF A (q0 , e).Шаг индукции. Пусть w = ua.
По предположению индукцииeeeDDFA (q0 , u) = DN F A (q0 , u) = {p1 , p2 , . . . pk } = r.eТогда по построению ДКА и определению DDFA имеемeeeDDFA (q0 , ua) = DDF A (DDF A (q , u), a) = DDF A (r , a) = DDF A ({p1 , p2 , . . . pk }, a) == e-closure(move({p1 , p2 , . . . pk }, a) =[= e-closure( DN F A (pi , a)), pi ∈ {p1 , p2 , . .
. pk }.i46Глава 3. Лексический анализeДля НКА имеем по определению DNFA[eDNDN F A (pi , a)), pi ∈ {p1 , p2 , . . . pk },F A (q , ua) = e-closure(iт. е. имеет место равенство. Таким образом, прочитав w, НКА окажется в pi .Если pi ∈ FN F A , pi ∈ pe = {p1 , p2 , . . .
pk }-состояние ДКА, то pe ∈ FDF Aпо построению.3.4.5. Построение детерминированного конечного автомата по регулярному выражению. Приведем теперь алгоритм построения по регулярному выражению детерминированного конечного автомата, допускающего тотже язык [3].Пусть дано регулярное выражение r в алфавите T . Для однозначностизаключим это выражение в скобки и добавим маркер конца: (r)#. Такое регулярное выражение будем называть пополненным.
В процессе своей работыалгоритм будет использовать пополненное регулярное выражение.Алгоритм будет оперировать с синтаксическим деревом для пополненного регулярного выражения (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.1.3.4.
Алгоритмы построения конечных автоматов47Т а б л и ц а 3.1узел n nullable(n)f irstpos(n)lastpos(n)лист etrue∅∅лист if alse{i}{i}|nullable(u)f irstpos(u)lastpos(u)/\or∪∪uvnullable(v)f irstpos(v)lastpos(v)(не e)·nullable(u) if nullable(u) then if nullable(v) then/\andf irstpos(u)lastpos(u)uvnullable(v)∪∪f irstpos(v)lastpos(v)else f irstpos(u)else lastpos(v)f irstpos(v)lastpos(v)∗|truevРис. 3.12Пример 3.7. На рис. 3.12 приведено cинтаксическое дерево для пополненногорегулярного выражения (a|b)∗ abb# с результатом вычисления функций f irstposи lastpos.
Слева от каждого узла расположено значение f irstpos, справа от узла —значение lastpos. Заметим, что эти функции могут быть вычислены за один обходдерева.Если i — позиция, то f ollowpos(i) есть множество позиций j , таких,что существует некоторая строка . . . cd . . ., входящая в язык, описываемый48Глава 3. Лексический анализрегулярным выражением, причем такая, что позиция 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.8. Результат вычисления функции f ollowpos для регулярного выражения из предыдущего примера приведен в табл. 3.2.Т а б л и ц а 3.2позиция f ollowpos1{1, 2, 3}2{1, 2, 3}3{4}4{5}5{6}6∅Алгоритм 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){3.4. Алгоритмы построения конечных автоматов49пусть символ a в R соответствуетпозициямSp1 , .
. . , pn , и пусть S =f ollowpos(pi );16i6nif (S 6= ∅){if (S ∈/ Q)добавить S в Q как непомеченноесостояние;определить D(R, a) = S ;}}}6. Определить F как множество всех состояний из Q, содержащих позиции, связанные с символом #.Пример 3.9. Результат применения алгоритма 3.3 к регулярному выражения(a|b)∗ abb приведен на рис. 3.13.Рис. 3.13Лемма 3.2. Построенный автомат не зависит от порядка расстановки скобок ассоциативных операций.Д о к а з а т е л ь с т в о . Нужно рассмотреть непосредственные построения для двух ассоциативных операций — конкатенации и объединения.3.4.6. Построение ДКА по РВ на Java.
Регулярное выражение записывается в соответствии с синтаксисом, задаваемым следующими правилами:Expr::=Union’#’Union::=Factor(’|’Factor)Factror::=TermTerm*Term::=Atom[′ ∗′ ]Atom::=String|′ (′ Expr′ )′ |′ $′В соответствии с этой грамматикой в пакете regularExpression написансинтаксический анализатор методом рекурсивного спуска (см.
раздел 4.3).Одновременно с синтаксическим анализом осуществляется вычисление атрибутов nullable, f irstP os, lastP os и функции f ollowP os. Затем по функцииf ollowP os практически так же, как и при построении ДКА по НКА, строитсяДКА.50Глава 3. Лексический анализ3.4.7. Обоснование. Пусть задано регулярное выражение РВ со своимдеревом, и пусть ДКА — детерминированный конечный автомат, построенныйпо РВ в соответствии с алгоритмом 3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
