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

UptoLike

ВУЗ: 

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

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

Рубрика: 

213
11 1 2 21 221 1 21
rm rm rm rm rm
121 121 121
rm
rm
****
*
2 ) ...
... ... ... ,
mmm
mmm mm mm
SAy y Ay Ayy Ayyy
Ayy yy Byy yy yy yy y
1 112 11 11 11 −
11 − 11 − 11 −
′′ ′
⇒α ⇒αββ =αβ α ⇒αβ ⇒αβ α ⇒
⇒αβ =αβ ⇒αβ =αβ
где α
1
β
1
= αβ, A
m
= B, y
m
y
m–1
…y
2
y
1
= y.
Отметим, что |α
1
β
1
B| = |αβ| +1, но это противоречит предположению, что
α
1
A
1
y
1
— последняя цепочка в этом выводе, открытая часть которой имеет
длину, не превосходящую величину |αβ| +1. Следовательно, u ∈
EFF
G
k
(β
2
v).
Мы нашли две LR(k)-ситуации, допустимые для одного и того же активного
префикса αβ: [A →β.,
u] и [A
1
→β
1
.β
2
, v] при том, что u ∈
EFF
G
k
(β
2
v).
Поскольку с самого начала предполагалось, что не существует двух таких
разных LR(k)-ситуаций, то должно быть [A →β.,
u]=[A
1
→β
1
.β
2
, v]. Из этого
равенства следует: A = A
1
, β = β
1
, β
2
= ε.
Кроме того, поскольку α
1
β
1
= αβ, а
β
1
= β, то α
1
= α. С учётом этого вывод
2)
′
′
можем переписать так:
откуда заключаем, что y
1
= y.
Не забывая, что это другой вид того же самого вывода 2), заменим цепочку
β на A, и получим цепочку αβy, которая совпадает с предыдущей сентен-
циальной формой в этом выводе. Это означает нарушение условия б)
γBx ≠αAy. Данное противоречие — следствие неправомерного допущения, что
G — не LR(k)-грамматика. Следовательно, G — LR(k)-грамматика.
Достаточность доказана. Теорема также доказана.
Определение 3.8. Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная грамма-
тика и γ∈ (V
N
∪ V
T
)
*
— некоторый её активный префикс. Определим множество
V
G
k
(γ) как множество всех LR(k)-ситуаций, допустимых для γ:
rm
*
() [ , ] ; ,
=, FIRST()
{
}.
G
k
rm
G
k
VAuAPSAww
uw
1 2 12 12
1
′
γ = →β .β ∃ →ββ ∈ ∃ ⇒α ⇒αββ
γαβ ∈
Множество
S = {A | A =
V
G
k
(γ), где γ — активный префикс G } назовем
системой множеств LR(k)-ситуаций для грамматики G.
Алгоритм 3.2: вычисление множества
V
G
k
(γ).
Вход:
G =(V
N
, V
T
, P, S) — контекстно-свободная грамматика,
γ = X
1
X
2
...X
m
, X
i
∈ V
N
∪ V
T
, i =1, 2,…, m; m ≥ 0.
Выход: множество
V
G
k
(γ).
Метод.
Будем строить последовательность множеств
V
G
k
(ε),
V
G
k
(X
1
),
V
G
k
(X
1
X
2
),...,
V
G
k
(X
1
X
2
...X
m
).
1. Строится множество
V
G
k
(ε).
а) Инициализация:
V
G
k
(ε) = {[S→.α, ε] | ∃ S → α∈ P }.
11
rm rm
*
2) ,SAy yy
1
′′ ′
⇒α ⇒αβ =αβ

Страницы