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

UptoLike

ВУЗ: 

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

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

Рубрика: 

147
Кроме того, из (1.14) следует, что
x = ax
1
x
2
…x
m
, y = y
0
y
1
y
2
…y
m
, (1.16)
([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
), i = 1, 2,…, m; q
m +1
= p. (1.17)
Из (1.15) и (1.17) с учётом (1.16) выстраивается последовательность
движений:
(q, x, Z, ε) = (q, ax
1
x
2
…x
m
, Z, ε) (q
1
, x
1
x
2
…x
m
, Z
1
Z
2
…Z
m
, y
0
)
(p, ε, ε, y
0
y
1
y
2
…y
m
) = (p, ε, ε, y).
Из рассуждений I и II следует, что для любых q,p∈Q и Z∈Γ вывод
([qZp], [qZp]) (x, y) существует тогда и только тогда, когда
(q, x, Z, ε) (p, ε, ε, y).
В частности, это справедливо для Z = Z
0
.
В то же время при помощи правила вида 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, x, Z
0
, ε) (p, ε, ε, y). Лемма доказана.
Из лемм 1.1 и 1.2 следует
Теорема 1.1. Трансляция τ = τ(T ), где T — простая схема синтаксически
управляемой трансляции тогда и только тогда, когда существует недетерми-
нированный магазинный преобразователь P, такой, что τ
e
(P) = τ.
Пример 1.5. В предыдущем примере по простой SDTS T = ({E}, {a, +,
*
},
{a, +,
*
}, R, E), где R = {(1) E → +EE, EE+ (2) E →
*
EE, EE
*
(3) E → a, a},
был построен эквивалентный магазинный преобразователь
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, +,
*
}.
Теперь по этому недетерминированному преобразователю P мы построим
эквивалентную простую схему синтаксически управляемой трансляции, вос-
пользовавшись алгоритмом, описанным в лемме 1.2.
Положим T = ({S, [qEq], [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, ε (7) [q
*
q] →
*
, ε (9) [q+’q] → ε, +
(6) [q+q] → +, ε (8) [qa’q] → ε, a (10) [q
*
’q] → ε,
*
}.
i
l
P
−
−
i
l
T
⇒
P
−
−
*
P
−−
*
P
−−
*
P
−−
*
T
⇒
*
P
−
−
T
⇒
*
T
⇒

Страницы