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

UptoLike

ВУЗ: 

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

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

Рубрика: 

233
Однако, если простая синтаксически управляемая трансляция с входной
грамматикой класса LR(k) не требует, чтобы выходная цепочка порождалась до
того, как устанавлено, какое правило применяется, то соответствующая
трансляция может быть реализована посредством dpdt. Это приводит нас к
понятию постфиксной схемы синтаксически управляемой трансляции.
Определение 3.16. T = (N, Σ, ∆, R, S) называется постфиксной схемой
синтаксически управляемой трансляции, если каждое её правило имеет вид
A →α, β, где β∈ N
*
∆
*
.
Теорема 3.8. Пусть T = (N, Σ, ∆, R, S) — простая семантически однознач-
ная постфиксная схема синтаксически управляемой трансляции с входной
LR(k)-грамматикой. Существует детерминированный магазинный преобразо-
ватель P, такой, что τ(P) =
{(x$, y) | (x, y) ∈ τ(T)}.
Доказательство. По входной грамматике схемы T можно построить
канонический LR(k)-анализатор, а затем моделировать его работу посредством
dpdt P, накапливающего аванцепочку в состояниях и воспроизводящего
действия shift и reduce i. При этом вместо выдачи на выходную ленту номера
правила i он выдаёт выходные символы, входящие в состав семантической
цепочки этого правила.
В момент принятия входной цепочки dpdt P переходит в
конечное состояние. Именно, если правило с номером i есть A →α, βz, где β∈
N
*
,
z ∈ ∆
*
, то dpdt P выдаёт цепочку z на выход.
Технические детали построения dpdt P и доказательство его адекватности
SDTS T оставляем в качестве упражнения читателю.
Пример 3.14. Пусть имеется схема T с правилами
0)
S
′
→ S, S 1) S → SaSb, SSc 2) S → ε, ε.
Входную грамматику этой схемы, являющуюся LR(1)-грамматикой, во всех
деталях мы обсуждали ранее. По ней была построена управляющая таблица
адекватного канонического LR(1)-анализатора. Эта же таблица может быть
использована LR(1)-транслятором, который отличается от анализатора только
тем, что вместо номера правила пишет на выходную ленту выходные символы
из семантической цепочки этого правила.
Пусть имеется следующий вывод в схеме:
(S, S)
(1)
rm
⇒
(SaSb, SSc)
(1)
rm
⇒
(SaSaSbb, SSScc)
()
2
rm
⇒
(SaSabb, SScc)
()
2
rm
⇒
()
2
rm
⇒
(Saabb, Scc)
()
2
rm
⇒
(aabb, cc).
Руководствуясь табл. 3.3, LR(1)-транслятор совершает следующие
движения:
(T
0
, aabb, ε)
(T
0
ST
1
, aabb, ε)
(T
0
ST
1
aT
2
, abb, ε)
(T
0
ST
1
aT
2
ST
3
, abb, ε)
(T
0
ST
1
aT
2
ST
3
aT
4
, bb, ε)
(T
0
ST
1
aT
2
ST
3
aT
4
ST
6
, bb, ε)
(T
0
ST
1
aT
2
ST
3
aT
4
ST
6
bT
7
, b, ε)
(T
0
ST
1
aT
2
ST
3
, b, c)
(T
0
ST
1
aT
2
ST
3
bT
5
, ε, c)
(T
0
ST
1
, ε, cc).
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A

Страницы