1 Часть II. Глава 1. Трансляции, их представление и реализация Теория формальных языков и трансляций

2 § 1.1. Трансляции и трансляторы Определение 1.1. Трансляцией из языка L 1 * в язык L 2 * называется отношение L 1 L 2. Здесь входной алфавит, L 1 входной язык, выходной алфавит, L 2 выходной язык. Другими словами, трансляция есть некоторое множество пар предложений (x, y), где x L 1 входное, а y L 2 выходное предложение. Часть 2: Трансляции и синтаксические методы их реализации

3 Хотя в общем случае в трансляции одному входному предложению x может соответствовать несколько выходных пред- ложений y, по отношению к языкам программирования трансляция всегда является функцией, т. е. для каждого входа существует не более одного выхода. Существует бесконечно много примеров трансляций, но самым элементарным, ве- роятно, является тот, который может быть задан гомоморфизмом, т. е. отображением h из в *. Часть 2: Трансляции и трансляторы

4 Пример 1.1. Предположим, что мы хотим закодировать некоторый текст с помощью азбуки Морзе. Как известно, в коде Морзе каждая буква представляется как некоторая последовательность из точек и тире. Эти последовательности, называемые посылка- ми, имеют разную длину. Для отделения одной посылки от другой используется пауза. Часть 2: Трансляции и трансляторы

5 Очевидно, что трансляцию предложений, например, на русском языке, в код Морзе можно реализовать с помощью гомомор- физма, задаваемого следующим образом: Буква:аб в …я Посылка:. …. ….. Для простоты предполагаем, что паузы представлены пробелами, завершающими каждую посылку. Тогда, скажем, слово абба с помощью замены букв на посылки даёт результат:. … …. Часть 2: Трансляции и трансляторы

6 Для любой входной цепочки x = a 1 a 2 … a n, a i, i=1,2,…,n, гомоморфизм h позволяет найти соответствующую выходную цепочку y * с помощью посимвольной подстанов- ки: y = h(a 1 )h(a 2 )… h(a n ). Область определения гомоморфизма можно расширить до * следующим образом: h(ax) = h(a)h(x), h( ) =. Здесь a, x *. Далее используется одно и тоже обозначе- ние h для гомоморфизма на и *. Часть 2: Гомоморфизм

7 Гомоморфизм h определяет трансляцию (h) = {(x, h(x)) x * }. Устройство, которое по заданной цепочке x * находит соответствующую цепочку y = h(x), такую, что (x, y) (h), тривиально: оно должно посимвольно просмотреть входную цепочку x и заменить каждый её символ a на h(a). Это устройство является примером простейшего транслятора, реали- зующего трансляцию (h). Часть 2: Гомоморфизм

8 Реалистичным примером транслятора, основанного на гомоморфизме, является простейший ассемблер. Транслятором для данной трансляции называется такое устройство, которое по данной входной строке x вычисляет выходную цепочку y, такую, что (x, y). Часть 2: Трансляции и трансляторы

9 Желательными свойствами транслятора являются: 1) эффективность (время, затрачиваемое на перевод входной строки, должно быть линейно пропорционально её длине); 2) малый размер; 3) правильность (желательно иметь неболь- шой тест, такой, чтобы если транслятор прошёл его, то это гарантировало бы правильную работу транслятора на всех входных цепочках). Часть 2: Трансляции и трансляторы

10 § 1.2. Схемы синтаксически управляемой трансляции Трансляторы являются средством реализации трансляций, хотя их можно рассматривать также и как способ задания трансляций. Способом спецификации трансляций, более сложных, чем те, которые описы- ваются при помощи гомоморфизма, является аппарат схем синтаксически управляемых трансляций (sdts syntax- directed translation schema).

11 Определение 1.2. Схемой синтаксически управляемой трансляции называется фор- мальная система T = (N,,, R, S), где N алфавит нетерминалов; конечный входной алфавит; конечный выходной алфавит, причём N = и N = ; R конечное множество правил схемы вида Часть 2: Схемы синтаксически управляемой трансляции

12 A,, где A N, (N ) *, (N ) *, причём каждое вхождение нетерминала в цепочку взаимно однозначно связано с некоторым вхождением одноимённого нетерминала в, и эта связь является неотъемлемой частью правила; S N начальный нетерминал. Цепочка называется синтаксической, а цепочка семантической. Часть 2: Схемы синтаксически управляемой трансляции

13 Для указания связей между вхожде- ниями нетерминалов можно использовать индексы. Например, связанные вхождения одно- имённых нетерминалов помечаются одина- ковыми индексами: A aB (1) bCB (2), B (2) B (1) dC. Часть 2: Схемы синтаксически управляемой трансляции

14 Определение 1.3. Введем понятие трансляционной формы следующим образом: 1) (S, S) начальная трансляционная форма, причём эти два вхождения начального нетерминала связаны друг с другом по определению; Часть 2: Трансляционные формы

15 2) если ( A, A ) трансляционная форма, в которой два явно выделенных вхождения нетерминала A связаны, и если A, правило из R, то (, ) трансляционная форма; причём связь между нетерминалами в и такая же, как в правиле; нетерминалы в цепочках и связываются с нетерминалами в цепочках и в новой трансляционной форме точно так же, как в предыдущей; связь между нетерминалами является существенной чертой трансляционной формы; Часть 2: Трансляционные формы

16 3) трансляционными формами являются такие и только такие пары цепочек, которые могут быть получены с помощью этих двух способов. Это определение фактически вводит отношение непосредственной выводимости одной трансляционной формы из другой. В таком случае принято писать: ( A,A) (,). Часть 2: Трансляционные формы

17 Для степени, транзитивного и рефлексивно- транзитивного замыкания этого отношения используются соответственно следующие обозначения:, и. Когда ясно, в какой схеме производится вывод, имя схемы может быть опущено. Часть 2: Схемы синтаксически управляемой трансляции

18 Часть 2: Схемы синтаксически управляемой трансляции Определение 1.4. Трансляция, заданная при помощи схемы синтаксически управляемой трансляции T, есть множество (T) = {(x, y) (S, S) (x, y), x *, y * } и называется синтаксически управляемой трансляцией (sdt syntax-directed transla- tion).

19 Определение 1.5. Грамматика G i = (N,, P i, S), где P i = {A A, R}, называется входной грамматикой схемы. Грамматика G o = (N,, P o, S), где P o = {A A, R}, называется выходной грамматикой схемы. Очевидно, что G i и G o контекстно- свободные грамматики, порождающие входной и выходной языки трансляции, задаваемой схемой. Часть 2: Схемы синтаксически управляемой трансляции

