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

Детерминированные МП-автоматы и КС-языки

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

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

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

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

(1) d (q, a, Z) содержит не более одного элемента для каждого a Î S и d(q, e, Z)=Æ, либо

(2) d (q, a, Z) = Æ для всех a Î S и d (q, e, Z) содержит не более одного элемента.

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

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

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

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

d (q₁, x, x) = (q₁, e) для всех xÎ {a, b}

d (q₁, e, Z) = (q₂, e)

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

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

(1) d (q, a, g) содержит не более одного элемента для всех q Î Q, a Î S È {e } и gÎG ^*;

(2) если d (q, a, a) ¹ Æ, d (q, a, b) ¹ Æ и a ¹ b, то ни одна из цепочек a и b не является суффиксом другой;

(3) если d (q, a, a) ¹ Æ и d (q, e, b) ¹ Æ, то ни одна из цепочек a и b не является суффиксом другой.

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

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

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

R = (Q, S, G, D, d, q₀, Z₀, F),

где все символы имеют тот же смысл, что и в определении МП-автомата, за исключением того, что D - конечный выходной алфавит, а d - отображение конечного подмножества множества Q ´(SÈ{e})´G ^* в множество конечных подмножеств множества Q ´G ^* ´ D ^*.

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

(q, aa, Zg, x) ú¾ (r, a, bg, xz)

для любых a Î S ^*, g Î G ^* и x Î D ^*.

Цепочку x называют выходом для a, если (q₀, a, Z₀, e) ú¾ ^* (q, e, b, x) для некоторых q Î F и bÎ G ^*. Переводом (или преобразованием), определяемым МП-пре­об­ра­зо­ва­те­лем R (обозначается t (R) ), называется множество

{(a, x) ½ (q₀, a, Z₀, e) ú¾ ^* (q, e, b, x) для некоторых q Î F и bÎ G ^* }

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

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

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

(1) d (q, a, e) = {(q, a, a)} для всех bÎ {a, +, *, (,)};

(2) d (q, b, e) = {(q, b, e)} для всех bÎ { +, *, (,)};

(2) d (q, e, E+T) = {(q, E, +)}

d (q, e, T) = {(q, E, e)}

d (q, e, T * F) = {(q, T, * )}

d (q, e, F) = {(q, T, e)}

d (q, e, (E)) = {(q, F, e)}

d (q, e, a) = {(q, F, e)};

(3) d (q, e, $E) = {(r, e, e)}.

Для входа 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, $E+T * a, aaa)

ú¾ (q, e, $E+T * F, aaa)

ú¾ (q, e, $E+T, aaa * )

ú¾ (q, e, $E, aaa * +)

ú¾ (r, e, e, aaa * +)

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

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

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

Пусть G=( N, S, P, S) - КС-грамматика, правила которой занумерованы 1, 2,..., p. Пусть a Î (NÈS) ^*. Тогда

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

(2) правым разбором цепочки a называется обращенная последовательность правил, примененных при правом выводе цепочки a из 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=( N, S, P, S) - КС-грамматика, правила которой занумерованы от 1 до p. Пусть M_L - недетерминированный МП преобразователь

M_L = ({q}, S, NÈS, {1, 2,..., p}, d, q, S, Æ)

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

(1) d (q, e, A) содержит (q, a, i), если A ® a правило из P с номером i,

(2) d (q, a, a}= {(q, e, e)} для всех a Î S.

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

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

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

M_L = ({q}, S, NÈS, {1,2,3,4,5,6}, d, q, E, Æ)

где

d (q, e, E) = {(q, E+T, 1), (q, T, 2)}

d (q, e, T) = {(q, T * F, 3), (q, F, 4)}

d (q, e, F) = {(q,(E), 5), (q, a, 6)}

d (q, b, b) = {(q, e, e)} для всех bÎ S

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

(q, a+a * a, E, 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, e, e, 12463466) œ

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

M_R = ({q}, S, NÈSÈ {$}, {1, 2,..., p}, d, q, $, Æ)

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

(1) d (q, e, a) содержит (q, A, i), если A ® a правило из P с номером i,

(2) d (q, a, e}= {(q, a, e)} для всех a Î S,

(3) d (q, e, $S}= {(q, e, e)}.

Преобразователь 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}, S, NÈSÈ {$}, {1, 2,3,4,5,6}, d, q, $, Æ)

где

d (q, e, E+T) = {(q, E, 1)}

d (q, e, T) = {(q, E, 2)}

d (q, e, T * F) = {(q, T, 3)}

d (q, e, F) = {(q, T, 4)}

d (q, e, (E)) = {(q, F, 5)}

d (q, e, a) = {(q, F, 6)}

d (q, b, e) = {(q, b, e)} для всех bÎ S

d (q, e, $E) = {(q, e, e)}

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

(q, a+a * a, $, e) ú¾ (q, +a * a, $a, e)

ú¾ (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, $E+T * a, 64264)

ú¾ (q, e, $E+T * F, 642646)

ú¾ (q, e, $E+T, 6426463)

ú¾ (q, e, $E, 64264631)

ú¾ (q, e, e, 64264631)

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

Дата добавления: 2015-06-27