Главная Промышленная автоматика.

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

СИМВОЛЫ, расположенные на уровне символа и выше, устраняются из магазина. При этом к моменту, когда длина магазина становится меньше \Ву ... В1хф{у)\, на выходе выдается цепочка с. Тогда (q, Uy, By, ё)\-[q, е, Vy), и соответствующая последовательность состоит менее чем из п тактов. По предположению индукции (By, Vy).

Рассуждая таким образом, мы приходим к тому, что х можно записать в виде xUyXy ... «х, а (/ - в виде • кУн при-

чем (Bf, 0;) для l<i<fc. Так как правило

А-хВуХу ... BXk, УВуУу ... Bf,y, очевидно, принадлежит то (Л, Л)=*(х, У).

В качестве частного случая утверждения (3.1.3) имеем (S, S) * (х, у) тогда и только тогда, когда (q, х, S, е) j-* {q, е, е, у), так что т(Р) = т(Г). □

Пример 3.12. От простой СУ-схемы с правилами.. E-i-EE, ЕЕ + Е-ЕЕ, ЕЕ Е-уй, а

можно перейти к эквивалентному МП-преобразователю РИя} {«. +--}. «. + ,х.,й,+,}, {й,+.*Ьб,?., 0) где б определяется равенствами

(1) 6(9, в, £)-{(?, +ЕЕу,е), {q,EE,e), {q,aa\e)},

(2) б [q, b, b) = {(q, e, e)} для всех b£{a, -f, »},

(3) б (q, €, b) = {(<?, e, b)] для всех b£{a, +. *}•

Это недетерминированный МП-преобразователь. Эквивалентный ему детерминированный МП-преобразователь приведен в примере 3.11. □

Лемма 3.3. Пусть P{Q, 2, Г, Д, б, q, Z, F)~МП-преобразователь. Существует такая простая СУ-схема, что т(Г)

Доказательство. Построение схемы аналогично построению КС-грамматики по МП-автомату. Пусть T = (N, S, Д, R, 5), где

(1) ={[pAq]\p,q£Q,A£r}U{S},

(2) R определяется так:

(а) если б(р, а, А) содержит (г, Ху Х .,. Л, у)у то при к>0 ъ R входят правила

[pAqj,]~a[rXygy][qyX,q,] ... [qk-iXql

y[rXyqy][qyX,q,] . . . [-Лй]

,.1. .onnrirv для ОПРЕДЕЛЕНИЯ ПЕРЕВОДА

для всех последовательностей qy,q,...,q состояний из Q, а при fe -О в R входит одно правило [рЛг]->а, у; (б) для каждого qQ в R входит правило S-~[qZq],

Ясно, что Т-простая СУ-схема. Снова индукцией по т и по п легко доказать, что

(3.1.4) ilpAq], [pAq])="ix, у) тогда и только тогда, когда [р, X, Л, e)y-4q, е, е, у) для всех p,q£Q и ЛГ.

Доказательство утверждения (3.1.4) оставляем в качестве упражнения.

Таким образом, (S, S) => ([ЗД, [f/.Z?]) =>+(х, у) тогда и только тогда, когда (q, х, Z, е) у-- (q, е, е, у). Следовательно, т(Г)тЛР). □