20 Пример 1.2. Пусть sdts T = ({E, T, F}, {a, +, *, (, )}, {a, +, * }, R, E), где R = {(1) E E + T, E T +; (2) E T, T; (3) T T * F, T F * ; (4) T F, F; (5) F (E), E; (6) F a, a }. Связь между нетерминалами в этих правилах очевидна, так как в синтаксической и семантиче- ской цепочках каждого правила не более чем одно вхождение нетерминала, представленного данным символом из {E, T, F}. Ret 24

21 Часть 2: Пример 1.2. Рассмотрим какой-нибудь левосторонний вывод в схеме T, например: (E, E) (E + T, ET+) (T (1) + T, T (1) T +) (F + T, FT +) (a + T, aT+) (a + T * F, aTF * +) (a + a * F, aaF * +) (a + a * a, aaa * +).

22 Нетрудно догадаться, что (T) = {(x, y) x инфиксная запись, y эквивалентная постфиксная запись арифметического выражения}. Часть 2: Пример 1.2.

23 Определение 1.6. Схема синтаксически управляемой трансляции называется простой, если в каждом её правиле A, связанные нетерминалы в цепочках и встречаются в одинаковом порядке. Трансляция, определяемая простой схемой, называется простой синтаксически управ- ляемой трансляцией. Простые синтаксически управляемые трансляции

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

25 Другими словами, магазинные преобразо- ватели характеризуют класс простых синтаксически управляемых трансляций таким же образом, как магазинные автоматы характеризуют класс контекстно-свободных языков. К рассмотрению таких трансляций мы сейчас и перейдем. Простые синтаксически управляемые трансляции

26 § 1.3. Магазинные преобразователи и синтаксически управляемые трансляции Здесь мы рассмотрим магазинные преобразователи, отличающиеся от мага- зинных автоматов тем, что у них есть выходная лента.

27 q Q Q ( ) 2 Q Вход: Выход: Рис Недетерминированный магазинный преобразователь МZkZk а г а зZ2Z2 иZ1Z1 нZ0Z0 a1a1 a2a2 a3a3 aiai anan b1b1 b2b2 b3b3 bjbj bmbm Ret 24 Z k a i b j

28 Определение 1.7. Недерминированный магазинный преобразователь (npdt nondeterministic pushdown transducer) есть формальная система P = (Q,,,,, q 0, Z 0, F), где Q конечное множество состояний, конечный входной алфавит, конечный алфавит магазинных символов, конечный выходной алфавит, q 0 Q начальное состояние, Z 0 начальный символ магазина, F Q множество конечных состояний, отображение типа Q ( { }) 2 Q * *, причём область значений представлена конечными подмножествами троек из Q * *.

29 Запись (q, a, Z) = означает, что npdt P, находясь в состоянии q Q, сканируя a на входной ленте или не зависимо от текущего входного символа в случае a =, имея Z на вершине магазина, переходит в одно из состояний p i Q, заменяя в магазине символ Z на цепочку i * и записывая цепочку y i * на выходную ленту. Магазинный преобразователь

30 При этом входная головка сдвигается на одну ячейку вправо, если a, иначе головка остается на месте, головка магазина сканирует последнюю запись в магазине, а головка выходной ленты размещается справа от последней её записи. Магазинный преобразователь

31 В частности: если a =, то выбор действия не зависит от текущего входного символа и, как уже отмечалось, входная головка неподвижна; если i =, то верхний символ магазина стирается, а вершина магазина опускается; если y i =, то на выходную ленту ничего не пишется, и её головка остается на прежнем месте. Магазинный преобразователь

32 В начальный момент q = q 0, в магазине находится единственный символ Z 0, входная головка сканирует первую ячейку на входной ленте, а выходная лента пуста, причём её головка находится на первой ячейке. Работу магазинного преобразователя опишем в терминах конфигураций. Магазинный преобразователь

33 Определение 1.8. Конфигурацией магазин- ного преобразователя P назовем четверку (q, x,, y), где q Q текущее состояние, x * часть входной цепочки от текущего символа до её последнего символа, называемая непросмотренной частью входной цепочки, * содержимое магазина (будем считать, что первый символ цепочки есть верхний символ магазина), y * вся выходная цепочка. Магазинный преобразователь

34 Магазинный преобразователь Таким образом, начальная конфигурация есть (q 0,x,Z 0, ), где x обозначает всю входную цепочку. Пусть (q,ax,Z,y) текущая конфигура- ция, и (p,, z) (q, a, Z). Тогда один такт работы pdt P записывается как отношение между двумя последовательными конфигурациями: (q, ax, Z, y) (p, x,, yz). Здесь q Q, a { }, x *, Z,, *, y, z *.

35 Как обычно, определяются степень ( ), транзитивное замыкание ( ) и рефлексивно- транзитивное замыкание ( ) этого отноше- ния. Трансляция, реализуемая магазинным преобразователем

36 Трансляция, реализуемая магазинным преобразователем Определение 1.9. Говорят, что y * есть выход для x * при конечном состоянии, если (q 0, x, Z 0, ) (q,,, y) для некоторых q F и *. Трансляция, определяемая магазинным пре- образователем P при конечном состоянии, есть (P) = {(x, y) (q 0, x, Z 0, ) (q,,, y) для некоторых q F и * }.

37 Говорят, что y * есть выход для x * при пустом магазине, если (q 0, x, Z 0, ) (q,,, y) для некоторого q Q. Трансляция, определяемая магазинным преобразователем P при пустом магазине, есть e (P) = {(x, y) (q 0, x, Z 0, ) (q,,, y) для некоторого q Q}. Трансляция, реализуемая магазинным преобразователем

38 Пример 1.3. Пусть pdt P = ({q}, {a, +, * }, {E, +, * }, {a, +, * },, q, E, {q}), где 1) (q, a, E) = {( q,, a)}, 2) (q, +, E) = {( q, EE+, )}, 3) (q, *, E) = {( q, EE *, )}, 4) (q,, +) = {( q,, +)}, 5) (q,, * ) = {( q,, * )}. Ret 66 Входной символ используется Входной символ не используется

