гл. 3. ТЕОРИЯ ПЕРЕВОДА

Рис. 3.4. Граф переходов.

ственное различие между парами q, q и q, q состоит в том, что если символу. а предшествует четное число минусов, то первая из них выдает --а, а не только а.

Для входа ~аЛ--й--!-а последовательность тактов пре-

эбразователя Ы. такова;

too» -а + -fl-+ -о, а + -+ е)

f-Л-а-+ -а, -а)

Н(2» -й--1---

Ь(?з. <--а, -а)

+ -Д. -а~а) Hto* -а, -а-а)

G, - а-а) \-(qi, е, а-а + а)

Отсюда ясно, что М отображает цепочку -а-]--а--[--а в

- а-а-а, поскольку q - заключительное состояние, П

Конечный преобразователь М назовем детерминированным если для всех qQ

(1) либо б(, а) содержит не более одного элемента для каждого й 2 и 6 ((jf, пусто, либо

(2) б {q, е) содержит один элемент и б а) пусто для всех

В примере 3.8 конечный преобразователь детерлшпированпый. Заметим, что детерминированный конечный преобразователь может давать несколько переводов для одного входа.

Пример 3.9. Пусть M = ({9o, J, {а), {Ь\, б, q, и б а) = -{(1.)}> Тогда

h-{q„e,b)

- допустимая последовательность тактов для всех iO. Таким образом, r{M) = {{a,b)\i-\}. □

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

Для HCKOTOj)bix классов языков можно получить ряд свойств замкнутости, если рассматривать преобразователи как операторы, определенные на языках. HanpiiMep, если М - конечный преобразователь и язык L содержится в области определения отношения х{М), то полагаем

M(L){y\xL и (ХуУ)т(М)}

Можно также определить обратное конечное преобразование, а именно, если М -конечный преобразователь, положим ()- =={x\yL и {х,у)ех(М)\.

Нетрудно показать, что конечные преобразования (прямые и обратные) сохраняют свойства регулярности и контекстной свобод-ности. Иными словами, если L-регулярное множество (КС-язык) и М-конечный преобразователь, то M(L) и M~(L) - регулярные множества (КС-я:ыки). Доказательства этих фактов оставляем в качестве упражнений. С их помощью можно доказать, что некоторые языки не регулярны (или не контекстно-свободны).

Пример 3.10. Язык, порождаемый грамматикой G с правилами

5~if5then5a не регулярен. Обозначим

L = L (G) П (ii)* а (then g)* = {(if)" а (then й)« 1 п >0} Рассмотрим конечный преобразователь A1 = {Q, 2, А, б, д, F), где

О) Q = {Яi\0<i<Щ,

(2) I={a,i, f, t,h, V,nf,

(3) A-{О, U,

(4) б определяется диаграммой, изображенной на рис. 3.5,

(5) f = {?.}.

А. Лхо, Дж. Ульман, т. I 257

Здесь "е" означает букву е в отличие от пустой цепочки. Таким образом, М (LJ = (0*1* ft >0J, а это, как мы знаем, не регулярное множество. Так как класс регулярных множеств замкнут относительно пересечения и конечных преобразований, то L(G) не регулярное множество. □

Рис. 3.5. Диаграмма преобразователя М.

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

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

Определение. Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P~(Q, S, Г, Д, б, а, ai) где все символы имеют тот же смысл, что в определении МП-автомата, за исключением того, что Д - конечный выходной алфавит, а 6-отображение множества Qx(2u{)xr в множество конечных подмножеств множества QxFxA*.

Определим конфигурацию преобразователя Р как четверку {q X, а, у), где х и а те же, что у МП-автомата, а у - выходная цепочка, выданная вплоть до настоящего момента. Если 6 (9, а, Z) содержит (г, а, г), то будем писать [q, ах, Zy, у)\- {г, X, ау, yz) для любых xgS*, у € Г* и уА*-

Цепочку у назовем выходом для х, если {q,, х, Z, е)1-*((?, е, о:, у) длянекоторых qF и аГ*. Переводом (или преобразованием), определяемым Мй-преобразователем Р (обозначается г(Р)), назовем множество

{( у) I 2о, е) \-* [q, е, а, у) для некоторых qF и а С Г*}

Аналогично МП-автоматам можно говорить о преобразовании входа X в выход у опустошением магазина, если (q, х, Z, е)\-* {q,e,e,y) для некоторого qQ. Переводом, определяемым преобразователем Р опустошением магазина (обозначается (Р)),

назовем множество

{{X, у) I (?о, > -0. ) to. у) ДЛЯ некоторого д € Q)} Аналогично расширенным МП-автоматам можно определить расширенные МП-преобразователи (у них верх магазина расположен справа).

Пример зли Рассмотрим МП-преобразователь P{{q}, {+.*,-£}. {а, 6,q,E, {q})

где 6 определяется равенствами

6(9, а, £)={(?, е, а)} b{q, Jr,E) = {{q, ЕЕ-{-,е)) b(q,.,E) = \(q,EE,e)} {Я. е, +){{q,e, +)} (Я, . *) = {to, »)[ Для входа --ааа МП-преобразователь Р сделает такую последовательность тактов:

{q, + if-aaa, Е, е) \-{д, * ааа, ЕЕ +, е) 1-(9, ааа, ЕЕ * Е -f, с) [-{q,aa,E*E а) [~{q,a,*E + , аа) 1-(9, а, £ + , аа *) \- (я* е, 4-, аа * а) y-(q, е, е,аа*а -f)

Таким образом, Р переводит цепочку + * ааа в цепочку аа»а +» опустошая магазин. Можно проверить, что

т(Р) -{(х, у)\х - префиксное польское арифметическое выражение в алфавите ( + , а} и у-соответствующая постфиксная польская запись)- П

Определение. Если P-:(Q,S, Г, \,6,q,Z, f) -МП-преобразователь, то МП-автомат (Q, 2, Г, 6, q, Z, F), где 6 (q, а, Z) содержит {г, у) тогда и только тогда, когда 6{q,a,Z) содержит t Y. у) для некоторого у, назовем МП-автоматом, лежаиим б основе преобразователя Р (нли просто основой Р).

Будем говорить, что МП-нреобразователь Р -(Q, 2, Г, Л, б, о, 0. F) детерминированный (ДМП-преобразователь), если

(О для всех qQ, о 2U {е} и Z6Г множество {q,a,Z) одержит не более одного элемента, 9*

1 ./i. 1 tnjFMH ПЕРЕВОДА

(2) если b(q,ey 1)Ф0, то Ь{д, а, Z) = 0 для всех а2),

Очевидно, что если L-область определения отношения т(р) для некоторого МП-преобразователя Р, то L~L{P), где Р - МП-автомат, лежаш.ий в основе Р.

Многие из результатов, доказанных в разд. 2.5 для МП-автоматов, естественным образом распространяются на МП-преобразователи. В частности, аналогично леммам 2.22 и 2.23 можно доказать следующую лемму.

Лемма 3.1. Т~т(Р) для МП-преобразователя Р тогда и только тогда, когда Т~т(Р) для подходяиго MU-преобразо-вателя Р.

Доказательство. Упражнение. П

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

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

Лемма 3.2. Пусть 7(N, 2, Д, R, S) - простая СУ-схема. Существует такой МП-преобразователь Р, что Тр(Я)т(Г).

Доказательство. Пусть С,--входная грамматика схемы Т. Построим Р так, чтобы он распознавал сверху

вниз, как в лемме 2.24.

При моделировании правила Л-+а, р схемы Г преобразователь Р заменит в магазине верхний символ Л цепочкой а, в которую вставлены выходные символы из цепочки р, т. е. если а = Х(,Лх, ... Л„х, и )УоЛгУ1 • то символ Л будет

заменен цепочкой Х(уЛху ... Аху. Надо уметь, однако, отличать символы алфавита 2 от символов алфавита Д, чтобы можно было правильно разбивать цепочки х,у,- на две части. Если S и Д не пересекаются, то никакой проблемы нет. В общем случае определим новый алфавит А, соответствующий Д, но заведомо не пересекающийся с S. Будем считать, что Д состоит

) Заметим, что это определение несколько сильнее утверждения о том, что лежащий в основе МП-автомат дстерминнрованный. Последнее может быть и тогда, когда (1) не выполняется из-за того, что МП-преобразователь может выдать два разных выхода на двух шагах, которые во всем остальном совпадают. Заметим также, )то из условия (2) следует, что если 6{q, a,Z) = 0 для некоторого 2, то b{q, е, Z)i3.

из новых символов а, соответствующих аЛ. Тогда ДП2=0 и естественно определить такой гомоморфизм h, чток(а) = а

пля каждого а€ Д-

Пусть 2, NUXUA, Д, б, 9, S, 0), где 6 определя-

ется так:

(1) если АхВх ... BXf,, уВу . -. 6/ -правило из R для >0, то 6(t/, е. Л) содержит (9, Xof/oSj.i; ... SftXftf/ft, в), где yih(yi) для 0<t<;

(2) b{q,a,o) ~{(q,e,e)) для всех а 2;

(3) Hq,e,a) = {{q,e,a)) для всех сД.

Индукцией по m и /г можно показать, что для ЛN н т, /11 справедливо следующее утверждение: (3.1.3) (Л, А)="(х, у) для некоторого т тогда и только тогда, когда (q, X, Л, е)\-" {q, е, е, у) для некоторого п.

Необходимость. Базис, т=\, выполняется тривиально, так как правило А~-*х,у должно принадлежать R. Тогда (9, х, Л, е) I- {q, X, xh (у), е) (q, е, h (у), е) [-* {q, е, е, у).

Для доказательства шага индукции допустим, что (3.1.3) справедливо для значений, меньших т, и пусть (Л, Л) =ф (XpBiXj ... SftXft, уВ.у, .. . ВУп)"" {X, у). Так как в простой СУ-схеме порядок вхождений нетерминалов не меняется, можно писать x = X(,WjXi. . -WftXj и у = У(РгУг - • - Ук» причем {Bt, Bi)"i («,-, f,) для Xik, где /7z<m для каждого /. Таким образом, по предположению индукции {q, и-, Bi, е)* (q, ееи). Объединяя эти последовательности тактов, получаем

(й, X, Л, е) Ь (9, X, Xoh (0) 1 - - • Ef,Xf,h [у), е)

Ь* (q, их ... WftXft, h (Уо) В ... Bf,x„ h (у). е) Н*((?. uXi . .. пхд, В ... BfXkh{y), (/,) [-*(. -1 • • Л. xMyi) ftV(ft), y<ii} h* ... (q, e, e, y)

Достаточность. Опять базис, nl, тривиален, так как правило Л-е должно принадлежать R. Для доказательства Шага Индукции допустим, что первый такт преобразователя Р Имеет вид

to. х,А,е) I- {q, X, xh (у) Bxji (i/J ... BfXfJt {y), e)

где 2*, (/,-Д*, ?i(£/,) Д*. Тогда цепочка Xq должна быть префиксом цепочки х и на следующих тактах работы преобразователя Р цепочка х будет прочитана на входе и устранена из агазина, а затем на выходе будет выдана цепочка у,. Пусть X оставшаяся часть входной цепочки. Тогда цепочка х должна >летъ префикс и, который приводит к тому, что магазинные