6. 3. Детерминированные мп-автоматы и кс-языки

Из теорем раздела 6.2 следует, что для каждой КС-грамматики G можно построить МП-автомат, распознающий L(G). Однако построенные МП-автоматы были недетерминированными. В практических приложениях больший интерес представляют детерминированные МП-автоматы, т.е. такие, которые в каждой конфигурации могут сделать не более одного очередного такта. К сожалению, детерминированные МП-автомоты не так мощны по своей распознавательной способности, как недетерминированные МП-автоматы. Существуют КС-языки, которые нельзя определить детерминированными МП-автоматами.

Язык, определяемый детерминированным МП-автоматом, называется детерминированным КС-языком.

Во второй части пособия будут рассмотрены подклассы КС-грамматик (LL(k)- и LR(k)- грамматики), порождающие детерминированные КС-языки. Все известные языки программирования могут определяться этими грамматиками. Пока же остановимся на определениях и примерах детерминированных автоматов.

МП-автомат R = (Q,  , ,  , q₀ , Z₀ , F) называется детерминированным (ДМП-автоматом), если для каждых q Q и Z  либо

(1)  (q, a, Z) содержит не более одного элемента для каждого a  и (q,  , Z)=, либо

(2)  (q, a, Z) =  для всех a  и  (q,  , Z) содержит не более одного элемента.

В силу этих ограничений ДМП-автомат в любой конфигурации может выбрать не более одного такта. Так как у ДМП-автоматов  (q, a, Z) содержит не более одного элемента, для них можно писать  (q, a, Z)=(r,  ) вместо  (q, a, Z)={(r,  )}.

Пример 6.6. Построим ДМП-автомат, распознающий язык L={ c ^R   {a, b} ⁺}. Пусть R = ({q₀, q₁, q₂}, {a, b, c}, {Z, a, b},  , q₀, Z, {q₂}), где  определяется так:

 (q₀, x, y) = (q₀, xy) для всех x {a, b} и y {Z, a, b}

 (q₀, c, y) = (q₁, y) для всех y {a, b}

 (q₁, x, x) = (q₁,  ) для всех x {a, b}

 (q₁,  , Z) = (q₂,  )

До тех пор пока R не увидит маркер c, отмечающий середину, он записывает в магазин символы входной цепочки. Когда R достигает c, он переходит в состояние q₁ и далее сравнивает оставшуюся часть входной цепочки с содержимым магазина. 

Расширенный МП-автомат R = (Q,  , ,  , q₀ , Z₀ , F) называется детерминированным, если выполняются следующие условия:

(1)  (q, a, ) содержит не более одного элемента для всех q Q, a   { } и   ^ ;

(2) если  (q, a, )   ,  (q, a, )   и    , то ни одна из цепочек  и  не является суффиксом другой;

(3) если  (q, a, )   и  (q,  , )   , то ни одна из цепочек  и  не является суффиксом другой.

Заметим, что речь в последнем определении идет о суффиксах цепочек магазина, так как в расширенном МП-автомате верхний символ магазина - это самый правый символ цепочки.

6. 4. Преобразователи с магазинной памятью

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

Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка

R = (Q, , , , , q₀, Z₀, F) ,

где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что  - конечный выходной алфавит, а  - отображение конечного подмножества множества Q({}) ^ в множество конечных подмножеств множества Q ^  ^.

Определим конфигурацию преобразователя R как четверку (q, , , ), где q,  и  те же, что у МП-автомата, а  выходная цепочка, выданная к данному моменту. Если  (q, a, Z) содержит (r,  ,  ), то будем писать

(q, a , Z ,  )  (r,  ,  ,  )

для любых    ^,    ^ и    ^.

Цепочку  называют выходом для  , если (q₀, , Z₀,  ) ^ (q, , ,  ) для некоторых q F и   ^. Переводом (или преобразованием), определяемым МП-пре­об­ра­зо­ва­те­лем R (обозначается  (R)), называется множество

{(, ) (q₀, , Z₀,  ) ^ (q, , ,  ) для некоторых q F и   ^}

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

Пример 6.7. Рассмотрим расширенный МП-преобразователь

R = ({q, r}, {a, +, , (, )} , {E, T, F, a, +, , (, ), $},  , q, $, {r}), где  определяется так:

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

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

