Трансляции, их представление и реализация

§ 1.1. Трансляции и трансляторы
Определение 1.1. Трансляцией из языка L1 ⊆ Σ* в язык L2 ⊆ Δ* называется отношение τ ⊆ L1 × L2.
Здесь Σ — входной алфавит, L1 — входной язык, Δ — выходной алфавит, L2 — выходной язык.
Другими словами, трансляция есть некоторое множество пар предложений (x, y), где x∈L1 — входное, а y∈L2 — выходное предложение.

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

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

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

Для любой входной цепочки x = a1a2 … an, ai∈Σ, i=1,2,…,n, гомоморфизм h позволяет найти соответствующую выходную цепочку y∈Δ* с помощью посимвольной подстанов-ки: y = h(a1)h(a2)… h(an).
Область определения гомоморфизма можно расширить до Σ* следующим образом:
h′(ax) = h(a)h′(x), h′(ε) = ε. Здесь a∈Σ, x∈Σ*.
Далее используется одно и тоже обозначе-ние h для гомоморфизма на Σ и Σ*.

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

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

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

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

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

A→ α, β, где A∈N, α∈(N∪Σ)*, β∈(N∪Δ)*,
причём каждое вхождение нетерминала в цепочку α взаимно однозначно связано с некоторым вхождением одноимённого нетерминала в β, и эта связь является неотъемлемой частью правила;
S ∈ N — начальный нетерминал.
Цепочка α называется синтаксической, а цепочка β — семантической.

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

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

2) если (αAβ, α’Aβ’) — трансляционная форма, в которой два явно выделенных вхождения нетерминала A связаны, и если A → γ, γ’ — правило из R, то (αγβ, α’γ’β’) — трансляционная форма; причём связь между нетерминалами в γ и γ’ такая же, как в правиле; нетерминалы в цепочках α и β связываются с нетерминалами в цепочках α’ и β’ в новой трансляционной форме точно так же, как в предыдущей; связь между нетерминалами является существенной чертой трансляционной формы;

Определение 1.5.
Грамматика Gi = (N, Σ, Pi, S), где
Pi = {A → α | ∃ A → α, β∈R},
называется входной грамматикой схемы.
Грамматика Go = (N, Δ, Po, S), где
Po = {A → β | ∃ A → α, β∈R},
называется выходной грамматикой схемы.
Очевидно, что Gi и Go — контекстно-свободные грамматики, порождающие входной и выходной языки трансляции, задаваемой схемой.

Пример 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

Часть 2: Пример 1.2.

Нетрудно догадаться, что
τ(T) = {(x, y) |
x — инфиксная запись,
y — эквивалентная постфиксная
запись арифметического выражения}.

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

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

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

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

q∈Q
Q×(Σ∪{ε})×Γ
→ 2Q × Γ* × Δ*
Вход:
Выход:
Рис. 1.1.
Ret 24
Zk∈Γ
ai∈Σ
bj ∈ Δ

Определение 1.7.
Недерминированный магазинный преобразователь (npdt — nondeterministic pushdown transducer) есть формальная система
P = (Q, Σ, Γ, Δ, δ, q0, Z0, F), где
Q — конечное множество состояний,
— конечный входной алфавит,
— конечный алфавит магазинных символов,
— конечный выходной алфавит,
q0∈Q — начальное состояние,
Z0∈Γ — начальный символ магазина,
F ⊆ Q — множество конечных состояний,
— отображение типа Q×(Σ∪{ε})×Γ → 2Q×Γ*×Δ*, причём область значений δ представлена конечными подмножествами троек из Q × Γ*× Δ*.

Запись
δ(q, a, Z) =
означает, что npdt P, находясь в состоянии q∈Q, сканируя a∈Σ на входной ленте или не зависимо от текущего входного символа в случае a = ε, имея Z ∈ Γ на вершине магазина, переходит в одно из состояний pi∈Q, заменяя в магазине символ Z на цепочку γi∈Γ* и записывая цепочку yi∈Δ* на выходную ленту.

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

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

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

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

Таким образом, начальная конфигурация есть (q0,x,Z0,ε), где 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∈Δ*.

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

Определение 1.9. Говорят, что y∈Δ* есть выход для x∈Σ* при конечном состоянии, если
(q0, x, Z0, ε) (q, ε, α, y)
для некоторых q∈F и α∈Γ*.
Трансляция, определяемая магазинным пре-образователем P при конечном состоянии, есть
τ(P) = {(x, y) | (q0, x, Z0, ε) (q, ε, α, y)
для некоторых q∈F и α∈Γ*}.

