6. 2. Эквивалентность мп-автоматов и кс-грамматик

Теперь можно показать, что языки, определяемые МП-автоматами - это в точности КС-языки. Начнем с построения естественного (недетерминированного) “нисходящего” распознавателя, эквивалентного данной КС-грамматике.

Теорема 6.2. Пусть G=(, , P, S) - КС-грамматика. По грамматике G можно построить такой МП-автомат R, что L(R)=L(G).

Доказательство. Построим R так, чтобы он моделировал все левые выводы в грамматике G.

Пусть R=({q},  ,    ,  , q, S,  ), где  определяется следующим образом:

(1) если A   принадлежит P, то  (q,  , A) содержит (q,  );

(2)  (q, a, a) = {(q,  ) для всех a  .

Необходимо показать, что

A  ^m 

тогда и только тогда, когда

(q,  , A)  ⁿ (q,  ,  )

для некоторых m, n  1.

Необходимость условия доказывается индукцией по m. Допустим, что A  ^m . Если m=1 и  = a₁ ... a_k (k  0), то

(q, a₁ ... a_k , A)  (q, a₁ ... a_k , a₁ ... a_k )

 ^k (q,  ,  )

Теперь предположим, что A  ^m  для некоторого m>1. Первый шаг этого вывода должен иметь вид A  X₁ X₂ ... X_k , где для некоторого m _i < m, 1 i  k, и x₁ x₂ ...x_k =  . Тогда

(q,  , A)  (q,  , X₁ X₂ ... X_k )

Если X_i   , то по предположению индукции

(q, x_i , X_i )  ^ (q,  ,  )

Если X_i   , то

(q, x_i , X_i )  (q,  ,  )

Объединяя все эти последовательности тактов, видим, что

(q,  , A)  ⁺ (q,  ,  ).

Для доказательства достаточности покажем индукцией по n, что если

(q,  , A)  ⁿ (q,  ,  ),

то

A  ⁺  .

Если n=1, то  =  и A   принадлежит P. Предположим, что утверждение верно для всех n^< n. Тогда первый такт, сделанный МП-автоматом R, должен иметь вид

(q,  , A)  (q,  , X₁ ... X_k )

причем (q, x_i , X_i )  (q,  ,  ) для 1 i  k и  = x₁ x₂ ... x_k . Тогда A  X₁ ... X_k - правило из P, и по предположению индукции X_i  ⁺ x_i для X_i   . Если X_i   , то X_i  ⁰ x_i. Таким образом

A  X₁ ... X_k

 ^ x₁ X₂ ... X_k

........................

 ^ x₁ x₂ ... x_k-1 Xk

 ^ x₁ x₂ ... x_k-1 x_k = 

- вывод цепочки  из A в грамматике G. 

Пример 6.4. Построим МП-автомат R, для которого L(R) = L(G₀ ), где G₀ - грамматика, определяющая арифметические выражения с правилами

E  E+TT

T  TFF

F  (E)a

Пусть R = ({q},  ,  ,  , q, E,  ), где  определяется так:

(1)  (q,  , E) = {(q, E+T), (q, T)};

(2)  (q,  , T) = {(q, TF), (q, F)};

(3)  (q,  , F) = {(q, (E)), (q, a)};

(4)  (q, b, b) = {(q,  )} для всех b {a, +, , (, )}.

При выводе a+aa для R возможна среди других следующая последовательность тактов:

(q, a+aa, E)  (q, a+aa, E+T)

 (q, a+aa, T+T)

 (q, a+aa, F+T)

 (q, a+aa, a+T)

 (q, +aa, +T)

 (q, aa, T)

 (q, aa, TF)

 (q, aa, FF)

 (q, aa, aF)

 (q, a, F)

 (q, a, F)

 (q, a, a)

 (q,  ,  )

Заметим, что вычисление МП-автомата R соответствует левому выводу цепочки a+aa из E в грамматике G₀ .

Тип синтаксического анализа, проводимого МП-автоматом, построенным в теореме 6.2, называется “нисходящим анализом” (“анализом сверху вниз”) или “пред­ска­зы­ва­ю­щим анализом”, потому что при этом дерево вывода строится по существу сверху (от корня) вниз, а каждый такт вида (1) можно трактовать как предсказание очередного шага левого вывода. Подробно нисходящий синтаксический анализ и его алгоритмы, как часть компилятора, будут рассмотрены во второй части пособия.

Можно построить расширенный МП-автомат, который работает “снизу вверх” как “восходящий анализатор”, моделируя в обратном порядке правые выводы в КС-грамматике. Рассмотрим цепочку a+aa L(G₀ ) из примера 6.4 и ее правый вывод из E в грамматике G₀ :

E  E+T  E+TF  E+Ta  E+Fa

 E+aa  T+aa  F+aa  a+aa

Предположим, что мы записываем этот вывод в обратном порядке. Если считать, что переход от цепочки a+aa к цепочке F+aa происходит по правилу F  a, примененному “в обратном направлении”, то можно сказать, что цепочка a+aa “сверты­ва­ется (редуцируется) слева” к цепочке F+aa. Более того, это единственно возможная левая свертка. Подобным же образом можно правовыводимую цепочку F+aa свернуть слева к цепочке T+aa с помощью правила T  F и т.д. Определим формально левую свертку.

Пусть G=(, , P, S) - КС-грамматика и

S ^ A   ^ 

- правый вывод в ней. Говорят, что правовыводимую цепочку  можно свернуть слева (редуцировать) к правовыводимой цепочке A с помощью правила A   . Указанное вхождение цепочки  в цепочку  называется основой цепочки  .

Таким образом, основа правовыводимой цепочки - это ее любая подцепочка, которая является правой частью некоторого правила, причем после замены ее левой частью этого правила тоже получится правовыводимая цепочка.

Основу правовыводимой цепочки можно было определить другим способом в терминах деревьев вывода.

Основа - это крона самого левого поддерева глубины 1 некоторого дерева вывода заданной правовыводимой цепочки.

Дерево глубины 1, состоящее из вершины и ее прямых потомков, которые являются листьями, называется кустом или веером.

Дерево вывода цепочки a+aa в грамматике G₀ показано на рис 6.2 (а). Самый левый куст состоит из самой левой вершины, помеченной F, которая является его корнем, и кроны a.

Если удалить единственный лист самого левого куста, то останется дерево, показанное на рис. 6.2 (б). Крона F+aa этого дерева и есть результат левой свертки цепочки a+aa, а его основа - крона F поддерева с корнем, помеченным T. Опять удалив основу, получим дерево на рис 6.2 (в).

Описанный процесс свертки деревьев называется отсечением основ.

По КС-грамматике G можно построить эквивалентный расширенный МП-автомат R, работа которого заключается в отсечении основ. Здесь удобно представлять себе магазин в виде цепочки, верхним символом которой является самый правый, а не самый левый символ. В силу этого, отношение перехода  в этом автомате будет определятся несколько иначе. Если  (q, a,  ) содержит (p,  ), то будем писать

(q, a ,  )  (p,  ,  )

для всех    ^ и    ^.

В дальнейшем, если не оговорено противное, будем считать, что у обычного МП-автомата (нисходящего анализатора) верх магазина расположен слева, а у расширенного (восходящего анализатора) - справа.

Теорема 6.3. Пусть G=(, , P, S) - КС-грамматика. По G можно построить такой расширенный МП-автомат R, что L(R) = L(G).

Эта теорема является следствием теорем 6.1 и 6.2, но здесь интересна сама конструкция расширенного МП-автомата R, который и моделирует процесс отсечения основ. Итак

R = ({q, r},  ,     {$},  , q, $, {r})

- расширенный МП автомат, где по соглашению верх магазина расположен справа, и, в котором  определяется следующим образом:

(1)  (q, a,  ) = {(q, a)} для всех a  . (На этих тактах входные символы переносятся в магазин.)

(2) Если A   принадлежит P, то  (q,  ,  ) содержит (q, A). (В случае, когда в верхней части магазина окажется правая часть некоторой продукции эта правая часть может быть заменена левой частью соответствующего правила без движения по входной ленте.)

(3)  (q,  , $S) = {(r,  )}. (Если вся входная цепочка прочитана и в вершине магазина только начальный символ грамматики, автомат переходит в заключительную конфигурацию.)

Можно показать, что процесс вычисления в автомате R заключается в построении правовыводимых цепочек грамматики G, начиная с терминальной цепочки (на входе R) и кончая цепочкой S. 

Пример 6.5. Построим “восходящий” расширенный автомат R для грамматики арифметических выражений G₀ . Пусть R = ({q, r},  , ,  , q, $, {r}), где  определяется так:

(1)  (q, b,  ) = {(q, b)} для всех b {a, +, , (, )};

(2)  (q,  , E+T) = {(q, E)}

 (q,  , T) = {(q, E)}

 (q,  , TF) = {(q, T)}

 (q,  , F) = {(q, T)}

 (q,  , (E)) = {(q, F)}

 (q,  , a) = {(q, F)};

(3)  (q,  , $E) = {(r,  )}.

Для входа a+aa распознаватель может сделать следующую последовательность тактов:

(q, a+aa, $)  (q, +aa, $a)

 (q, +aa, $F)

 (q, +aa, $T)

 (q, +aa, $E)

 (q, aa, $E+)

 (q, a, $E+a)

 (q, a, $E+F)

 (q, a, $E+T)

 (q, a, $E+T)

 (q,  , $E+Ta)

 (q,  , $E+TF)

 (q,  , $E+T)

 (q,  , $E)

 (r,  ,  )

Заметим, что для входа a+aa распознаватель R может сделать много различных последовательностей тактов. Однако представленная последовательность - единственная, которая переводит начальную конфигурацию в заключительную. 

Покажем теперь, что язык, определяемый МП-автоматом, контекстно-свободен.

Теорема 6.4. Пусть R = (Q,  , ,  , q₀ , Z₀ , F) - МП-автомат. Можно построить такую КС-грамматику G, что L(G) = L(R).

Доказательство. Построим G так, чтобы левый вывод цепочки  в грамматике G прямо соответствовал последовательности тактов, которую делает R при обработке цепочки . Нетерминальные символы будут иметь вид < qZr>, где q, r Q и Z .

Формально пусть G = ( ,  , P, S), где

(1)  = {< qZr>  q, r Q, Z  } {S};

(2) правила множества P строятся так:

(а) если  (q, a, Z) содержит (r, X₁ ... X_k) (k  0), добавим к P все правила вида

< qZs_k >  a< rX₁ s₁ ><s₁ X₂ s₂ > ... <s_k-1 X_k s_k >

для каждой последовательности s₁ , s₂ , ... , s_k состояний из Q,

(б) если  (q, a, Z) содержит (r,  ), добавим к P правило < qZr >  a,

(в) добавим к P правила S  < q₀ Z₀ q > для каждого q Q.

Индукцией по m и n можно доказать, что для любых q, r Q Z 

< qZr>  ^m  тогда и только тогда, когда (q,  , Z)  ⁿ (r,  ,  ).

Из этого утверждения следует, что

S < q₀ Z₀ q >  ⁺ 

тогда и только тогда, когда

(q₀ ,  , Z₀ )  ⁺ (r,  ,  )

для q Q. Таким образом L(R) = L(G). 

Результаты данного раздела можно сформулировать в виде следующей теоремы:

Теорема 6.5. Утверждения

(1) L = L(G) для КС-грамматики G,

(2) L = L(R₁) для МП-автомата R₁,

(3) L = L(R₂) для расширенного МП-автомата R₂.

эквивалентны.

Доказательство. Из (2) следует (1) по теореме 6.4. Из (1) следует (2) по теореме 6.2. Из (3) следует (2) по теореме 6.1, а (3) тривиально следует из (2). 