В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 16
Текст из файла (страница 16)
Построим грамматику G, порождающуюязык L.Пусть G = ({ [qZr] | q , r ∈ Q, Z ∈ Γ} ∪ {S}, T , P , S), где P состоит из правил следующего вида.1. S → [q0 Z0 q] ∈ P для всех q ∈ Q.2. Если (r, e) ∈ D(q , a, Z), то [qZr] → a ∈ P , a ∈ T ∪ {e}.3. Если (r, X1 . . . Xk ) ∈ D(q , a, Z), k > 1, то[qZsk ] → a[rX1 s1 ][s1 X2 s2 ] .
. . [sk−1 Xk sk ] ∈ Pдля любого набора s1 , s2 , . . . , sk состояний из Q.Нетерминалы и правила вывода грамматики определены так, что работеавтомата M при обработке цепочки w соответствует левосторонний вывод wв грамматике G.Лемма 4.1. Если (q , x, α) ⊢∗ (p, y , β), то ∀ w ∈ T ∗ , γ ∈ Γ∗ (q , xw, αγ) ⊢∗(p, yw, βγ).Д о к а з а т е л ь с т в о основано на том, что магазинный автомат читаетмагазин строго сверху-вниз посимвольно и читает вход также строго слеванаправо посимвольно.Интерпретация определенных выше нетерминалов такова.Теорема 4.3.
[qZp] ⇒∗ w титтк (q , w, Z) ⊢∗ (p, e, e).Д о к а з а т е л ь с т в о . Н е о б х о д и м о с т ь . Пусть (q , w, Z) ⊢∗ (p, e, e).Доказываем индукцией по числу переходов.Базис. (q , w, Z) ⊢ (p, e, e), т. е. (p, e) ∈ D(q , w, Z). По построению (правило 2) [qZp] → w, w ∈ T ∪ {e}.Шаг.
Пусть (q , w, Z) ⊢∗ (p, e, e) состоит из n > 1 шагов. Рассмотримпервый шаг: (q , w, Z) ⊢ (s0 , u, X1 X2 . . . Xk ) ⊢∗ (p, e, e), w = au, (s0 , X1 X2 . . .. . . Xk ) ∈ D(q , a, Z), a ∈ T ∪ {e}. По построению [qZsk ] → a[s0 Xs1 ][s1 Xs2 ] . . .. . . [sk−1 Xsk ] для всех s1 , . . . sk ∈ Q. Поскольку автомат читает цепочкуu с опустошением магазина, ее можно разбить так, что u = w1 w2 .
. . wkи ∃ s1 , . . . sk−1 , такие, что (si−1 , wi , Xi ) ⊢∗ (si , e, e). При этом используется менее n шагов. По предположению индукции [si−1 Xi si ] ⇒ ∗ wi . Тогда [qZsk ] → a[s0 X1 s1 ][s1 X2 s2 ] . . . [sk−1 Xk sk ] ⇒∗ aw1 [s1 X2 s2 ] . . .
[sk−1 Xk sk ] ⇒∗⇒∗ aw1 . . . wk = w.Д о с т а т о ч н о с т ь . Пусть [qZp] ⇒∗ w. Индукция по длине вывода.4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью75Базис. Правило [qZp] → w ∈ P , значит по правилу 2 (q , w, Z) ⊢ (p, e, e), w ∈∈ T ∪ e.Шаг. Пусть [qZp] ⇒ ∗ w за n > 1 шагов. На первом шаге [qZsk ] ⇒⇒ a[s0 X1 s1 ][s1 X2 s2 ] .
. . [sk−1 Xk sk ] ⇒∗ w(sk = p). Разобьем цепочку aw1 . . . wkтак, что [si−1 Xi si ] ⇒ ∗ wi , i = 1, . . . k . По предположению индукциипоскольку все эти выводы короче n, (si−1 wi Xi ) ⊢∗ (si , e, e). Значит,по лемме (si−1 , wi wi+1 . . . wk , Xi Xi+1 . . . Xk ) ⊢∗ (si , wi+1 . . . wk , Xi+1 . . . Xk ).Правило [qZsk ] → a[s0 X1 s1 ][s1 X2 s2 ] . . . [sk−1 Xk sk ] соответствует переходу(s0 , X1 , X2 , . .
. , Xk ) ∈ D(q , a, Z). Следовательно, (q , aw1 . . . wk ) ⊢ (s0 , w1 . . .. . . wk , X1 . . . Xk ) ⊢∗ (s1 , w2 . . . wk , X2 . . . Xk ) ⊢∗ (sk , e, e).Следствие. S ⇒∗ w титтк [q0 Zp0 ] ⇒∗ w титтк (q0 , w, Z0 ) ⊢∗ (p, e, e).Пример 4.2. Построение грамматики по МП-автомату.Пусть задан автоматD(q0 , 0, Z0 ) = (q0 , XZ0 )D(q0 , 0, X) = (q0 , XX)D(q0 , 1, X) = (q1 , e)D(q1 , 1, X) = (q1 , e)D(q1 , e, X) = (q1 , e)D(q1 , e, Z0 ) = (q1 , e)Грамматика:S → [q0 , Z0 , q0 ]S → [q0 , Z0 , q1 ]Из D(q0 , 0, Z0 ) = (q0 , XZ0 ) получаются:[q0 , Z0 , q0 ] → 0[q0 , X , q0 ][q0 , Z0 , q0 ][q0 , Z0 , q0 ] → 0[q0 , X , q1 ][q1 , Z0 , q0 ][q0 , Z0 , q1 ] → 0[q0 , X , q0 ][q0 , Z0 , q1 ][q0 , Z0 , q1 ] → 0[q0 , X , q1 ][q0 , Z0 , q1 ]Из D(q0 , 0, X) = (q0 , XX) получаются:[q0 , X , q0 ] → 0[q0 , X , q0 ][q0 , X , q0 ][q0 , X , q0 ] → 0[q0 , X , q1 ][q1 , X , q0 ][q0 , X , q1 ] → 0[q0 , X , q0 ][q0 , X , q1 ][q0 , X , q1 ] → 0[q0 , X , q1 ][q1 , X , q1 ]Из D(q0 , 1, X) = (q1 , e) получается [q0 , X , q1 ] → 1.Из D(q1 , e, Z0 ) = (q1 , e) получается [q1 , Z0 , q1 ] → e.Из D(q1 , e, X) = (q1 , e) получается [q1 , X , q1 ] → e.Из D(q1 , 1, X) = (q1 , e) получается [q1 , X , q1 ] → 1.Нет правил для [q1 , X , q0 ], [q , Z0 , q0 ].Нет терминальных выводов для [q0 , Z0 , q0 ] [q0 , X , q0 ].Остаются:S → [q0 , Z0 , q1 ][q0 , Z0 , q1 ] → 0[q0 , X , q1 ][q1 , X , q0 ][q0 , X , q1 ] → 0[q0 , X , q1 ][q1 , X , q1 ][q1 , Z0 , q1 ] → e[q0 , X , q1 ] → 1[q1 , X , q1 ] → e76Глава 4.
Синтаксический анализ[q1 , X , q1 ] → 1Или в другой записи:S→AA → 0BCB → 0BDC→eB→1D→eD→1МП-автомат M = (Q, T , Γ, D, q0 , Z0 , F ) называется детерминированным(ДМП-автоматом), если выполняются следующие условия:1) множество D(q , a, Z) содержит не более одного элемента для любыхq ∈ Q, a ∈ T ∪ {e}, Z ∈ Γ;2) если D(q , e, Z) 6= ∅, то D(q , a, Z) = ∅ для всех a ∈ T .Допускаемый ДМП-автоматом язык называется детерминированным КСязыком.Так как функция переходов ДМП-автомата содержит не более одногоэлемента для любой тройки аргументов, мы будем пользоваться записьюD(q , a, Z) = (p, u) для обозначения D(q , a, Z) = {(p, u)}.Пример 4.3. Рассмотрим ДМП-автоматM = ({q0 , q1 , q2 }, {a, b, c}, {Z , a, b}, D, q0 , Z , {q2 }),функция переходов которого определяется следующим образом:D(q0 , X , Y ) = (q0 , XY ), X ∈ {a, b}, Y ∈ {Z , a, b},D(q0 , c, Y ) = (q1 , Y ), Y ∈ {a, b},D(q1 , X , X) = (q1 , e), X ∈ {a, b},D(q1 , e, Z) = (q2 , e).Нетрудно показать, что этот детерминированный МП-автомат допускает языкL = {wcwR |w ∈ {a, b}+ }.К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы.
Доказано, в частности, что существуют КСязыки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).Рассмотрим еще один важный вид МП-автомата.Расширенным автоматом с магазинной памятью назовем семерку M == (Q, T , Γ, D, q0 , Z0 , F ), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечногоподмножества множества Q × (T ∪ {e}) × Γ∗ во множество конечных подмножеств множества Q × Γ∗ . Все остальные определения (конфигурации, такта,допустимости) для расширенного МП-автомата остаются такими же, как дляобычного.4.1.
Контекстно-свободные грамматики и автоматы с магазинной памятью77Теорема 4.4. Пусть M = (Q, T , Γ, D, q0 , Z0 , F ) — расширенный МПавтомат. Тогда существует МП-автомат M ′ , такой, что L(M ′ ) = L(M ).Расширенный МП-автомат M = (Q, T , Γ, D, q0 , Z0 , F ) называется детерминированным, если выполняются следующие условия:1) множество D(q , a, u) содержит не более одного элемента для любых q ∈∈ Q, a ∈ T ∪ {e}, u ∈ Γ∗ ;2) если D(q , a, u) 6= ∅, D(q , a, v) 6= ∅ и u 6= v , то не существует цепочки x,такой, что u = vx или v = ux;3) если D(q , a, u) 6= ∅, D(q , e, v) 6= ∅, то не существует цепочки x, такой,что u = vx или v = ux.Теорема 4.5. Пусть M = (Q, T , Γ, D, q0 , Z0 , F ) — расширенный ДМПавтомат.
Тогда существует ДМП-автомат M ′ , такой, что L(M ′ ) == L(M ).ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе LL- и LR-анализаторов.Определение 4.1. Говорят, что КС-грамматика находится в нормальнойформе Хомского, если каждое правило имеет один из следующих видов:1) A → BC , A, B , C — нетерминалы;2) A → a, a — терминал;3) S → e, и в этом случае S не встречается в правых частях правил.Утверждение 4.1.
Любую КС-грамматику можно преобразовать в эквивалентную ей в нормальной форме Хомского.Определение 4.2. Назовем высотой дерева максимальную длину пути(число внутренних вершин) от корня до листа.Утверждение 4.2. Если КС-грамматика находится в нормальной форме Хомского, то для любой цепочки α, если α ∈ L(G) и h — высота деревавывода с кроной α, |α| 6 2h−1 .Обратно, если |α| > 2h−1 , то высота дерева больше или равна h.Теорема 4.6. (Лемма о разрастании для контекстно-свободных языков.)Для любого КС-языка L существуют такая константа k , что любаяцепочка α ∈ L, |α| > k , представима в виде α = uvwxy , где:1) |vwx| 6 k ;2) vx 6= e;3) uv i wxi y ∈ L для любого i > 0.Д о к а з а т е л ь с т в о . Пусть L = L(G), где G = (N , Σ, P , S) —контекстно-свободная грамматика в нормальной форме Хомского.
Обозначимчерез n число нетерминалов, т. е. n = |N |, и рассмотрим k = 2n .78Глава 4. Синтаксический анализПусть |α| > k = 2n . Тогда высота дерева с кроной α больше или равна n + 1 и есть путь по дереву (от корня до некоторого листа), которыйвключает не менее, чем n + 1 внутренних вершин (нетерминалов). Такимобразом, существует хотя бы один нетерминал, который помечает не менеедвух вершин этого пути. Среди всех таких нетерминалов на этом путипусть A — такой, что его второе вхождение, считая от листа, не содержитдругих нетерминалов, обладающих этим свойством (если бы это было не так,то выбрали бы этот другой).
Пусть q — вхождение A, ближайшее к листу,p — ближайшее, расположенное выше. Представим крону α в виде uvwxy , гдеw — крона поддерева D1 с корнем q и vwx — крона поддерева D2 с корнем p.Тогда высота поддерева D2 не более (n − 1) + 2 = n + 1 (не более n − 1нетерминалов, отличных от A, плюс два вхождения A), так что |vwx| 6 2n .Также очевидно, что vx 6= e, поскольку в силу определения нормальнойформы Хомского p имеет двух сыновей, помеченных нетерминалами, из которых не выводится пустая цепочка.Кроме того, S ⇒∗ uAy ⇒ ∗ uvAxy ⇒ ∗ uvwxy , а также A ⇒ ∗ vAx ⇒ ∗ vwx.Отсюда получаем A ⇒ ∗ v i wxi для всех i > 0 и S ⇒ ∗ uv i wxi y для всех i > 0.Пример 4.4. Покажем, что язык L = {an bn cn | n > 1} не является контекстно–свободным языком.Если бы он был КС–языком, то мы взяли бы константу k , которая определяетсяв лемме о разрастании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