Говорят, что y∈Δ* есть выход для x∈Σ* при пустом магазине, если
(q0, x, Z0, ε) (q, ε, ε, y)
для некоторого q∈Q.
Трансляция, определяемая магазинным преобразователем P при пустом магазине, есть
τe(P) = {(x, y) | (q0, x, Z0, ε) (q, ε, ε, y)
для некоторого q∈Q}.

Пример 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

Определение 1.10. Магазинный преобразова-тель P = (Q, Σ, Γ, Δ, δ, q0, Z0, F) называется детерминированным (dpdt), если
#δ(q, a, Z) ≤ 1
для всех q∈Q, a∈Σ ∪ {ε} и Z∈Γ;
2) если δ(q,ε,Z)≠∅ для данных q∈Q и Z∈Γ, то δ(q, a, Z) = ∅ для всех a∈Σ.

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

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

Положим
P = ({q}, Σ, N ∪ Σ ∪ Δ’, Δ , δ, q, S, ∅).
Чтобы отличать в магазине P входные символы от выходных, последние пере-именовываются с помощью гомоморфизма h, определяемого для каждого выходного символа b∈Δ при помощи равенства h(b) = b’ таким образом, чтобы множество символов Δ’ = {b’ | b∈Δ} не пересекалось со словарем Σ, т. е. Σ ∩ Δ’ = ∅.

Отображение δ определяется так:
1. (q, x0y0’B1x1y1’…Bmxmym’, ε)∈δ(q,ε,A), если
A → x0B1x1 … Bmxm, y0B1y1… Bmym∈R,
yi’ = h(yi), 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∈Δ.
Ret 53
Ret 55

Ret 52

На первом шаге данного вывода было применено правило
A → x0B1x1B2x2…Bmxm, y0B1y1B2y2…Bmym∈R
и потому согласно п.1 построения имеем
(q, x0y0’B1x1y1’B2x2y2’… Bmxmym’B, ε)∈δ(q, ε, A).
(1.3)
Кроме того, согласно индукционной гипотезе из существования частичных выводов (1.2), следует возможность перехода
(q, ti, Bi, ε) (q, ε, ε, zi), i = 1, 2,…, m. (1.4)

Рассмотрим движения pdt P.
Учитывая условия (1.1) и (1.3), имеем
(q, x, A, ε) = (q, x0t1x1t2x2…tmxm, A, ε)
(q, x0t1x1t2x2…tmxm, x0y0’B1x1y1’B2x2y2’…Bmxmym’, ε).
Согласно п.2 построений имеем переход
(q, x0t1x1t2x2…tmxm, x0y0’B1x1y1’B2x2y2’…Bmxmym’, ε)
(q, t1x1t2x2…tmxm, y0’B1x1y1’B2x2y2’…Bmxmym’, ε);
согласно п.3 построений имеем переход
(q, t1x1t2x2…tmxm, y0’B1x1y1’B2x2y2’…Bmxmym’, ε)
(q, t1x1…tmxm, B1x1y1’B2x2y2’…Bmxmym’, y0).

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

Поскольку в исходной конфигурации на вершине магазина A∈N, то первое же движение — типа 1:
(q, x, A, ε) (q, x, x0y0’B1x1y1’…Bmxmym’, ε)
(q, ε, ε, y). (1.5)
В конечной конфигурации магазин пуст. Цепочка x0∈Σ*, появившаяся в верхней части магазина после первого движения, может быть удалена только, если входная цепочка x начинается на x0.
Ret 63

Далее мы можем повторить рассуждения, аналогичные предыдущим, относя их к цепочкам xi∈Σ*, yi’∈Δ’ (i = 1, 2, …, m) и Bj∈N ( j = 2, …, m), последовательно появ-ляющимся в верхней части магазина в результате серии движений, построенных в соответствии с п.2, затем п.3, и ряда движений, приводящих к понижению вершины магазина ниже позиции, занимаемой Bj.

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

Пример 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 есть
P = ({q}, {a, +, *}, {E, a, +, *, a’, +’, *’}, {a, +, *}, δ,
q, E, ∅), где
δ(q, ε, E) = { (q, +EE+’, ε),
(q, *EE*’, ε),
(q, aa’, ε)},
2) δ(q, b, b) = {( q, ε, ε)} для всех b∈{a, +, *},
3) δ(q, ε, с’) = {( q, ε, с)} для всех с∈{a, +, *}.

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

Из (1.15) следует, что существует правило
[qZp] → a[q1Z1q2]…[qmZmqm+1],
y[q1Z1q2]…[qmZmqm+1]∈R,
которое обязано своим происхождение тому, что
(q1, Z1…Zm, y)∈δ(q, a, Z). (1.16)

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

Пример 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

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

Положим 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] → ε, *}.

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