Языки и трансляции. Мартыненко Б.К. - 142 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

140
Трансляция, определяемая простой схемой, называется простой синтакси-
чески управляемой трансляцией.
В примере 1.2 схема T простая, как и определяемая ею трансляция τ(T).
Многие, но не все, полезные трансляции могут быть описаны как простые.
Простые синтаксически управляемые трансляции интересны тем, что
каждая из них может быть реализована транслятором в классе недетерминиро-
ванных магазинных преобразователей (рис. 1.1, пояснения в §1.3).
Рис. 1.1.
Другими словами, магазинные преобразователи характеризуют класс
простых синтаксически управляемых трансляций таким же образом, как
магазинные автоматы характеризуют класс контекстно-свободных языков. К
рассмотрению таких трансляций мы сейчас и перейдем.
§ 1.3. Магазинные преобразователи
и синтаксически управляемые трансляции
В гл.9 ч.I были описаны обобщённые последовательные машины, называе-
мые также конечными преобразователями. Здесь мы рассмотрим магазинные
преобразователи, отличающиеся от конечных, лентой памяти, используемой в
режиме магазина, как в магазинном автомате.
Определение 1.7. Магазинный преобразователь (pdt — pushdown transducer)
есть формальная система P =(Q, Σ, Γ, ∆, δ, q
0
, Z
0
, F), где Q — конечное
множество состояний, Σ — входной алфавит, Γ — алфавит магазинных
символов, ∆ — выходной алфавит, q
0
∈Q — начальное состояние, Z
0
∈Γ —
начальный символ магазина, F ⊆ Q — множество конечных состояний, δ —
отображение типа: Q × (Σ∪{ε}) ×Γ→2
Q ×Γ
*
×∆
*
.
Запись δ(q, a, Z)=
означает, что pdt P, находясь в состоянии
q ∈Q, сканируя символ a ∈Σ∪{ε} на входной ленте и имея Z ∈Γ на вершине
магазина, переходит в одно из состояний p
i
∈Q, заменяя в магазине символ Z
на γ
i
∈Γ
*
и записывая y
i
∈∆
*
на выходную ленту. При этом входная головка
сдвигается на одну ячейку вправо, если a ≠ε (иначе головка остаётся на месте),
головка магазина сканирует последнюю запись в магазине, а головка выходной
ленты размещается справа от последней её записи.
q
М
а
г
а
з
и
н
Q × (Σ∪{ε}) ×Γ
→
2
Q × Γ×∆
∗
Вход
a
1
a
2
a
3
a
n
…
Выход
b
1
b
2
b
3
b
m
…
Z
1
Z
0
Z
2
Z
k
…
q
Вход:
a
2
a
3
Z
2
1
{( , , )}
n
i
i
ii
py
=
γ
a
n
…
Z
0
Выход:
b
1
b
2
b
3
b
m
…
Z
1
М
а
г
а
з
и
н
Z
…
Q × (Σ∪{ε}) ×Γ
→ 2
Q × Γ×∆
∗
a

Страницы