В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 11
Текст из файла (страница 11)
Введем обозначение 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.
Язык, допускаемый детерминированным конечным автоматом, является регулярным множеством.Д о к а з а т е л ь с т в о . Пусть L — язык, допускаемый детерминированным конечным автоматомM =({q1 , . . . , qn }, T , D, q1 , F ).k множество всех слов x, таких, что D e (q , x) =Обозначим посредством Riji= qj и если De (qi , y) = qs для любой цепочки y — префикса x, отличного от xи e, то s 6 k .k есть множество всех слов, которые переводят коИными словами, Rijнечный автомат из состояния qi в состояние qj , не проходя ни через какоесостояние qs для s > k . Однако i и j могут быть больше k .k может быть определено рекурсивно следующим образом:Rij0 = {a|a ∈ T , D(q , a) = q },Rijij52Глава 3.
Лексический анализk = Rk−1RijijSk−1k−1 ∗ k−1(Rkk) Rkj , где 1 6 k 6 n.Rikk означает, что для входной цепочки w , пеТаким образом, определение Rijреводящей M из qi в qj без перехода через состояния с номерами, бо́льшимиk, справедливо ровно одно из следующих двух утверждений.k−11) Цепочка w принадлежит Rij, т. е. при анализе цепочки w автоматникогда не достигает состояний с номерами, бо́льшими или равными k .k−12) Цепочка w может быть представлена как w = w1 w2 w3 , где w1 ∈ Rikk−1 ∗(подцепочка w1 переводит M сначала в qk ), w2 ∈ (Rkk) (подцепочка w2переводит M из qk обратно в qk , не проходя через состояния с номерами,k−1(подцепочка w3 переводит Mбо́льшими или равными k ), w3 ∈ Rkjиз состояния qk в qj ) — рис.
3.14.jРис. 3.14Тогда L =регулярно.Sqj ∈FR1nj . Индукцией по k можно показать, что это множествоТаким образом, для всякого регулярного множества имеется конечныйавтомат, допускающий в точности это регулярное множество, и наоборот —язык, допускаемый конечным автоматом, есть регулярное множество.Рассмотрим теперь соотношение между теми языками, которые порождаются праволинейными грамматиками, и теми, которые допускаются конечными автоматами.Праволинейная грамматика G = (N , T , P , S) называется регулярной,если:1) каждое ее правило, кроме S → e, имеет вид либо A → aB , либо A → a,где A, B ∈ N , a ∈ T ;2) в том случае, когда S → e ∈ P , начальный символ S не встречаетсяв правых частях правил.Лемма 3.4. Пусть G — праволинейная грамматика. Тогда существуетрегулярная грамматика G′ такая, что L(G) = L(G′ ).Д о к а з а т е л ь с т в о предоставляется читателю в качестве упражнения.3.5.
Связь регулярных множеств, конечных автоматов и регулярных грамматик53Теорема 3.4. Пусть G = (N , T , P , S) — праволинейная грамматика. Тогда существует недетерминированный конечный автомат M == (Q, T , D, q0 , F ) для которого L(M ) = L(G).Д о к а з а т е л ь с т в о . На основании леммы 3.4 без ограничения общности можно считать, что G — регулярная грамматика.Построим НКА M следующим образом:1) состояниями M будут нетерминалы G плюс новое состояние R, не принадлежащее N , так что Q = N ∪ {R};2) в качестве начального состояния M примем S , т. е.
q0 = S ;3) если P содержит правило S → e, то F = {S , R}, иначе F = {R} (напомним, что S не встречается в правых частях правил, если S → e ∈ P );4) состояние R ∈ D(A, a), если A → a ∈ P ; кроме того, D(A, a) содержитвсе B , такие, что A → aB ∈ P , причем D(R, a) = ∅ для каждого a ∈ T .Читая вход w, M моделирует вывод w в грамматике G. Покажем, чтоL(M ) = L(G). Пусть w = a1 a2 . . . an ∈ L(G), n > 1. Тогда S ⇒ a1 A1 ⇒⇒ . . .
⇒ a1 a2 . . . an−1 An−1 ⇒ a1 a2 . . . an−1 an для некоторой последовательности нетерминалов A1 , A2 , . . . , An−1 . По определению, D(S , a1 ) содержит A1 ,D(A1 , a2 ) содержит A2 , и т. д., D(An−1 , an ) содержит R. Значит, w ∈ L(M ),поскольку De (S , w) содержит R, а R ∈ F . Если e ∈ L(G), то S ∈ F , так чтоe ∈ L(M ).Аналогично, если w = a1 a2 .
. . an ∈L(M ), n > 1, то существует последовательность состояний S , A1 , A2 , . . . , An−1 , R, такая, что D(S , a1 ) содержит A1 ,D(A1 , a2 ) содержит A2 , и т. д. Поэтому S ⇒ a1 A1 ⇒ a1 a2 A2 ⇒ . . . ⇒ a1 a2 . . .. . . an−1 An−1 ⇒ a1 a2 . .
. an−1 an — вывод в G и x ∈ L(G). Если e ∈ L(M ),то S ∈ F , так что S → e ∈ P и e ∈ L(G).Теорема 3.5. Для каждого недетерминированного конечного автомата M = (Q, T , D, q0 , F ) существует праволинейная грамматика G == (N , T , P , S), такая, что L(G) = L(M ).Д о к а з а т е л ь с т в о . Без потери общности можно считать, что автомат M — детерминированный. Определим грамматику G следующим образом:1) нетерминалами грамматики G будут состояния автомата M , так чтоN = Q;2) в качестве начального символа грамматики G примем q0 , т. е.
S = q0 ;3) A → aB ∈ P , если D(A, a) = B ;4) A → a ∈ P , если D(A, a) = B и B ∈ F ;5) S → e ∈ P , если q0 ∈ F .Доказательство того, что S ⇒ ∗ w тогда и только тогда, когда De (q0 , w) ∈∈ F , аналогично доказательству теоремы 3.2.54Глава 3. Лексический анализВ некоторых случаях для определения того, является ли язык регулярным, может быть полезным необходимое условие, которое называется леммойОгдена о разрастании.Теорема 3.6. (Лемма о разрастании для регулярных множеств.) ПустьL — регулярное множество. Тогда существует такая константа k , чтоесли w ∈ L и |w| > k , то цепочку w можно представить в виде xyz , где0 < |y|, |xy| 6 k и xy i z ∈ L для всех i > 0.Д о к а з а т е л ь с т в о .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
