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

UptoLike

ВУЗ: 

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

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

Рубрика: 

235
§ 3.10. LALR(k)-Грамматики
На практике часто используются частные подклассы LR(k)-грамматик,
анализаторы для которых имеют более компактные управляющие таблицы по
сравнению с таблицами канонического LR(k)-анализатора. Здесь мы определим
один из таких подклассов грамматик, называемых LALR-грамматиками.
Определение 3.17. Ядром LR-ситуации [А → β
1
.β
2
, u] назовем А → β
1
.β
2
.
Определим функцию CORE(A ), где A — некоторое множество LR(k)-ситуаций,
как множество ядер, входящих в состав LR(k)-ситуаций из A.
Определение 3.18. Пусть G — контекстно-свободная грамматика, S —
каноническая система множеств LR(k)-ситуаций для грамматики G и
:{ () ()}.{}CORE CORE
∈
′′ ′
=∀∈ = =
∪
BS
SA ASA B B A
Если каждое множество
′
′
∈
AS — непротиворечиво, то G называется
LALR(k)-грамматикой.
Другими словами, если слить все множества LR(k)-ситуаций с
одинаковыми наборами ядер в одно множество и окажется, что все полученные
таким образом множества LR(k)-ситуаций непротиворечивы, то G
LALR(k)-
грамматика.
Число множеств, полученных при слиянии, разве лишь уменьшится.
Соответственно уменьшится и число LR(k)-таблиц. Последние строятся
обычным образом по объединённым множествам LR(k)-ситуаций. Очевидно,
что корректность LALR(k)-анализатора, использующего таким образом
полученные таблицы, не нуждается в доказательстве.
Пример 3.15. Проверим, является ли рассмотренная раннее LR(1)-
грамматика с правилами 0)
S
′
→ S, 1) S → SaSb, 2) S →ε LALR(1)-
грамматикой.
Каноническая система множеств LR(1)-ситуаций для неё была построена в
примере 3.10:
A
0
= {[
S
′
→ .S, ε], [S → .SaSb, ε | a], [S → ., ε | a]};
A
1
= {[
S
′
→ S., ε], [S → S.aSb, ε | a]};
A
2
= {[S → Sa.Sb, ε | a], [S → .SaSb, a | b], [S → ., a | b]};
A
3
= {[S → SaS.b, ε|a], [S → S.aSb, a | b]};
A
4
= {[S → Sa.Sb, a | b], [S → .SaSb, a | b], [S → ., a | b]};
A
5
= {[S → SaSb., ε|a};
A
6
= {[S → SaS.b, a | b], [S → S.aSb, a | b]};
A
7
= {[S → SaSb., a | b]}.
Ясно, что в приведённой выше системе можно слить множества A
2
и A
4
:
A
24
= {[S → Sa.Sb, ε | a | b], [S → .SaSb, a | b], [S → ., a | b]},
множества A
3
и A
6
: A
36
= {[S → SaS.b, ε|a | b], [S → S.aSb, a | b]},
а также множества A
5
и A
7
: A
57
= {[S → SaSb., ε|a | b]}.
Полученные множества A
24
, A
36
и
A
57
не противоречивы.

Страницы