39 Пример 1.3. Рассмотрим действия pdt P на входе +*aaa: (q, + * aaa, E, ) (q, * aaa, EE+, ) (q, aaa, EE * E+, ) (q, aa, E * E+, a) (q, a, * E+, aa) (q, a, E+, aa * ) (q,, +, aa * a) (q,,, aa * a+). Очевидно, что он преобразует префиксные арифметические выражения в постфиксные. Данный магазинный преобразователь является примером детерминированного магазинного преобразователя (см. определе- ние 1.10 далее).1.10

40 Определение Магазинный преобразова- тель P = (Q,,,,, q 0, Z 0, F) называется детерминированным (dpdt), если 1) # (q, a, Z) 1 для всех q Q, a { } и Z ; 2) если (q,,Z) для данных q Q и Z, то (q, a, Z) = для всех a. Детерминированный магазинный преобразователь

41 На практике предпочитают использовать детерминированными магазинными преоб- разователями (dpdt), поскольку в реализации они оказываются более эффективными по сравнению с недетерминированными мага- зинными преобразователями (npdt). Когда неважно различать, о каких преобразователях, детерминированных или недетерминированных, идёт речь, исполь- зуется обозначение pdt. Детерминированный магазинный преобразователь

42 Лемма 1.1. Пусть T = (N,,, R, S) простая схема синтаксически управляемой трансляции. Существует недетерминированный мага- зинный преобразователь P, такой, что e (P) = (T). Доказательство. Построим npdt P, о котором идёт речь, и покажем, что он реализует трансляцию (T). Ret 65

43 Положим P = ({q},, N,,, q, S, ). Чтобы отличать в магазине P входные символы от выходных, последние пере- именовываются с помощью гомоморфизма h, определяемого для каждого выходного символа b при помощи равенства h(b) = b таким образом, чтобы множество символов = {b b } не пересекалось со словарем, т. е. =. (T) e (P)

44 Отображение определяется так: 1. (q, x 0 y 0 B 1 x 1 y 1 …B m x m y m, ) (q,,A), если A x 0 B 1 x 1 … B m x m, y 0 B 1 y 1 … B m y m R, y i = h(y i ), i = 1, 2,…, m, где m 0. Здесь h(by) = b'h(y) для каждого b и y *, h( ) =. 2. (q, a, a) = {(q,, )} для всех a. 3. (q,, b') = {(q,, b)} для всех b. (T) e (P) Ret 53Ret 55

45 I. Докажем сначала, что если (S, S) (x, y), то (q, x, S, ) (q,,, y). Для этого индукцией по длине вывода l докажем более общее утверждение для любого A N: если существует вывод (A, A) (x, y), то (q, x, A, ) (q,,, y). База. Пусть l = 1. Имеем (A, A) (x, y). На этом единственном шаге вывода применяется правило A x, y R. (T) e (P) Ret 52

46 (T) e (P) Согласно п.1 определения имеем (q, xy, ) (q,, A). Поэтому (q, x, A, ) (q, x, xy, ). Далее согласно п.2 (q, x, xy, ) (q,, y, ). Наконец, согласно п.3 имеем (q,, y, ) (q,,, y). Итак, существует переход (q, x, A, ) (q,,, y).

47 Индукционная гипотеза. Предположим, что вспомогательное утверждение выполняется для всех выводов длиной l n (n 1). Индукционный переход. Докажем утверждение для l = n + 1. Пусть (A, A) (x 0 B 1 x 1 … B m x m, y 0 B 1 y 1 …B m y m ) (x, y) вывод длиной n + 1. Очевидно, что x = x 0 t 1 x 1 t 2 x 2 …t m x m, y = y 0 z 1 y 1 z 2 y 2 …z m y m, (1.1) и (B i, B i ) (t i, z i ), l i n, i = 1, 2,…, m.(1.2) (T) e (P)

48 На первом шаге данного вывода было применено правило A x 0 B 1 x 1 B 2 x 2 …B m x m, y 0 B 1 y 1 B 2 y 2 …B m y m R и потому согласно п.1 построения имеем (q, x 0 y 0 B 1 x 1 y 1 B 2 x 2 y 2 … B m x m y m B, ) (q,, A). (1.3) Кроме того, согласно индукционной гипотезе из существования частичных выводов (1.2), следует возможность перехода (q, t i, B i, ) (q,,, z i ), i = 1, 2,…, m. (1.4) (T) e (P)

49 Рассмотрим движения pdt P. Учитывая условия (1.1) и (1.3), имеем (q, x, A, ) = (q, x 0 t 1 x 1 t 2 x 2 …t m x m, A, ) (q, x 0 t 1 x 1 t 2 x 2 …t m x m, x 0 y 0 B 1 x 1 y 1 B 2 x 2 y 2 …B m x m y m, ). Согласно п.2 построений имеем переход (q, x 0 t 1 x 1 t 2 x 2 …t m x m, x 0 y 0 B 1 x 1 y 1 B 2 x 2 y 2 …B m x m y m, ) (q, t 1 x 1 t 2 x 2 …t m x m, y 0 B 1 x 1 y 1 B 2 x 2 y 2 …B m x m y m, ); согласно п.3 построений имеем переход (q, t 1 x 1 t 2 x 2 …t m x m, y 0 B 1 x 1 y 1 B 2 x 2 y 2 …B m x m y m, ) (q, t 1 x 1 …t m x m, B 1 x 1 y 1 B 2 x 2 y 2 …B m x m y m, y 0 ). (T) e (P)

50 Учитывая существование перехода (1.4) для i = 1, получаем: (q, t 1 x 1 t 2 x 2 …t m x m, B 1 x 1 y 1 B 2 x 2 y 2 … B m x m y m, y 0 ) (q, x 1 t 2 x 2 …t m x m, x 1 y 1 B 2 x 2 y 2 …B m x m y m, y 0 z 1 ). Далее рассуждения с использованием пп.2, 3 построений, а также переходов (1.4) для i = 2, 3,…, m, повторяются. В результате получаем последующие движения: (T) e (P)

51 (T) e (P) (q, x 1 t 2 x 2 …t m x m, x 1 y 1 B 2 x 2 y 2 … B m x m y m, y 0 z 1 ) (q, t 2 x 2 …t m x m, y 1 B 2 x 2 y 2 … B m x m y m, y 0 z 1 ) (q, t 2 x 2 …t m x m, B 2 x 2 y 2 … B m x m y m, y 0 z 1 y 1 ) … (q, t m x m, B m x m y m, y 0 z 1 y 1 … z m–1 y m–1 ) (q, x m, x m y m, y 0 z 1 y 1 … z m–1 y m–1 z m ) (q,, y m, y 0 z 1 y 1 … z m–1 y m–1 z m ) (q,,, y 0 z 1 y 1 … z m–1 y m–1 z m y m ) = (q,,, y).

