В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 10
Текст из файла (страница 10)
Если такоеподмножество уже есть, переход делается в него. Если нет — формируетсяновое состояние, оно попадает в список состояний и в список непомеченныхсостояний.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. Введем обозначение p ≈ a, еслипозиции p соответствует символ a. Каждой позиции соответствует единственный символ, но обратное несправедливо: один и тот же символ можетсоответствовать разным позициям.Лемма 3.3. Если p1 , p2 , .
. . pn , pn+1 — последовательность позиций, такая, что:1) p1 ∈ f irstpos(root);2) pi+1 ∈ f ollowpos(pi ), 1 6 i 6 n;3) pn+1 ≈ #,то a1 a2 . . . an ∈ L(РВ), pi ≈ ai .И наоборот, если a1 a2 . . . an ∈ L(РВ), то существует p1 , p2 , . . . , pn ,pn+1 — последовательность позиций, такая, что выполняются перечисленные выше условия.Д о к а з а т е л ь с т в о . Д о с т а т о ч н о с т ь. Условие p1 ∈ f irstpos(root)означает, что по определению строка может начинаться с символа a1 , p1 ≈ a1 .Если pi+1 ∈ f ollowpos(pi ), 1 6 i 6 n, то это означает, что пара символовai ai+1 может встретиться в какой-либо строке, принадлежащей языку.
Записьpn+1 ≈ # означает, что символ an может быть заключительным в строке.Н е о б х о д и м о с т ь . Обратно, пусть a1 a2 . . . an ∈ L(РВ). Тогда по построению ∃ p1 ≈ a1 , p1 ∈ f irstpos(root) . Поскольку в строке, принадлежащей языку, ai+1 следует за ai , то это значит по определению, что средипозиций, соответствующих каждому символу, мы можем выбрать такие, чтоpi+1 ≈ ai+1 , pi+1 ∈ f irstpos(pi ). Поскольку # добавили для строки, принадлежащей языку, pn+1 ∈ f ollowpos(pn ).Пусть {pji+1 } — множество таких pji+1 , что pji+1 ≈ ai+1 , а {pki } — множество таких pki , что pki ≈ ai . Поскольку символ ai+1 следует в строке за символом ai , а строка принадлежит языку, каждый элемент pji+1 ≈ ai+1 естьобраз некоторого pki , ∈ {pki }, т. е.
pji+1 ∈ f ollowpos(pki ). Идя таким образомот последнего символа # к первому a1 , мы построим последовательностьпозиций, удовлетворяющих условию.Теорема 3.2. w ∈ L(РВ) титтк w ∈ L(ДКА). (Здесь и далее титкк —сокращение словосочетания «тогда и только тогда, когда».)Д о к а з а т е л ь с т в о . Д о с т а т о ч н о с т ь . Пусть w ∈ L(РВ), w == a1 a2 .
. . an . Существует последовательность позиций p1 , p2 , . . . pn , pn+1 , порождающих w (в смысле pi ≈ ai ), такая, что p1 ∈ f irstpos(root), pi+1 ∈∈ f ollowpos(pi ), 1 6 i 6 n, pn+1 ≈ #. Покажем, что тогда существует последовательность состояний ДКА q0 , q1 , . . .
qn , такая, что pi ∈ qi−1 , qi = D(qi−1 , ai ),1 6 i 6 n. Докажем это индукцией по i.3.5. Связь регулярных множеств, конечных автоматов и регулярных грамматик51Базис. Возьмем q0 = f irstpos(root) = q0 . Тогда, поскольку w ∈ L(РВ),p1 ∈ f irstpos(root) = q0 .Шаг. Пусть после прочтения a1 a2 . . . ai автомат оказался в состоянии qi .По предположению индукции pi ∈ qi−1 .По построению ДКА[D(qi−1 , ai ) =f ollowpos(pi ) = qi 6= ∅,pi ∈qi−1 ,pi ≈aiпоскольку pi ≈ ai , pi+1 ∈ f ollowpos(pi ), qi — состояние ДКА по построениюи pi+1 ∈ qi .Если i = n, то pn+1 ∈ f ollowpos(pn ) и по построению pn+1 ∈ qn ∈ F ,поскольку pn+1 ≈ #, так что цепочка допускается ДКА.Н е о б х о д и м о с т ь . Пусть w ∈ L(ДКА). Пусть q0 , q1 , . . . qn — последовательность состояний ДКА, которые проходит автомат, допуская w. Имеем:qi = D(qi−1 , ai ), 1 6 i 6 n.
qi = {pji }, qi−1 = {pli−1 }. Поскольку переход из q i−1в q i определен, то ∀ pji ∃ pli−1 , такое, что pji ∈ f ollowpos(pli−1 ) и pji ≈ ai . Значит, можно выбрать последовательность позиций, удовлетворяющих лемме.Следовательно, a1 a2 . . . an ∈ L(РВ), pn+1 ∈ qn , поскольку qn ∈ F ; pn+1 ≈ #.3.5. Связь регулярных множеств, конечных автоматови регулярных грамматикВ подразделе 3.3.3 приведен алгоритм построения детерминированногоконечного автомата по регулярному выражению. Рассмотрим теперь, какпо описанию конечного автомата построить регулярное множество, совпадающее с языком, допускаемым конечным автоматом.Теорема 3.3. Язык, допускаемый детерминированным конечным автоматом, является регулярным множеством.Д о к а з а т е л ь с т в о .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
