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

UptoLike

ВУЗ: 

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

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

Рубрика: 

151
Теорема 1.3. Пусть T = (N, Σ, ∆, R, S) — простая семантически одно-
значная схема синтаксически управляемой трансляции, правила которой
занумерованы как 1, 2, …, p. Существует детерминированный магазинный
преобразователь P, такой, что τ
e
(P) = {(π, y) | (S, S) (x, y) для некоторой
цепочки x∈Σ
*
}.
Говоря неформально, выходная цепочка трансляции y может быть сгенери-
рована детерминированным магазинным преобразователем (dpdt) по левосто-
роннему анализу π входной цепочки x.
Доказательство. Построим dpdt P, о котором идёт речь, положив
P = ({q}, {1, 2,…, p}, N ∪∆, ∆, δ, q, S, ∅),
где δ определяется следующим образом:
1. δ(q, i, A)=(q, β, ε), если A →α, β — i-е правило схемы, единственное,
начинающееся на A →α.
2. δ(q, ε, b)=(q, ε, b) для всех b ∈∆.
Магазинный преобразователь P — детерминирован, так как правила вида 1
применимы, только если на вершине магазина находится нетерминал, а
правила вида 2 используются только тогда, когда на вершине магазина
находится выходной символ. Остаётся доказать, что построенный dpdt P
действительно реализует требуемую трансляцию.
I. Индукцией по длине вывода l покажем, что если для любого A ∈N
существует левосторонний вывод (A, A)
(x, y), то (q, π, A, ε)
(q, ε, ε, y).
База. Пусть l = 1. На единственном шаге вывода (A, A) (x, y) применяется
правило схемы A → x, y с номером i. В соответствии с п.1 построения δ(q, i, A)=
(q, y, ε), и тогда (q, i, A, ε)
(q, ε, y, ε)
(q, ε, ε, y). Последний переход
совершён согласно п.2 построений, так как y ∈∆
*
.
Индукционная гипотеза. Предположим, что подобное утверждение
выполняется для всех выводов длиной l ≤ n (n ≥ 1).
Индукционный переход. Покажем, что утверждение выполняется и для
l = n + 1.
Пусть
(A, A) (x
0
A
1
x
1
A
2
…A
m
x
m
, y
0
A
1
y
1
A
2
…A
m
y
m
) (x,y) — вывод длиной
n + 1, |π’ | = n, A, A
j
∈N , x
j
∈Σ
*
, y
j
∈∆
*
, j = 1,2,…,m. На первом шаге приме-
няется
правило схемы A → x
0
A
1
x
1
A
2
…A
m
x
m
,y
0
A
1
y
1
A
2
…A
m
y
m
, имеющее номер i.
Согласно п.1
δ(q, i, A) = (q, y
0
A
1
y
1
A
2
…A
m
y
m
, ε). (1.18)
Одновременно ясно, что
x = x
0
t
1
x
1
t
2
…t
m
x
m
, y= y
0
z
1
y
1
z
2
…z
m
y
m
, π = iπ
1
π
2
…π
m
, (1.19)
где (A
j
, A
j
) (t
j
, z
j
), |π
j
|≤n, и, следовательно, по индукционной гипотезе
(q, π
j
, A
j
, ε)
(q, ε, ε, z
j
) для j = 1,2,…,m. (1.20)
Принимая во внимание (1.18)–(1.20), а также п.2, можем написать:
(q, π, A, ε) = (q, iπ
1
π
2
…π
m
, A, ε) (q, π
1
π
2
…π
m
, y
0
A
1
y
1
A
2
…A
m
y
m
, ε)
(q, π
1
π
2
…π
m
, A
1
y
1
A
2
…A
m
y
m
, y
0
)
(q, π
2
…π
m
, y
1
A
2
…A
m
y
m
, y
0
z
1
)
…
…
(q, ε, y
m
, y
0
z
1
y
1
…z
m
)
(q, ε, ε, y
0
z
1
y
1
…z
m
y
m
)=(q, ε, ε, y).
*
P
−
−
*
P
−−
*
P
−−
*
P
−
−
*
P
−−
*
P
−−
*
P
−
−
P
−
−
*
P
−−
*
P
−
−
P
−
−
lm
j
π
⇒
lm
π
⇒
lm
π
⇒
lm
i
⇒
lm
i
⇒
lm
′
π
⇒

Страницы