52 (T) e (P) В конце рассуждений о движениях pdt P принято во внимание представление цепочки y согласно равенству (1.1). Итак, вся последовательность движений может быть представлена в виде (q, x, A, ) (q,,, y). В частности, из доказанного вспомога- тельного утверждения при A = S следует утверждение I. утверждение I

53 e (P) (T) II. Докажем теперь обратное утверждение: если (q, x, S, ) (q,,, y), то (S, S) (x, y). Для этого индукцией по числу l движений типа 1, независимых от входных символов, определённых согласно п.1 построений, докажем более общее утверждениеп.1 для любого A N : если (q, x, A, ) (q,,, y), то (A, A) (x, y).

54 База. Пусть l = 1. Имеем (q, x, A, ) (q,,, y), где только одно движение типа 1. Очевидно, что оно первое движение, так как в исходной конфигурации на вершине магазина находится A N. Это движение не может привести к появлению нетерминалов в магазинной цепочке из-за того, что они неизбежно привели бы к другим движениям типа 1. e (P) (T)

55 Кроме того, магазинная цепочка, заме- щающая A на вершине магазина, должна начинаться на x, так как только в этом случае удаться продвинуться по входу x (за счёт движений, определённых в п.2, которые используют входные символы).п.2 Наконец, магазинная цепочка должна заканчиваться на y, потому что только в этом случае на выходе может образоваться цепочка y (за счёт движений, определённых в п.3, которые переносят образы выходных символов из магазина на выход). п.3 e (P) (T)

56 e (P) (T) Поэтому фактически имеем (q, x, A, ) (q, x, xy, ) (q,, y, ) (q,,, y), где первое движение обусловлено тем, что (q, xy, ) (q,, A), а это означает существование правила A x, y R. Два последних перехода выполнены согласно пп. 2, 3 построений. Воспользовавшись существующим прави- лом, немедленно получаем вывод (A, A) (x, y).

57 e (P) (T) Индукционная гипотеза. Предположим, что вспомогательное утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем утверж- дение для l = n + 1. Пусть имеется переход (q, x, A, ) (q,,, y), в котором ровно n + 1 движение типа 1.

58 e (P) (T) Поскольку в исходной конфигурации на вершине магазина A N, то первое же движение типа 1: (q, x, A, ) (q, x, x 0 y 0 B 1 x 1 y 1 …B m x m y m, ) (q,,, y). (1.5) В конечной конфигурации магазин пуст. Цепочка x 0 *, появившаяся в верхней части магазина после первого движения, может быть удалена только, если входная цепочка x начинается на x 0. Ret 63

59 e (P) (T) Поэтому далее последуют движения, опреде- ляемые п.2, которые продвинут вход по x 0 и удалят такую же цепочку из магазина. (q, x, A, ) (q, x 0, x 0 y 0 B 1 x 1 y 1 …B m x m y m, ) (q,, y 0 B 1 x 1 y 1 …B m x m y m, )… Далее ряд движений, определяемых п.3, удалит цепочку y 0 из магазина, выдав на выход y 0, и символ B 1 окажется на вершине магазина. (q,, B 1 x 1 y 1 …B m x m y m, y 0 ) =

60 e (P) (T) = (q,, B 1 x 1 y 1 …B m x m y m, y 0 ) (q,, x 1 y 1 …B m x m y m, y 0 z 1 ) К моменту, когда вершина магазина опустится ниже позиции B 1, будет просканирована некоторая часть входа t 1, следующая за цепочкой x 0, т. е. а на выходе образуется некоторая цепочка z 1 :

61 Далее мы можем повторить рассуждения, аналогичные предыдущим, относя их к цепочкам x i *, y i (i = 1, 2, …, m) и B j N ( j = 2, …, m), последовательно появ- ляющимся в верхней части магазина в результате серии движений, построенных в соответствии с п.2, затем п.3, и ряда движений, приводящих к понижению вершины магазина ниже позиции, занимаемой B j. e (P) (T)

62 e (P) (T) Другими словами, детальный разбор возможных движений от исходной конфигурации к конечной даёт основание утверждать, что вход x и выход y представимы в виде x = x 0 t 1 x 1 …t m x m, y = y 0 z 1 y 1 … z m y m, (1.6) причём (q, t i, B i, ) (q,,, z i ), (1.7) l i n, i = 1, 2, …, m.

63 e (P) (T) По построению первое движение (1.5) обусловлено существованием правила(1.5) A x 0 B 1 x 1 … B m x m, y 0 B 1 y 1 …B m y m R, (1.8) а из существования движений (1.7) по индукционному предположению следует существование выводов(1.7) (B i, B i ) (t i, z i ), i = 1, 2, …, m. (1.9) Используя (1.8) и (1.9), с учетом (1.6) получаем: (A, A) (x 0 B 1 x 1 … B m x m, y 0 B 1 y 1 … B m y m ) (x 0 t 1 x 1 … t m x m, y 0 z 1 y 1 … z m y m ) = (x, y).

64 В частности, при A = S следует утверж- дение II. Из рассуждений I и II следует утверждение леммы. Доказанная лемма даёт алгоритм построе- ния недетерминированного магазинного преобразователя, эквивалентного данной простой схеме синтаксически управляемой трансляции. e (P) (T)

65 Пример 1.4. Пусть sdts T = ({E}, {a, +, * }, {a, +, * }, R, E), где R = {(1) E +EE, EE+ ; (2) E * EE, EE * ; (3) E a, a}. По лемме 1.1 эквивалентный npdt есть1.1 P = ({q}, {a, +, * }, {E, a, +, *, a, +, * }, {a, +, * },, q, E, ), где 1) (q,, E) = { (q, +EE+, ), (q, * EE *, ), (q, aa, )}, 2) (q, b, b) = {( q,, )} для всех b {a, +, * }, 3) (q,, с ) = {( q,, с)} для всех с {a, +, * }.

66 Пример 1.4. Сравните этот недетерминированный магазин- ный преобразователь с эквивалентным детерми- нированным преобразователем из примера Оба преобразуют префиксные арифметические выражения в постфиксные. (q, + * aaa, E, ) (q, + * aaa, +EE+, ) (q, * aaa, EE+, ) (q, * aaa, * EE * E+, ) (q, aaa, aa E * E+, ) (q, aaa, EE * E+, ) (q, aa, a E * E+, ) (q, aa, E * E+, a) (q, aa, aa * E+, a) (q, a, a * E+, a) (q, a, * E+, aa) (q, a, E+, a a * ) (q, a, aa +, aa * ) (q,, a +, aa * ) (q,, +, a a * a) (q,,, a a * a +).

