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

UptoLike

ВУЗ: 

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

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

Рубрика: 

191
Таблица 2.7
Аванцепочки
Маг.
сим-ы
aa ab ba bb a b
ε
T
0
aa
’
T
1
aaa
’
a
’
aa
’
T
1
aaa
’
a
’
b·T
2
baÒa
’
T
1
e
bb
’
T
2
e
bb
’
a pop pop pop
b pop pop pop
a
’
pass pass pass pass pass pass pass
b
’
pass pass pass pass pass pass pass
e pass pass pass pass pass pass pass
·
pass pass pass pass pass pass pass
Ò
pass pass pass pass pass pass pass
$ accept
Для иллюстрации работы только что построенного 2-предсказывающего
алгоритма трансляции рассмотрим обработку входной цепочки
bba:
(bba, T
0
$, ε) (bba, b·T
2
baÒa’$, ε) (ba, ·T
2
baÒa’$, ε)
(ba, T
2
baÒa’$, ·) (ba, ebaÒa’$, ·)
(ba, baÒa’$, ·e) (a, aÒa’$, ·e) (ε, Ò$, ·e)
(ε, a’$, ·eÒ) (ε, $, ·eÒa).
Итак, ℑ(bba)=
·eÒa. Нетрудно проверить, что (S, S)
*
T
⇒ (bba, ·eÒa).
Замечание 2.2. Если входная грамматика схемы — LL(1)-грамматика или сильная
LL(k)-грамматика, то очевидно, что можно обойтись без построения LL(k)-таблиц, как
показано на следующем примере.
Пример 2.14. Пусть T = ({E, E’, T, T’, F}, {a, +,
*
, (, )}, {a, +,
*
}, R, E), где
{ ( 1 ) ,
(2) ,
(3) ,
(4) ,
RETETE
ETETE
E
TFTFT
′′
=→
′
′′
→+ +
′
→ε ε
′′
→
Очевидно, что T — простая, семантически однозначная SDTS с входной
грамматикой LL(1). Посредством алгоритма 2.8 получаем следующий 1-
предсказывающий алгоритм трансляции:
ℑ
где M представлена в табл. 2.8.
(5) ,
*
*
(6) ,
(7) ( ),
(8) , }.
TFTFT
T
FEE
Faa
′
′′
→
′
→ε ε
→
→
−
−
−
−
−
−
−
−
−
−
−
−
−
−
−
− −−
−
−
−
−
−
−
= ({ , , , (, )}, { , , , , , , , , (, ), , , , $}, { , , }), , ,$),
***
*
aEETTFaa aME
′′ ′′
++++
'

Страницы