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

UptoLike

ВУЗ: 

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

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

Рубрика: 

223
Согласно индукционной гипотезе
V
G
k
(
′
γ
)=
′
A ∈ S. Кроме того, в соответ-
ствии с алгоритмом 3.3,
GOTO( , ) GOTO( ( ) ( )
GG
kk
XVXV
′′
==γ),=γAA
включает-
ся во множество S.
Утверждение II доказано. Из рассуждений I и II следует утверждение
теоремы.
§ 3.5. Тестирование LR(k)-грамматик
Здесь мы рассмотрим метод проверки, является ли данная cfg LR(k)-грам-
матикой при заданном значении
k ≥ 0.
Определение 3.11. Множество A =
V
G
k
(γ)∈ S назовем непротиворечивым,
если
оно не содержит двух разных LR(k)-ситуаций вида [A →β., u] и [B →β
1
.β
2
, v]
(цепочка β
2
может быть пустой), таких, что u∈
EFF
G
k
(β
2
v).
Алгоритм 3.4: LR(k)-тестирование.
Вход: G =(V
N
, V
T
, P, S) — контекстно-свободная грамматика, k ≥ 0.
Выход: “Да”, если G — LR(k)-грамматика. “Нет” в противном случае.
Метод.
1. Построим каноническую систему S множеств LR(k)-ситуаций, допусти-
мых для грамматики
G.
2. Каждое A ∈ S проверим на непротиворечивость. Если окажется, что рас-
сматриваемое множество A противоречиво, то алгоритм заканчивается с
ответом “Нет”.
3. Если алгоритм не закончился на шаге 2, то он выдаёт ответ “Да” и
завершается.
Замечание 3.5. При тестировании достаточно просматривать лишь множества A ∈ S,
в которых имеется хотя бы одна
LR(k)-ситуация вида [A →β., u] (с точкой в конце
правила).
Пример 3.11. Протестируем грамматику примера 3.10, содержащую
следующие правила: 0)
S
′
→ S, 1) S → SaSb, 2) S → ε.
В соответствии с замечанием 3.5 необходимо и достаточно проверить лишь
непротиворечивость множеств
01234567
,,,,,,,,AAAAAAAAпостроенных в пре-
дыдущем примере (новая нумерация).
Проверка A
0
= {[
S
′
→ .S, ε], [S → .SaSb, ε | a], [S → ., ε | a]}:
u ∈ {ε,a}, u∉
1
EFF
G
(S{ε}) = ∅; u∉
1
EFF
G
(SaSb{ε, a}) = ∅.
Вывод: множество A
0
, непротиворечиво.
Проверка A
1
={[
S
′
→ S., ε], [S → S.aSb, ε | a]}:
u = ε, u∉
1
EFF
G
(aSb{ε, a}) ={a}.
Вывод: множество A
1
непротиворечиво.
Проверка A
2
={[S → Sa.Sb, ε | a], [S → .SaSb, a | b], [S → ., a | b]}:
u∈ {a,b}, u∉
1
EFF
G
(Sb{ε, a}) = ∅, u∉
1
EFF
G
(SaSb{a, b}) = ∅.
Вывод: множество A
2
непротиворечиво.

Страницы