В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 15
Текст из файла (страница 15)
Будем писать(q , aw, Zu) ⊢ (p, w, vu),если множество D(q , a, Z) содержит (p, v), где q , p ∈ Q, a ∈ T ∪ {e}, w ∈ T ∗ ,Z ∈ Γ и u, v ∈ Γ∗ (верхушка магазина слева).72Глава 4. Синтаксический анализНачальной конфигурацией МП-автомата M называется конфигурациявида (q0 , w, Z0 ), где w ∈ T ∗ , т. е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине имеется только начальный символ Z0 .Заключительной конфигурацией называется конфигурация вида (q , e, u),где q ∈ F , u ∈ Γ∗ , т.
е. управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.Введем транзитивное и рефлексивно-транзитивное замыкания отношения⊢, а также его степень k > 0 (обозначаемые ⊢+ , ⊢∗ и ⊢k соответственно).Говорят, что цепочка w допускается МП-автоматом M , если(q0 , w, Z0 ) ⊢∗ (q , e, u) для некоторых q ∈ F и u ∈ Γ∗ .Множество всех цепочек, допускаемых автоматом M , называется языком,допускаемым (распознаваемым, определяемым) автоматом M (обозначаетсяL(M )).Пример 4.1. Рассмотрим МП-автоматM = ({q0 , q1 , q2 }, {a, b}, {Z , a, b}, D, q0 , Z , {q2 }),у которого функция переходов D содержит элементы:D(q0 , a, Z) = {(q0 , aZ)},D(q0 , b, Z) = {(q0 , bZ)},D(q0 , a, a) = {(q0 , aa), {q1 , e)},D(q0 , a, b) = {(q0 , ab)},D(q0 , b, a) = {(q0 , ba)},D(q0 , b, b) = {(q0 , bb), (q1 , e)},D(q1 , a, a) = {(q1 , e)},D(q1 , b, b) = {(q1 , e)},D(q1 , e, Z) = {(q2 , e)}.Нетрудно показать, что L(M ) = {wwR |w ∈ {a, b}+ }, где wR обозначает обращение(«переворачивание») цепочки w.Иногда допустимость определяют несколько иначе: цепочка w допускаетсяМП-автоматом M , если (q0 , w, Z0 ) ⊢∗ (q , e, e) для некоторого q ∈ Q.
В такомслучае говорят, что автомат допускает цепочку опустошением магазина. Этиопределения эквивалентны, ибо справедливаТеорема 4.1. Язык допускается МП-автоматом тогда и только тогда, когда он (некоторым другим автоматом) допускается опустошениеммагазина.Д о к а з а т е л ь с т в о . Пусть L = L(M ) для некоторого МП-автоматаM = (Q, T , Γ, D, q0 , Z0 , F ).
Построим новый МП-автомат M ′ , допускающийтот же язык опустошением магазина.Пусть M ′ = (Q ∪ {q0′ , qe }, T , Γ ∪ {Z0′ }, D′ , q0′ , Z0′ , ∅), где функция переходов D′ определена следующим образом:4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью731) если (r, u) ∈ D(q , a, Z), то (r, u) ∈ D′ (q , a, Z) для всех q ∈ Q, a ∈ T ∪ {e}и Z ∈ Γ (моделирование M );2) D′ (q0′ , e, Z0′ ) = {(q0 , Z0 Z0′ )} (начало работы);3) для всех q ∈ F и Z ∈ Γ ∪ {Z0′ } множество D′ (q , e, Z) содержит (qe , e)(переход в состояние сокращения магазина без продвижения);4) D′ (qe , e, Z) = {(qe , e)} для всех Z ∈ Γ ∪ {Z0′ } (сокращение магазина).Автомат сначала переходит в конфигурацию (q0 , w, Z0 Z0′ ) соответственноопределению D′ в п. 2), затем в (q , e, Y1 .
. .Yk Z0′ ), q ∈F соответственно п. 1),затем в (qe , e, Y1 . . .Yk Z0′ ), q ∈ F соответственно п. 3), затем в (qe , e, e) соответственно п. 4). Нетрудно показать по индукции, что (q0 , w, Z0 ) ⊢+ (q , e, u)(где q ∈ F ) выполняется для автомата M тогда и только тогда, когда(q0′ , w, Z0′ ) ⊢+ (qe , e, e) выполняется для автомата M ′ . Поэтому L(M ) = L′ , гдеL′ — язык, допускаемый автоматом M ′ опустошением магазина.Обратно, пусть M = (Q, T , Γ, D, q0 , Z0 , ∅) — МП–автомат, допускающийопустошением магазина язык L. Построим автомат M ′ , допускающий тот жеязык по заключительному состоянию.Пусть M ′ = (Q ∪ {q0′ , qf }, T , Γ ∪ {Z0′ }, D′ , q0′ , Z0′ , {qf }), где D′ определяется следующим образом:1) D′ (q0′ , e, Z0′ ) = {(q0 , Z0 Z0′ )} — переход в «режим M »;2) для каждого q ∈ Q, a ∈ T ∪ {e}, и Z ∈ Γ определим D′ (q , a, Z) == D(q , a, Z) — работа в «режиме M »;3) для всех q ∈ Q, (qf , e) ∈ D′ (q , e, Z0′ ) — переход в заключительное состояние.Нетрудно показать по индукции, что L = L(M ′ ).Одним из важнейших результатов теории контекстно-свободных языковявляется доказательство эквивалентности МП-автоматов и КС-грамматик.Теорема 4.2.
Язык является контекстно-свободным тогда и толькотогда, когда он допускается МП-автоматом.Д о к а з а т е л ь с т в о . Пусть G = (N , T , P , S) — КС-грамматика. Построим МП-автомат, допускающий язык L(G) опустошением магазина.Пусть M = ({q}, T , N ∪ T , D, q , S , ∅), где D определяется следующимобразом:1) если A → u ∈ P , то (q , u) ∈ D(q , e, A);2) D(q , a, a) = {(q , e)} для всех a ∈ T .74Глава 4.
Синтаксический анализФактически этот МП-автомат в точности моделирует все возможные выводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки w ∈ T ∗ вывод S ⇒ + w в грамматике G существует тогда и только тогда,когда существует последовательность тактов (q , w, S) ⊢+ (q , e, e) автомата M .Наоборот, пусть дан M = (Q, T , Γ, D, q0 , Z0 , ∅) — МП-автомат, допускающий опустошением магазина язык L.
Построим грамматику 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