Пример 3.13. С помощью конструкции предыдущей леммы построим по МП-преобразователю из примера 3.11 .эквивалент-н)1о ему простую СУ-схему. Получим СУ-схему Т= (N, {а, +, »}, R,S), где N-{[9X9] + -(}и{5), асостоит

из правил

SiqEql [qEq-\ [qEq]a, а

[qEq] -> + [qEq] [qEq] [9 -j- 9], [qEq] [qEq] [q -f 9] [qEq] * [qEq] {qEq [9 « 9], [qEq] {qEq~\ [9 * 9]

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

S-a, а

5 -> к- 55, 55 * □

Теорема 3.2. Т - простой CY-перевод тогда и только тогда, когда Тт{Р) для некоторого МП-преобразователя Р.

Доказательство. Теорема непосредственно следует из лемм 3.1-3.3. □

В гл. 9 мы введем машины, называемые процессорами с магазинной памятью, способные определять любые синтаксически Управляемые переводы.



ГЛ. 3. ТЕОРИЯ ПЕРЕВОДА

УПРАЖНЕНИЯ

3.1.1. Операция!) с одним аргументом называется унарной, с двумя-бинарной, и вообще операция с п аргументами называется п-арной (или п-местной). Например, операция - может быть унарной (как в-д) и бинарной (как в а-Ь). Число аргументов операции иногда называют ее арностью (или местностью). Пусть в-множество операций с заданными арностями и 2 - множество операндов. Постройте КС-грамматики (j и G, порождающие префиксные и постфиксные польские записи выражений, составленных из операций множества в н операндов множества 2.

*3.1.2. „Предшествование" (приоритет) инфиксных операций определяет порядок, в котором они выполняются. Если бинарная операция „предшествует" операции д, то аОЬвс вычисляется как aG(66jC). Например, » предшествует и потому аЬас означает д 4-(*), а не {a-\~b)ii-c. Рассмотрим булевы операции ~] (не), Л (и), V (или), (импликация) и = (эквивале1щия), Эти операции перечислены в том порядке, в каком они предшествуют друг другу. Операция ~-унарная, а остальные - бинарные. Например, в выражении ] {а\/Ь)= ~] а А ~\ Ь подразумевается такая расстановка скобок: ("] {а\/Ь))({ ~1 а)/\ ( ~] Ь)). Постройте КС-грамматику, порождающую все правильные булевы выражения, составленные из этих операций и операндов а, Ь, с и не содержащие избыточных скобок.

*3..3. Постройте простую СУ-схему, отображающую инфиксные булевы выражения в префиксные.

*3.1.4. В Алголе выражения строятся с помощью операций, перечисленных ниже в порядке их приоритетов. Если операций одрюго приоритета более одной, то они выполняются в порядке слева направо. Например, а - Ь-\~с означает {а - Ь)-\-с.

(1) t (2) X / (3) -f

(4)< < > > (5) 1 (6) Л

(7) V (8) (9)

Постройте простую СУ-схему, которая отображает инфиксные выражения, содержащие эти операции, в их постфиксные польские записи.

) Здесь н в дальнейшем мы будем называть операциями как сами опрпа-цаи (например, арифметические), так и знаки операций. Надеемся чтп .tn up вызовет недоразумений.-Ярмж. ред.

3.1.5. Рассмотрим следующую СУ-схему, в которой цепочка вида <л:> озпач1хет один нетерминал:

<ехр> sum <ехр>< with <var> <ехр><2 to <ехр><з, i) bQgin local i;

tor <var> -<-<exp>2) to <exp>* do if-/-f <exp>i; resuHt

-<id>, <id>

-><id>, <id> -G<id>, G<id> ~&<id>, b<id> a, a b, b

<var> -<exp>-<id>-<id>-<id>-<id>-

Постройте переводы предложений

а) sum аа with a-b to bb

б) sum sum a with aa<~aaa Xoaaaa with b-t-bb tobbb *3.1.6. Рассмотрим такую схему трансляции: <statement> - for <var> <exp>* to <exp>=* do <statement>,

begin <var>-*- <exp>; L: tf <var><exp>2then begin <stateraent>;

<var> -<var> + 1 go to L

-<id>, <id> <id>, <id> ~<var><exp>, <var>-->a<id>, G<id> ->fo<id>, b<id> ->-a, a b, b

-<exp>

<var>-<exp> <statenient> -<id> <id> <id> <id>

Почему эта схема не является СУ-схедюй? Каким должен быть выход для входного предложения

iora-f-b to аа do baa-( bba

1) Обратите вннмапие. что эта запятая отделяет две части правила.



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

Указание: Примените алгоритм 3.1, дублируя в выходном дереве вершины, помеченные <var>.

