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

UptoLike

ВУЗ: 

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

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

Рубрика: 

193
схемы, является правильным. Модификация, превращающая его в LL(k)-
транслятор, фактически состоит в том, что когда анализатор, моделируя шаг
левостороннего вывода, замещает некоторую LL(k)-таблицу T
A,L
образом
правой части правила A → x
0
A
1
x
1
A
2
...A
m
x
m
вида
11 22
,, ,
01
...
mm
AL A L A L m
x
TxT T x, транс-
лятор “подмешивает” к этой магазинной цепочке выходные символы из
семантической цепочки соответствующего правила схемы таким образом, что
полученная смесь
11 22
,,,
00 11
...
mm
AL A L A L m
m
x
yT xyT T xy
′
′
′
в магазине обеспечивает точ-
ное воспроизведение движений анализатора и синхронизированную с ними
генерацию соответствующей цепочки на выходной ленте. Действительно,
выполнив pop-движения
и продвинувшись по фрагменту x
i
входной цепочки,
который является также и фрагментом правила входной грамматики
A → x
0
A
1
x
1
A
2
...A
m
x
m
, транслятор тут же выдаёт на выход соответствующий
фрагмент y
i
выходной цепочки, который также является и фрагментом
семантической цепочки соответствующего правила схемы
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
.
Теорема 2.11. Пусть T = (N, Σ, ∆, R, S) — простая семантически
однозначная схема синтаксически управляемой трансляции
с входной
грамматикой G
i
класса LL(k). Существует детерминированный магазинный
преобразователь P, такой, что τ
e
= {(x$, y) | (x, y)∈τ(T)}.
Доказательство. Заметим, что входная цепочка трансляции, реализуемой
магазинным преобразователем, всегда имеет маркер конца, тогда как схема
порождает трансляцию с входами без такого маркера. Маркер необходим,
чтобы гарантировать детерминизм магазинного преобразователя.
Доказательство основано на построении dpdt, моделирующего движения
k-предсказывающего алгоритма трансляции, адекватного данной схеме,
который согласно теореме 2.6 существует.
Итак, пусть построен k-предсказывающий алгоритм трансляции
ℑ = (Σ, ∆, Γ∪{$}, M, T
0
, $).
Положим dpdt
P = (Q, Σ ∪ {$}, Γ∪{$},∆, δ, q
0
, $, ∅),
где Σ и Γ — те же, что и в ℑ; Q = {q
0
} ∪ {[u] | u ∈Σ
*
k
} ∪ {[v$] | v ∈Σ
*
k –1
}.
1. δ(q
0
, ε, $) = ([ε], T
0
$, ε) — моделирует начальную конфигурацию ℑ.
2. δ([v], a, T ) = ([va], T, ε), v ∈Σ
*
k –1
, a ∈Σ, T∈T — накопление аванцепочки.
3. δ([v], $, T) = ([v$], T, ε), v∈Σ
*
k–1
, T∈T — накопление короткой аванцепочки.
4. δ([u], ε, T ) = ([u], β, ε), u∈Σ
*
k
, T∈T , M(T, u)=β — моделирование
движения типа 1 .
5. δ([v$], ε, T ) = ([v$], β, ε), v ∈Σ
*
k –1
, T∈T , M(T, v)=β — моделирование
движения типа 1 при короткой аванцепочке.
6. δ([av], ε, a) = ([v], ε, ε), a ∈Σ, v∈Σ
*
k –1
— моделирование pop-движения.
7. δ([av$], ε, a) = ([v$], ε, ε), a∈Σ, v∈Σ
*
k–2
— моделирование pop-движения при
короткой аванцепочке.
8. δ([u], ε, b’) = ([u], ε, b), b∈∆, v∈Σ
*
k
— моделирование pass-движения.

Страницы