67 Лемма 1.2. Пусть P = (Q,,,,, q 0, Z 0, ) недетерминированный магазинный преоб- разователь. Существует простая схема синтаксически-управляемой трансляции T, такая, что (T) = e (P). Доказательство. Построим такую схему T следующим образом (ср. с теор. 5.3).5.3 Положим T = (N,,, R, S), где N = {S} {[qZp] q, p Q, Z }, и такие же, как в npdt P, e (P) (T) Ret 82

68 e (P) (T) R = {S [q 0 Z 0 p], [q 0 Z 0 p] для всех p Q} {[qZp] a[q 1 Z 1 q 2 ][q 2 Z 2 q 3 ]…[q m Z m q m+1 ], y[q 1 Z 1 q 2 ][q 2 Z 2 q 3 ]…[q m Z m q m+1 ] (q 1, Z 1 Z 2 …Z m, y) (q, a, Z); a { }, y * ; p, q, q i Q; Z, Z i ; i = 1, 2, …, m; q m+1 = p}. I. Докажем сначала, что если (q, x, Z, ) (p,,, y), то ([qZp], [qZp]) (x, y), используя индукцию по числу l движений ndpt P.

69 e (P) (T) База. Пусть l = 1. Имеем (q, x, Z, ) (p,,, y). В этом случае x { } и (p,, y) (q, x, Z). Тогда по построению схемы T существует правило [qZp] x, y R, с помощью которого немедленно получаем: ([qZp], [qZp]) (x, y).

70 e (P) (T) Индукционная гипотеза. Предположим, что утверждение I выполняется для всех переходов между конфигурациями за число движений l n (n 1). Индукционный переход. Докажем, что тогда утверждение I справедливо и для l = n + 1. Итак, пусть (q, x, Z, ) (p,,, y). Рассмотрим этот переход подробнее.

71 e (P) (T) В общем случае первое движение имеет вид (q, x, Z, ) = (q, ax, Z, ) (q 1, x, Z 1 Z 2 …Z m, y 0 ). (1.10) Затем следуют дальнейшие движения : (q 1, x, Z 1 Z 2 …Z m, y 0 ) = = (q 1, x 1 x 2 …x m, Z 1 Z 2 …Z m, y 0 ) (q 2, x 2 …x m, Z 2 …Z m, y 0 y 1 ) … (q m+1,,, y 0 y 1 y 2 …y m ) = (p,,, y). (1.11) Здесь a { }, x = ax 1 x 2 … x m, y = y 0 y 1 y 2 …y m,

72 e (P) (T) причём (q i, x i, Z i, ) (q i + 1,,, y i ), (1.12) i = 1, 2, …, m; l i n; q m+1 = p. Первое движение (1.10) существует потому, что (q 1, Z 1 Z 2 …Z m, y 0 ) (q, a, Z), следователь- но, по способу построения правил схемы в ней имеется правило [qZp] a[q 1 Z 1 q 2 ][q 2 Z 2 q 3 ]…[q m Z m q m+1 ], y 0 [q 1 Z 1 q 2 ][q 2 Z 2 q 3 ]…[q m Z m q m+1 ], (1.13) в обозначениях нетерминалов которого уча- ствуют те состояния, по которым проходил npdt P.

73 Из последующих движений (1.11) согласно индукционной гипотезе, применённой к (1.12), следует существование выводов ([q i Z i q i+1 ], [q i Z i q i+1 ]) (x i, y i ), (1.14) i = 1, 2,…, m. Из (1.13) и (1.14) можно выстроить требуе- мый вывод: ([qZp], [qZp]) (a[q 1 Z 1 q 2 ]…[q m Z m q m+1 ], y 0 [q 1 Z 1 q 2 ]…[q m Z m q m+1 ]) (ax 1 x 2 …x m, y 0 y 1 …y m ) = (x, y). e (P) (T)

74 e (P) (T) II. Индукцией по длине l вывода докажем теперь обратное утверждение: если ([qZp], [qZp]) (x, y), то (q, x, Z, ) (p,,, y). База. Пусть l = 1. Имеем ([qZp], [qZp]) (x, y). На единственном шаге этого вывода использовано правило схемы [qZp] x, y, которое обязано своим происхождением тому, что (p,, y) (q, x, Z), где x { }, y *, а тогда (q, x, Z, ) (p,,, y).

75 e (P) (T) Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех выводов, длина которых не превосходит n (n 1). Индукционный переход. Докажем аналогичное утверждение для выводов длиной l = n + 1. Пусть ([qZp], [qZp]) (a[q 1 Z 1 q 2 ]…[q m Z m q m+1 ], y 0 [q 1 Z 1 q 2 ]…[q m Z m q m+1 ]) (x, y). (1.15)

76 Из (1.15) следует, что существует правило [qZp] a[q 1 Z 1 q 2 ]…[q m Z m q m+1 ], y[q 1 Z 1 q 2 ]…[q m Z m q m+1 ] R, которое обязано своим происхождение тому, что (q 1, Z 1 …Z m, y) (q, a, Z). (1.16) e (P) (T)

77 e (P) (T) Кроме того, из (1.15) следует, что x = ax 1 …x m, y = y 0 y 1 …y m, (1.17) ([q i Z i q i +1 ], [q i Z i q i +1 ]) (x i, y i ), l i n, а тогда согласно индукционной гипотезе (q i, x i, Z i, ) (q i+1,,, y i ), (1.18) i = 1, 2,…, m; q m+1 = p. Из (1.16) и (1.18) с учетом (1.17) выстраивается последовательность движе- ний: (q, x, Z, ) = (q, ax 1 …x m, Z, ) (q 1, x 1 …x m, Z 1 …Z m, y 0 ) (p,,, y 0 y 1 …y m ) = (p,,, y).

78 e (P) (T) Из рассуждений I и II следует, что для любых q, p Q и Z вывод ([qZp], [qZp]) (x, y) существует тогда и только тогда, когда (q, x, Z, ) (p,,, y). В частности, это справедливо для q = q 0 и Z = Z 0.

