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

UptoLike

ВУЗ: 

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

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

Рубрика: 

225
Определение 3.13. Будем говорить, что LR(k)-таблица T(A ) соответству-
ет активному префиксу γ, если A =
V
G
k
(γ).
Определение 3.14. Канонической системой LR(k)-таблиц для cfg G назовем
пару (T , T
0
), где T — множество LR(k)-таблиц, соответствующих канонической
системе множеств
LR(k)-ситуаций для G, а T
0
= T(A
0
), где A
0
=
V
G
k
(ε).
Обычно LR(k)-анализатор представляется управляющей таблицей, каждая
строка которой является LR(k)-таблицей.
Определение 3.15. Описанный ранее алгоритм 3.1 (см. § 3.3), если он
использует каноническую систему LR(k)-таблиц, назовем каноническим LR(k)-
алгоритмом разбора или просто каноническим LR(k)-анализатором.
Алгоритм 3.5: построение канонического LR(k)-анализатора.
Вход:
G =(V
N
, V
T
, P, S) — LR(k)-грамматика, k ≥ 0.
Выход: (T , T
0
) — каноническая система LR(k)-таблиц для грамматики G.
Метод.
1. Построить каноническую систему множеств LR(k)-ситуаций S для
грамматики G.
2. Взять T ={T(A ) | A ∈ S }в качестве множества LR(k)-таблиц.
3. Положить T
0
=T(A
0
), где A
0
=
V
G
k
(ε).
Пример 3.12. Построим каноническую систему LR(k)-таблиц для грам-
матики из примера 3.10, содержащей следующие правила:
0)
S
′
→ S, 1) S → SaSb, 2) S → ε,
учитывая результаты построения системы множеств LR(k)-ситуаций и функции
GOTO, приведённые в этом примере.
Поскольку
A
0
={[
S
′
→ .S, ε], [S → .SaSb, ε | a], [S → ., ε | a]}, то T
0
=(f
0
, g
0
)
имеет следующий табличный вид:
f
0
(u) g
0
(X )
a b
ε
S a b
reduce 2 error reduce 2 T
1
error error
Поскольку A
1
={[
S
′
→ S., ε], [S → S.aSb, ε | a]}, то T
1
= ( f
1
, g
1
) имеет следую-
щий табличный вид:
f
1
(u) g
1
(X )
a b
ε
S a b
shift error accept error T
2
error
Поскольку A
2
={[S → Sa.Sb, ε | a], [S → .SaSb, a | b], [S → ., a | b]}, то T
2
= ( f
2
, g
2
)
имеет следующий табличный вид:
f
2
(u) g
2
(X )
a b
ε
S a b
reduce 2 reduce 2 error T
3
error error

Страницы