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

UptoLike

ВУЗ: 

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

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

Рубрика: 

145
исходной конфигурации к конечной даёт основание утверждать, что вход x
представим в виде
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
), l
i
≤ n, i = 1,2,…, m. (1.7)
По построению первое движение (1.4) обусловлено существованием правила
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) по индукционному предположению следует
существование выводов
(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).
В частности, при 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 эквивалентный магазинный преобразователь есть
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, +,
*
}.
Сравните этот недетерминированный магазинный преобразователь с
эквивалентным детерминированным pdt из примера 1.3. Оба преобразуют
префиксные арифметические выражения в постфиксные.
Лемма 1.2. Пусть P=(Q, Σ, Γ, ∆, δ, q
0
, Z
0
, ∅) — недетерминированный
магазинный преобразователь. Существует простая схема синтаксически-
управляемой трансляции T, такая, что
τ(T ) = τ
e
(P).
Доказательство. Построим такую схему T следующим образом.
Положим T =(N,
Σ, ∆, R, S), где N ={S} ∪ {[qZp] | q, p ∈Q, Z ∈Γ}, Σ и ∆ —
такие же, как в pdt P,
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 +1; q
m +1
= p}.
I. Докажем сначала, что если (q, x, Z, ε)
(p, ε, ε, y), то ([qZp], [qZp]) (x, y),
используя индукцию по числу l движений магазинного преобразователя P.
База. Пусть l = 1. Имеем (q, x, Z, ε)
(p, ε, ε, y). В этом случае x ∈Σ∪{ε} и
(p, ε, y)∈δ(q, x, Z).
i
l
P
−−
*
T
⇒
T
⇒
*
T
⇒
*
T
⇒
*
P
−
−
P
−
−

Страницы