79 e (P) (T) В то же время при помощи правила вида S [q 0 Z 0 p], [q 0 Z 0 p] всегда можно при- строить начало к вышеприведённому выводу, чтобы считать доказанным утверждение: (S, S) ([q 0 Z 0 p], [q 0 Z 0 p]) (x, y) тогда и только тогда, когда (q 0, x, Z 0, ) (p,,, y). Лемма доказана.

80 Из лемм 1.1 и 1.2 следует Теорема 1.1. Трансляция = (T), где T простая схема синтаксически управляемой трансляции, существует тогда и только тогда, когда существует недетерминиро- ванный магазинный преобразователь P, такой, что e (P) =. e (P) (T) Ret 106

81 Пример 1.5. В предыдущем примере по простой sdts T = ({E},{a, +, * }, {a, +, * }, R, E), где R = {(1) E +EE, EE+ ; (2) E * EE, EE * ; (3) E a, a}, был построен эквивалентный npdt P = ({q}, {a, +, * }, {E, a, +, *, a, +, * }, {a, +, * },, q, E, ), где 1) (q,, E) = {(q, +EE+, ), (q, * EE *, ), (q, aa, )}, 2) (q, b, b) = {( q,, )} для всех b {a, +, * }, 3) (q,, с ) = {( q,, с)} для всех с {a, +, * }. Ret 84

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

83 Положим T = ({S, [qEq], [qaq], [q+q], [q * q], [qa q], [q+ q], [q * q]}, {a, +, * },{a, +, * }, R, S), R = {(1) S [qEq], [qEq]; (2) [qEq] [q+q] [qEq] [qEq] [q+ q], [q+q] [qEq] [qEq] [q+ q]; (3) [qEq] [q * q] [qEq] [qEq] [q * q], [q * q] [qEq] [qEq] [q * q]; (4) [qEq] [qaq] [qa q], [qaq] [qa q]; (5) [qaq] a, ; (8) [qa q], a; (6) [q+q] +, ; (9) [q+ q], +; (7) [q * q] *, ; (10) [q * q], * }. Пример 1.5.

84 Эта схема мало похожа на исходную, в которой было всего три правила. Однако её можно эквивалентными преобразованиями привести к исходной.исходную Пример 1.5.

85 Во-первых, правые части правил 5–10 можно подставить в правые части правил 2–4. В результате получим R = {(1) S [qEq], [qEq]; (2 ) [qEq] +[qEq] [qEq], [qEq] [qEq]+; (3 ) [qEq] * [qEq] [qEq], [qEq] [qEq] * ; (4 ) [qEq] a, a}. Легко видеть, что из (S, S) выводится в точности то же, что и из ([qEq], [qEq]). Остается заменить в правилах 2 –4 слева и справа [qEq] на простое E и отбросить бесполезное правило 1, чтобы получить исходную схему. Пример 1.5.

86 Лемма 1.3. Пусть P = (Q,,,,, q 0, Z 0, F) недетерминированный магазинный преобра- зователь и = (P). Существует недетерминированный мага- зинный преобразователь P, такой, что e (P ) =. (P) e (P ) Ret 105

87 Доказательство. Построим pdt P, исходя из того соображения, что он будет моделировать pdt P до тех пор, пока тот не примет свою входную цепочку, а затем pdt P будет опустошать свой магазин, совершая - движения и не выдавая ничего на выход. Таким образом, npdt P будет принимать то же самое множество входных цепочек при пустом магазине, какое pdt P принимает при конечных состояниях, и выдавать на выход такие же выходные цепочки. (P) e (P )

88 Итак, положим (ср. с теор II)5.1 - II P = (Q,,,,, q 0, Z 0, ), где входной и выходной алфавиты такие же, как у npdt P, а множество конечных состояний, которое в этом случае несущественно, пусто; Q = Q {q 0, q e }, q 0, q e Q; = {Z 0 }, Z 0. (P) e (P )

89 Отображение определяется следующим образом: 1. (q 0,, Z 0 ) = {(q 0, Z 0 Z 0, )} воспроизводит начальную конфигурацию недетер- минированного магазинного преобразователя P. 2. (q, a, Z) содержит все элементы (q, a, Z) для q Q, a { }, Z, реализуется собственно моделирование движений pdt P. 3. (q,, Z) содержит (q e,, ), если q F, Z, происходит переход в состояние-ловушку. 4. (q e,, Z) = {(q e,, )} для всех Z производится опустошение магазина. (P) e (P )

90 (P) e (P ) I. Докажем сначала, что если (x, y) (P), то (x, y) e (P ). Пусть (x, y) (P), т. е. (q 0, x, Z 0, ) (q,,, y), где q F. Посмотрим, как будет действовать npdt P на таком же входе. Согласно п.1 построения имеем (q 0, x, Z 0, ) (q 0, x, Z 0 Z 0, ).

91 Далее согласно п.2 npdt P повторяет все движения pdt P, т. е. (q 0, x, Z 0 Z 0, ) (q,, Z 0, y), где q F, а тогда согласно п.3 pdt P переходит в состояние q e, оставаясь в котором, в соответствии с п.4 опустошает свой магазин: (q,, Z 0, y) (q e,,, y). Следовательно, (x, y) e (P ). (P) e (P )

92 (P) e (P ) II. Докажем теперь обратное, т. е. если (x, y) e (P ), то (x, y) (P). Пусть (x, y) (P ), т. е. (q 0, x, Z 0, ) (q e,,, y). Рассмотрим подробнее его движения. Первое движение согласно п.1 имеет вид (q 0, x, Z 0, ) (q 0, x, Z 0 Z 0, ). Ясно, что для опустошения магазина npdt P должен оказаться в состоянии q e : без этого ему не сбросить символ Z 0, находящийся на дне магазина.

93 В свою очередь, согласно п.3 npdt P достигает состояния q e только после того, как, повторяя движения npdt P согласно п.2, он оказывается в состоянии q F. С этого момента он не продвигается по входной цепочке, ничего не пишет на выходную ленту и только стирает магазин. Это значит, что к моменту достижения конечного состояния он уже прочитал всю свою входную цепочку x и записал всю свою выходную цепочку y. (P) e (P )

94 Дальнейшие движения pdt P имеют вид (q 0, x, Z 0 Z 0, ) (q,, Z 0, y) (q e,,, y), где q F, *. Но на участке (q 0, x, Z 0 Z 0, ) (q,, Z 0, y) pdt P лишь повторяет движения npdt P: (q 0, x, Z 0, ) (q,,, y), q F, *. Следовательно, (x, y) (P). Из рассуждений I и II следует справедливость леммы. (P) e (P )

