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

UptoLike

ВУЗ: 

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

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

Рубрика: 

236
Системе объединённых множеств LR(1)-ситуаций соответствует управляю-
щая таблица (табл. 3.6).
Таблица 3.6
Отметим, что анализатор, использующий LALR(k)-таблицы, может чуть
запаздывать с обнаружением ошибки по отношению к анализатору, исполь-
зующему каноническое множество LR(k)-таблиц.
Например, канонический LR(1)-анализатор для рассматриваемой грам-
матики (см. пример 3.15) обнаруживает ошибку в цепочке abb, достигнув пятой
конфигурации:
(T
0
, abb, ε) (T
0
ST
1
, abb, 2) (T
0
ST
1
aT
2
, bb, 2) (T
0
ST
1
aT
2
ST
3
, bb, 22)
(T
0
ST
1
aT
2
ST
3
bT
5
, b, 22) ,
а LALR(1)-анализатор
— на шестой:
(T
0
, abb, ε)
(T
0
ST
1
, abb, 2) (T
0
ST
1
aT
24
, bb, 2) (T
0
ST
1
aT
24
ST
36
, bb, 22)
(T
0
ST
1
aT
24
ST
36
bT
57
, b, 22)
(T
0
ST
1
, b, 221).
Упражнения
II.3.1. Дана КС-грамматика G = (V
N
, V
T
, P, S), где
V
N
= {E, T, F}, V
T
= {a, +,
*
, (, )}, S = E,
P = {(1) E → E + T, (2) E → T,
(3) T → T
*
F, (4) T → F,
(5) F → (E), (6) F → a }.
Определить, является ли G
LR(1)-грамматикой?
Если это так, простроить канонический анализатор Кнута, а если она
LALR(1), то минимизировать его.
II-3.2. Дана расширенная КС-грамматика
G = (V
N
, V
T
, P, S), где V
N
= {E′, E, A, B, T, F},
V
T
= {a, +,
*
, (, )}, S = E′,
P ={ (0) E′ → E,
(1) E → T, (2) E → F, (3) E → a,
(4) A → T, (5) A → F, (6) A → a,
(7) B → (T), (8) B → F, (9) B → a,
(10) C → (T), (11) C → (F), (12) C → a,
(13) T → A + B, (14) F → B * C }.
f(u) g(X) LALR(1)-
таблицы
a b
ε
S
a b
T
0
reduce 2
reduce 2 T
1
T
1
shift
accept
T
24
T
24
reduce 2 reduce 2 T
36
T
36
shift shift T
4
T
57
T
57
reduce 1 reduce 1
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A

Страницы