(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 преобразователь R может сделать следующую последовательность тактов:

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

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

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

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

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

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

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

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

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

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

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

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

 (q,  , $E, aaa+ )

 (r,  ,  , aaa+)

Таким образом R переводит цепочку a+aa в цепочку aaa+.

Преобразователь R построен на базе расширенного МП-автомата из примера 6.5. и осуществляет восходящий анализ арифметических выражений по грамматике G₀ с переводом традиционных инфиксных выражений в польскую инверсную (постфиксную или суффиксную) запись (ПОЛИЗ). ПОЛИЗ - это одна из традиционных внутренних (для компилятора) форм исходной программы, где арифметические выражения не содержат скобок и знаки операций располагаются за операндами над которыми они выполняются в порядке их выполнения. Подробно ПОЛИЗ, методы перевода в ПОЛИЗ и возможности использования ПОЛИЗа будут рассмотрен во второй части пособия. 

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

Пусть G=(, , P, S) - КС-грамматика, правила которой занумерованы 1, 2, ..., p. Пусть   () ^. Тогда

(1) левым разбором цепочки  называется последовательность правил, примененных при левом выводе цепочки  из S,

(2) правым разбором цепочки  называется обращенная последовательность правил, примененных при правом выводе цепочки  из S.

Эти разборы можно представить в виде последовательности номеров из множества {1, 2, ... , p}.

Пример 6.8. Рассмотрим грамматику арифметических выражений G₀ с такой нумерацией правил:

(1) E  E+T

(2) E  T

(3) T  TF

(4) T  F

(5) F  (E)

(6) F  a

Левый разбор цепочки a (a+a) - это последовательность 23465124646, а правый разбор - 64642641532. 

Нетрудно убедится в том, что МП-преобразователи, построенные по КС-грамматикам могут быть напрямую связаны с разбором.

Пусть G=(, , P, S) - КС-грамматика, правила которой занумерованы от 1 до p. Пусть M_L - недетерминированный МП преобразователь

M_L = ({q}, , , {1, 2, ... , p}, , q, S, )

где  определяется так:

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

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

Преобразователь M_L называется левым анализатором для G.

Основа левого анализатора конечно же МП-автомат из теоремы 6.2, моделирующий левые выводы по грамматике G. По правилам (1) M_L каждый раз “развертывает” нетерминал, расположенный наверху магазина, в соответствии с некоторым правилом из P и одновременно выдает номер этого правила. Если наверху магазина находится терминальный символ, то M_L по правилу (2) проверяет, совпадает ли он с текущим входным символом.

Пример 6.9. Построим левый анализатор по грамматике G₀. Здесь

M_L = ({q},  ,  , {1,2,3,4,5,6},  , q, E,  )

где

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

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

 (q,  , F) = {(q,(E), 5), (q, a, 6)}

 (q, b, b) = {(q, , )} для всех b 

Для входной цепочки a+aa левый анализатор может среди других сделать такую последовательность тактов:

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

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

 (q, a+aa, F+T, 124)

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

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

 (q, aa, T, 1246)

 (q, aa, TF, 12463)

 (q, aa, FF, 124634)

 (q, aa, aF, 1246346)

 (q, a, F, 1246346)

 (q, a, F, 1246346)

 (q, a, a, 12463466)

 (q,  ,  , 12463466) 

Пусть G=(, , P, S) - КС-грамматика, правила которой занумерованы от 1 до p. Пусть M_R - расширенный недетерминированный МП преобразователь

M_R = ({q}, ,  {$}, {1, 2, ... , p}, , q, $, )

причем верх магазина расположен справа и  определяется так:

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

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

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

Преобразователь M_R называется правым анализатором для G.

Правый анализатор M_R строится по той же схеме, что и расширенный МП-автомат из теоремы 6.3. Преобразователь M_R содержит элементы алгоритма разбора, называемого алгоритмом типа “перенос - свертка”. На такте, соответствующем правилу (2), M_R переносит входной символ в магазин. Всякий раз, когда наверху магазина появляется основа, M_R может свернуть ее по правилу (1) и выдать номер правила, использованного при свертке. Чередование переноса и свертки происходит до тех пор, пока в магазине не останется только начальный символ с маркером дна магазина. По правилу (3) M_R может тогда перейти в заключительную конфигурацию с пустым магазином.

Пример 6.10. Правым анализатором для грамматики G₀ из примера 6.8 будет

M_R = ({q}, ,  {$}, {1, 2,3,4,5,6}, , q, $, )

где

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

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

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

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

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

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

 (q, b,  ) = {(q, b,  )} для всех b 

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

Для входной цепочки a+aa анализатор M_R может сделать среди других такую последовательность тактов:

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

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

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

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

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

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

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

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

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

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

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

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

 (q,  , $E, 64264631)

 (q,  ,  , 64264631)

Таким образом, для цепочки a+aa анализатор M_R выдает правый разбор 64264631. 