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

UptoLike

ВУЗ: 

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

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

Рубрика: 

232
Пример 3.13. Пусть имеется схема синтаксически управляемой трансляции
T =
({S}, {a, b}, {a, b}, {1) S → Sa, aSa, 2) S → Sb, bSb, 3) S →ε, ε}).
Очевидно, что её входная грамматика — LR(1). Действительно,
каноническая система
множеств допустимых LR(1)-ситуаций для этой
грамматики S ={A
0
, A
1
, A
2
, A
3
} — не противоречива, ибо
A
0
={[
S
′
→ .S, ε], [S → .Sa, εab], [S → .Sb, εa b], [S → ., εab]},
A
1
= GOTO(A
0
, S) = {[
S
′
→ S., ε], [S → S.a, εab], [S → S.b, εab]},
A
2
= GOTO(A
1
, a) = {[S → Sa., εab]},
A
3
= GOTO(A
1
, b) = {[S → Sb., εab]}.
Этому множеству соответствует управляющая таблица LR(1)-анализатора
(табл. 3.5).
Таблица 3.5
f (u) g(X)
T
a b
ε
S a b
T
0
reduce 3 reduce 3 reduce 3 T
1
error error
T
1
shift shift accept error T
2
T
3
T
2
reduce 1 reduce 1 reduce 1 error error error
T
3
reduce 2 reduce 2 reduce 2 error error error
Построенный канонический LR(1)-анализатор для входной цепочки bba
выдаёт правосторонний
анализ π
R
(bba) = 3221, так как
(
T
0
, bba, ε)
(T
0
ST
1
, bba,3)
(T
0
ST
1
bT
3
, ba, 3)
(T
0
ST
1
, ba, 32)
(
T
0
ST
1
bT
3
, a, 322)
(T
0
ST
1
, a, 322)
(T
0
ST
1
aT
2
, ε, 3221)
(T
0
ST
1
, ε, 3221).
Данная схема задаёт трансляцию
τ(T) =
{(w, w
R
w) | w ∈ {a, b}
*
}.
В частности, имеем вывод
(S, S)
(1)
rm
⇒
(Sa, aSa)
()
2
rm
⇒
(Sba, abSba)
()
2
rm
⇒
(Sbba, abbSbba)
()
3
rm
⇒
(bba, abbbba).
То, что в начале и в конце выходной цепочки должна быть порождена
буква a, определяется лишь в момент, когда сканирование входной цепочки
заканчивается и выясняется, что правилом (1) порождается буква a.
Следовательно, выдача на выход может начаться только после того, как вся
входная цепочка прочитана. Естественный способ получить на выходе цепочку
w
R
— запомнить w в магазине, а затем выдать цепочку w
R
на выход, выбирая её
символы из магазина. Далее требуется на выходе сгенерировать цепочку w, но
в магазине, пустом к этому времени, нет для этого никакой информации. Где
ещё, помимо магазина, могла бы быть информация для восстановления
цепочки w? — Только в состояниях управления детерминированного
магазинного преобразователя (dpdt). Но и там невозможно сохранить
информацию обо всей входной цепочке, так как она может быть сколь угодно
большой длины. Короче говоря, dpdt, который мог бы реализовать описанную
трансляцию, не существует.
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A

Страницы