95 Лемма 1.4. Пусть P = (Q,,,,, q 0, Z 0, F) недетерминированный магазинный преоб- разователь и = e (P). Существует недетерминированный ма- газинный преобразователь P, такой, что (P ) =. e (P) (P ) Ret 105

96 Доказательство. Построим npdt P, исходя из того соображения, что pdt P будет моделировать npdt P до тех пор, пока тот не примет свою входную цепочку, опустошив магазин, а затем npdt P совершит ещё одно -движение, не записывающее ничего на выходную ленту, и перейдет в свое конечное состояние, принимая ту же входную цепочку. e (P) (P )

97 Разумеется, надо позаботиться о том, чтобы к этому моменту магазин не был пуст, иначе никакое дальнейшее движение не будет возможно. Таким образом, npdt P будет принимать то же самое множество входных цепочек при конечном состоянии, выдавая те же выходные цепочки, что и npdt P. e (P) (P )

98 e (P) (P ) Положим npdt (ср. с теор I)5.1 - I P = (Q,,,,, q 0, Z 0, ). Здесь Q = Q {q 0, q f }, q 0, q f Q; входной и выходной алфавиты такие же, как у npdt P; = {Z 0 }, Z 0 ; = {q f }.

99 Отображение определяется следующим образом: 1. (q 0,, Z 0 ) = {(q 0, Z 0 Z 0, )} воспроизводит начальную конфигурацию npdt P. 2. (q, a, Z) содержит все элементы (q, a, Z) для q Q, a { }, Z, происходит собственно моделирование движений npdt P. 3. (q,, Z 0 ) = {(q f,, )}, где * про- извольная магазинная цепочка, определяет переход в конечное состояние.

100 I. Докажем сначала, что если (x, y) e (P), то (x, y) (P ). Пусть (x, y) e (P), т. е. (q 0, x, Z 0, ) (q,,, y). Посмотрим, как будет действовать npdt P с такой же входной цепочкой. Согласно п.1 (q 0, x, Z 0, ) (q 0, x, Z 0 Z 0, ). e (P) (P )

101 Далее согласно п.2 npdt P повторяет все движения npdt P, т. е. (q 0, x, Z 0 Z 0, ) (q,, Z 0, y), а затем согласно п.3 npdt P переходит в состояние q f : (q,, Z 0, y) (q f,,, y). Следовательно, (x, y) (P ). e (P) (P )

102 e (P) (P ) II. Докажем теперь обратное, т. е. если (x, y) (P ), то (x, y) e (P). Пусть (x, y) (P ), т. е. (q 0, x, Z 0, ) (q f,,, y) при некотором *. Рассмотрим подробнее его движения. Первое движение согласно п.1 имеет вид (q 0, x, Z 0, ) (q 0, x, Z 0 Z 0, ).

103 e (P) (P ) Далее в конце концов npdt P оказывается в своем конечном состоянии q f. Это возможно только в результате движения, построенного в соответствии с п.3, который применим лишь тогда, когда на вершине магазина npdt P покажется символ Z 0, т. е. дальнейшие движения имеют вид (q 0, x, Z 0 Z 0, ) (q,, Z 0, y) (q f,,, y).

104 e (P) (P ) На участке (q 0, x, Z 0 Z 0, ) (q,, Z 0, y) магазинный преобразователь P просто повторяет движения npdt P: (q 0, x, Z 0, ) (q,,, y). А это значит, что (x, y) e (P). Из рассуждений I и II следует утверждение леммы.

105 Из лемм 1.3 и 1.4 следует Теорема 1.2. Классы трансляций, реализуемых недетерминированными мага- зинными преобразователями при конечном состоянии и пустом магазине, совпадают. (P ) = e (P) Ret 106

106 Замечание 1.1. Принимая во внимание теорему 1.2, формулировку теоремы 1.1 можно усилить, не подчеркивая того факта, что простая трансляция реализуется недетерминированным магазинным преоб- разователем при пустом магазине К сожалению, не всякая, даже простая, синтаксически управляемая трансляция может быть реализована детерминиро- ванным МП-преобразователем. (P ) = e (P)

107 § 1.4. Детерминированная генерация выходной цепочки простой sdt по лево- стороннему анализу входной цепочки Определение Схема синтаксически управляемой трансляции называется семантически однозначной, если в ней не существует двух правил вида A и A, в которых. Другими словами, семантическая цепочка однозначно определяется правилом входной грамматики схемы.

108 Определение Пусть G = (V N, V T, P, S) cfg, правила которой занумерованы: 1, 2, …, p, и S x левосторонний вывод x V T * в грамматике G. Здесь {1, 2, …, p} *. Последовательность номеров правил, применённых в этом выводе, называется левосторонним анализом цепочки x.

109 Теорема 1.3. Пусть T = (N,,, R, S) простая семантически однозначная схема синтаксически управляемой трансляции, правила которой занумерованы как 1,2,…, p. Существует детерминированный мага- зинный преобразователь P, такой, что e (P) = {(, y) (S, S) (x, y) для некоторой цепочки x * }. Говоря неформально, выходная цепочка y простой трансляции может быть сгенерирована детерминирован- ным магазинным преобразователем (dpdt) по лево- стороннему анализу входной цепочки x.

110 Доказательство. Построим dpdt P, о идет речь, положив P = ({q}, {1, 2,…, p}, N,,, q, S, ), где определяется следующим образом: 1. (q, i, A) = (q,, ), если A, i-е правило схемы, единственное, начинающееся на A. 2. (q,, b) = (q,, b) для всех b. e (P) = {(, y) (S, S) (x, y), x * }

111 Магазинный преобразователь P детерминирован, так как правила вида 1 применимы, только если на вершине магазина находится нетерминал, а правила вида 2 используются только тогда, когда на вершине магазина находится выходной символ. Остаётся доказать, что построенный dpdt P действительно реализует требуемую трансляцию. e (P) = {(, y) (S, S) (x, y), x * }

112 e (P) = {(, y) (S, S) (x, y), x * } I. Индукцией по длине вывода l = | | пока- жем, что если для любого A N существует левосторонний вывод (A, A) (x, y), то (q,, A, ) (q,,, y). База. Пусть l = 1. На единственном шаге вывода (A, A) (x, y) применяется правило схемы с номером i A x, y (i)

