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

UptoLike

ВУЗ: 

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

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

Рубрика: 

142
Данный магазинный преобразователь является примером детерминирован-
ного магазинного преобразователя. Очевидно, что он преобразует префиксные
арифметические выражения в постфиксные.
Определение 1.10. Магазинный преобразователь P =(Q, Σ, Γ, ∆, δ, q
0
, Z
0
, F)
называется детерминированным (dpdt deterministic pushdown transducer) ,
если
1) #δ(q, a, Z) ≤ 1 для всех q ∈Q, a ∈Σ∪{ε} и Z ∈Γ;
2) если δ(q, ε, Z) ≠∅ для данных q ∈Q и Z ∈Γ, то δ(q,a,Z)=∅ для всех
a ∈Σ.
На практике предпочитают использовать dpdt, поскольку в реализации они
оказываются более эффективными по сравнению с недетерминированными pdt.
Лемма 1.1. Пусть T=(N, Σ, ∆, R, S) — простая схема синтаксически
управляемой трансляции. Существует недетерминированный магазинный пре-
образователь P, такой, что τ
e
(P) = τ(T ).
Доказательство. Построим pdt P, о котором идёт речь, и покажем, что он
реализует трансляцию τ(T ).
Положим P = ({q}, Σ, N ∪Σ∪∆
′
, ∆, δ, q, S, ∅). Чтобы отличать в магазине P
входные символы от выходных, последние переименовываются с помощью
гомоморфизма h, определяемого для каждого выходного символа b∈∆ при помощи
равенства h( b)=b
′
таким образом, чтобы множество символов ∆
′
= { b
′
| b ∈∆}
не пересекалось со словарем Σ, т.е. Σ∩∆
′
= ∅.
Отображение δ определяется так:
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 ∈∆.
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. Согласно п.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).
Индукционная гипотеза. Предположим, что вспомогательное утверж-
дение выполняется для всех выводов длиной 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)
*
P
−
−
*
P
−−
*
P
−
−
P
−
−
*
T
⇒
*
T
⇒
T
⇒
T
⇒
n
T
⇒
i
l
T
⇒
_
_
x
P
_
_
y
P

Страницы