Упражнения 3.1.5 и 3.1.6 дают примеры того, как с помощью синтаксических макросов можно расширять язык. В приложении П1 подробно показано, как включить в язык такой механизм расширения.

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

3.t.8. Пусть L-КС-язык и S* - регулярное множество. Постройте такую СУ-схему Т, что

т(Г) = {(л:, у)\ если x£L~~R, то у = 0, если x£L{R, то у=\} *3.t.9. Постройте такую СУ-схсму Т, что 1(Т) = {{х, у)\х£{а, Ь}* и у- с, где

W-#&WI и -число

символов d в цепочке х\

*3.1.10. Покажите, что если L - регулярное множество и М - конечный преобразователь, то М (1) и /"{L) - регулярные множества,

*3.1.И. Покажите, что если L - КС-язык и М - конечный преобразователь, то М (L) и (L) - КС-языки.

*3.l.i2. Пусть R - регулярное множество. Постройте такой конечный преобразователь М, что М (L) - L/R для любого языка L. Учитывая упр. 3.1.10 и 3.1.11, заключаем отсюда, что классы регулярных множеств и КС-языков замкнуты относительно операции /R (деление справа на регулярное множество).

*3.1.13. Пусть R - регулярное множество. Постройте такой

конечный преобразователь Л1, что М Щ - R/L для любого языка L.

3.1.14. СУ-схема T{N, S, Д, R, S) называется праволинейной, если каждое правило из R имеет вид

А-хВ, уВ

А-х, у

где А, 6N, xCS* н у£1У*. Покажите, что если 7" -праволинейная СУ-сХема, то х(Г) - регулярный перевод (конечное преобразование).

**3.1.15. Покажите, что если Г й*х Ь*-СУ-перевод, то Т определяется конечным преобразователем.

упражнения

3.1.16 Рассмотрим класс префиксных выражений в алфавитах операций О и операндов S. Если цепочка а,...а„ при-надлежит {ви)*, то степень S; ее /-й позиции [Osin] вычисляется так:

(1)5.-1,

(2) если ai-m-местная операция, то s,. = s i+/7г-1,

(3) если а,-€2, то - s. , -1.

Докажите, что а,-префиксное выражение тогда и только тогда, когда s„0 и s,-> О для всех i<n.

*3.1.17. Пусть Пу.. .о„ - префиксное выражение, в котором а-т-местная операция. Покажите, что единственный способ записать а.. .а„ как ayWy..,w,„, где w\, ш, -префиксные выражения, - это выбрать выражение Wj (1 /г) так, чтобы оно оканчивалось первым из символов а, у которого Sfm - /.

*3.1.18. Покажите, что каждое префиксное выражение с бинарными операциями получается из единственного инфиксного выражения, не содержащего избыточных скобок.

3.1.19. Переформулируйте и выполните упр. 3.1.16 - 3.1.18 для постфиксных выражений.

3.1.20. Дополните доказательство теоремы 3.1.

*3.1.21. Докажите, что порядок, в котором шаг (2) алгоритма 3.1 применяется к вершинам, не влияет на результирующее дерево.

3.1.22. Докажите лемму 3.1.

3.1.23. Постройте МП-преобразователи, реализующие простые СУ-переводы, определенные схемами трансляции из примеров 3.5 и 3.7,

3.1.24. Постройте грамматику для операций языка Снобол 4, отражающую ассоциативность и приоритет операций, указанные в приложении П2.

3.1.25. Найдите СУ-схему, определяющую перевод, который определяет (опустошением магазина) МП-преобразовагель

({9. Р}, {а. Ь], {Z,,A, В], {а, Ь), б, q, Z„ 0) где б задается равенствами

6(9, а, X) = (q, АХ, е) для всех X£{Z,, Л, В) 6(9, Ь, Л)-(9, ВХ, е) для всех X£{Z„ Л, В} 6(9, е, А) = (р, А, а) 6(Р, а, А) = {р, е, Ь) Ь, В) = (р, е, Ь) Ь{р, е, г,) = {р, е, а)





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 [43] 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002