113 e (P) = {(, y) (S, S) (x, y), x * } В соответствии с п.1 построения (q, i, A) = (q, y, ), и тогда (q, i, A, ) (q,, y, ) (q,,, y). Последний переход совершен согласно п.2 построений, так как y *. Индукционная гипотеза. Предположим, что подобное утверждение выполняется для всех выводов длиной l n (n 1).

114 e (P) = {(, y) (S, S) (x, y), x * } Индукционный переход. Покажем, что утверждение выполняется и для l = n + 1. Пусть (A, A) (x 0 A 1 x 1 A 2 …A m x m, y 0 A 1 y 1 A 2 …A m y m ) (x, y) вывод длиной n + 1; = n; A, A j N, j = 1, 2,…, m; x k *, y k *, k = 0, 1, 2,…, m. На первом шаге применяется правило схемы A x 0 A 1 x 1 A 2 …A m x m, y 0 A 1 y 1 A 2 …A m y m, имеющее номер i.

115 e (P) = {(, y) (S, S) (x, y), x * } Согласно п.1 (q, i, A) = (q, y 0 A 1 y 1 A 2 …A m y m, ). (1.19) Одновременно ясно, что x = x 0 t 1 x 1 t 2 …t m x m, y = y 0 z 1 y 1 z 2 …z m y m, = i 1 2 … m, (1.20) где (A j, A j ) (t j, z j ), j n, и, следовательно, по индукционной гипо- тезе (q, j, A j, ) (q,,, z j ) (1.21) для j = 1, 2, …, m.

116 e (P) = {(, y) (S, S) (x, y), x * } Принимая во внимание (1.19) – (1.21), а также п.2 построений dpdt P, можем написать: (q,, A, ) = (q, i 1 2 … m, A, ) (q, 1 2 … m, y 0 A 1 y 1 A 2 …A m y m, ) (q, 1 2 … m, A 1 y 1 A 2 …A m y m, y 0 ) (q, 2 … m, y 1 A 2 …A m y m, y 0 z 1 ) … (q,, y m, y 0 z 1 y 1 …z m ) (q,,, y 0 z 1 y 1 …z m y m ) = (q,,, y).

117 II. Индукцией по длине входной цепочки l = покажем, что для любого A N, если (q,, A, ) (q,,, y), то (A, A) (x, y) при некотором x *. База. Пусть l = 1, т. е. = i, и (q, i, A, ) (q,,, y). В общем случае этот переход может происходить только следующим образом: (q, i, A, ) (q,, y, ) (q,,, y). e (P) = {(, y) (S, S) (x, y), x * }

118 Действительно, первое движение происхо- дит согласно п.1, поскольку на вершине магазина A N. Других движений этого типа не существует, так как других символов на входе, требуемых для таких движений, не существует. Возможные же движения согласно п.2 предполагают нахождение в верхней части магазина некоторой цепочки y *. e (P) = {(, y) (S, S) (x, y), x * }

119 e (P) = {(, y) (S, S) (x, y), x * } Первое движение определяется значением (q, i, A) = (q, y, ), предполагающим существование правила вида A x, y R с номером i при некотором x *. С его помощью немедленно получаем (A, A) (x, y). Индукционная гипотеза. Предположим, что подобное утверждение выполняется для всех входных цепочек длиной l n (n 1).

120 Индукционный переход. Пусть (q,, A, ) (q,,, y), где = n + 1. В общем случае эти движения могут происходить только следующим образом: (q,, A, ) = (q, i, A, ) (q,, y 0 A 1 y 1 A 2 …A m y m, ) (q,, A 1 y 1 A 2 …A m y m, y 0 ) = = (q, 1 2 … m, A 1 y 1 A 2 …A m y m, y 0 ) (q, 2 … m, y 1 A 2 …A m y m, y 0 z 1 ) (q, 2 … m, A 2 …A m y m, y 0 z 1 y 1 ) … (q,, y m, y 0 z 1 y 1 …z m ) (q,,, y 0 z 1 y 1 …z m y m ) = = (q,,, y).

121 Соответственно = i 1 2 … m, y = y 0 z 1 y 1 z 2 …z m y m. (1.22) Первое движение позволяет утверждать, что (q, i, A) = (q, y 0 A 1 y 1 A 2 …A m y m, ), и, следовательно, в схеме существует правило под номером i вида A x 0 A 1 x 1 A 2 …A m x m, y 0 A 1 y 1 A 2 …A m y m. (1.23) e (P) = {(, y) (S, S) (x, y), x * }

122 e (P) = {(, y) (S, S) (x, y), x * } Промежуточные движения вида (q, j, A j, ) (q,,, z j ), j n, по индукционному предположению гаран- тируют существование выводов вида (A j, A j ) (t j, z j ) (1.24) при некоторых t j *, j = 1, 2, …, m.

123 e (P) = {(, y) (S, S) (x, y), x * } Используя правило (1.23), выводы (1.24) и учитывая равенство (1.22), можем построить вывод (A, A) (x 0 A 1 x 1 A 2 …A m x m, y 0 A 1 y 1 A 2 …A m y m ) (x 0 t 1 x 1 t 2 …t m x m, y 0 z 1 y 1 z 2 …z m y m ) = = (x, y). Здесь = 1 2 … m, i =, т. е. (A, A) (x, y). Утверждение теоремы следует из рассуждений I и II при A = S.

124 Пример 1.6. (Перевод выражений из инфиксной формы в префиксную). Пусть T = ({E, T, F}, {a, +, *, (, )}, {a, +, * }, R, E), где R = {(1) E E + T, +ET; (2) E T, T; (3) T T * F, * TF; (4) T F, F; (5) F (E), E; (6) F a, a }. В соответствии с описанием построений в теореме 1.3 определим детерминированный магазинный преобразователь, восстанавливающий выход трансляции по левостороннему анализу входной цепочки: P = ({q}, {1, 2, 3, 4, 5, 6}, {E, T, F, a, +, * }, {a, +, * },, q, E, ),

125 где 1) (q, 1, E) = (q, +ET, ); 2) (q, 2, E) = (q, T, ); 3) (q, 3, T) = (q, * TF, ); 4) (q, 4, T) = (q, F, ); 5) (q, 5, F) = (q, E, ); 6) (q, 6, F) = (q, a, ); 7) (q,, a) = (q,, a); 8) (q,, +) = (q,, +); 9) (q,, * ) = (q,, * ). Очевидно, что при = имеем ( E, E ) ( a * (a + a), * a + a a ). Нетрудно убедиться в том, что ( q, , E, ) ( q,,, * a + a a ). Пример 1.6. Next