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

UptoLike

ВУЗ: 

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

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

Рубрика: 

219
1. Существует LR(k)-ситуация [A
1
→α
1
.Xα
2
, v
1
]∈
V
G
k
(
′
γ
), допустимая для
активного префикса
′
γ.
2. Посредством шага 2а алгоритма построения множества
V
G
k
(γ) получается
LR(k)-ситуация [A
1
→α
1
X.α
2
, v
1
]∈
V
G
k
)
X
′
(
γ
=
V
G
k
(γ).
Случай 1:
[A
1
→α
1
X.α
2
, v
1
]=[A →β
1
.β
2
, u], т.е. рассматриваемая LR(k)-си-
туация получена на этом шаге алгоритма.
Из того, что [A
1
→ α
1
.Xα
2
, v
1
]∈
G
k
V
′
(
γ)
в соответствии с индукционным
пред-положением следует существование вывода вида
S
rm
*
⇒
α
0
A
1
w
1
rm
⇒
α
0
α
1
Xα
2
w
1
= γ’Xβ
2
w
1
= γβ
2
w
1
, причём
FIRST
G
k
(w
1
)=v
1
.
Другими словами, [A →β
1
.β
2
, u] — LR(k)-ситуация, допустимая для актив-
ного префикса γ.
Случай 2:
данная LR(k)-ситуация получена посредством замыкания
[A
1
→α
1
X.α
2
, v
1
] ∈
V
G
k
(γ). Это значит, что согласно алгоритму данная LR(k)-си-
туация [A →β
1
.β
2
, u] получается посредством нескольких шагов 2б, производя-
щих последовательность LR(k)-ситуаций следующим образом:
α
2
=A
2
δ
2
, ∃ A
2
→ α
3
∈ P, и шаг 2б даёт [A
2
→.α
3
, v
2
]∈
V
G
k
(γ),
где v
2
∈
FIRST
G
k
(δ
2
v
1
), т.е. ∃ δ
2
rm
*
⇒
w
2
и v
2
=
FIRST
G
k
(w
2
v
1
);
α
3
=A
3
δ
3
, ∃ A
3
→ α
4
∈ P, и шаг 2б даёт [A
3
→ .α
4
, v
3
]∈
V
G
k
(γ),
…
α
m
= A
m
δ
m
, ∃ A
m
→ α
m +1
∈ P, и шаг 2б даёт
[A
m
→ .α
m +1
, v
m
]=[A →β
1
.β
2
, u]∈
V
G
k
(γ),
где
*
1
rm
FIRST ( ), ò. å. è
G
mkmm òm
vv w
−
∈δ ∃δ⇒
Кроме того, из равенства двух LR(k)-ситуаций следует A
m
= A, β
1
= ε,
α
m +1
= β
2
, v
m
= u; также существует правило A →β
2
.
Извлечем теперь полезные следствия из вышеизложенной истории.
Из
п.1 согласно индукционной гипотезе следует существование вывода вида
в котором
11
FIRST ( ) { }.
G
k
wv=
Благодаря п.3 этот вывод может быть продолжен следующим образом:
β
1
γ’
β
2
γ
*
32 3
rm
где FIRST ( ), т.е. и
G
k
vv w
33
∈δ∃δ⇒
121
FIRST ( ) FIRST ( ... ).
GG
mkmm km
vwv wwv
−
∈=
332 321
FIRST ( ) FIRST ( );
GG
kk
vwv wwv∈=
*
11 1 1 2 1
rm rm
,SAw XwXwAw
0012 2 2
′
⇒α ⇒α α α =γ α =γ δ
** * *
21 2 1 3 1 3 1 3 1 1
rm rm rm rm rm
1
rm
...
, ... è FIRST ( ) { } { }.
mm
G
mkm
S A w Aww ww A ww Awww Aw ww
Aw w w w w w w v u
22 23232 2
22
⇒γ δ ⇒γ ⇒γα =γ δ ⇒γ ⇒γ =
=γ ⇒γβ = = =

Страницы