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

UptoLike

ВУЗ: 

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

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

Рубрика: 

218
II.
Докажем теперь, что если [A →β
1
.β
2
, u]∈
G
k
V
(γ), то существует право-
сторонний вывод вида в котором αβ
1
= γ есть активный пре-
фикс правосентенциальной формыαβ
1
β
2
w, а
FIRST ( ) { }
G
k
wu=
есть правый кон-
текст основы β
1
β
2
в данной сентенциальной форме αβ
1
β
2
w.
Индукция по l = |γ|.
База. Пусть l =0, т.е. γ = ε. В этом случае αβ
1
= γ = ε, следовательно, α = ε,
β
1
= ε, и надо доказать существование вывода вида S Aw
β
2
w, в котором на
последнем шаге применяется правило A →β
2
, а
Имеем [A→.β
2
, u] ∈
G
k
V
(ε). Все LR(k)-ситуации из множества
()
G
k
V
ε
согласно алгоритму 3.2 получаются на шаге 1а или 1б. В общем случае история
попадания данной LR(k)-ситуации в множество
()
G
k
V
ε
такова:
[S → .α
1
, ε] ∈
V
G
k
(ε) благодаря шагу 1а алгоритма и правилу S →α
1
∈ P;
α
1
= A
1
δ
1
, ∃ A
1
→ α
2
∈ P, и шаг 1б даёт [A
1
→.α
2
, v
1
]∈
(),
G
k
V
ε
где т.е.
(любой вывод терминальной цепочки можно
перестроить в правосторонний) и
11
FIRST ( );
G
k
vw∈
α
2
= A
2
δ
2
, ∃ A
2
→ α
∈ P, и шаг 1б даёт [A
2
→.α
3
, v
2
]∈
V
G
k
(ε),
где т.е. и v
2
∈
FIRST
G
k
(w
2
v
1
)=
FIRST
G
k
(w
2
w
1
);
…
α
m
=A
m
δ
m
, ∃ A
m
→ α
m +1
∈ P, и шаг 1(б) даёт [A
m
→.α
m +1
, v
m
]∈
V
G
k
(ε),
где v
m
∈
FIRST
G
k
(δ
m
v
m–1
); т.е.∃ δ
m
rm
*
⇒
w
m
и v
m
∈
FIRST
G
k
(w
m
v
m–1
)=
=
FIRST
G
k
(w
m
w
m–1
…w
1
)=
FIRST
G
k
(w)={u}, A
m
= A, α
m +1
= β
2
,
w
m
w
m –1
…w
1
= w.
Используя существующие правила и упомянутые частичные выводы,
построим требуемый вывод:
S
rm
⇒
α
1
= A
1
δ
1
rm
*
⇒
A
1
w
1
rm
*
⇒
α
2
w
1
= A
2
δ
2
w
1
rm
*
⇒
A
2
w
2
w
1
rm
*
⇒
…
rm
*
⇒
A
m
δ
m
w
m –1
…w
2
w
1
rm
*
⇒
rm
*
⇒
A
m
w
m
w
m –1
…w
2
w
1
rm
⇒
α
m +1
w
m
w
m –1
…w
2
w
1
= β
2
w.
Итак,
существует вывод
S
rm
*
⇒
Aw
rm
⇒
β
2
w и
FIRST
k
(w) =
FIRST
k
(w
m
…w
1
)={u}.
База доказана.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех γ, длина которых не превосходит n (n ≥ 0).
Индукционный переход.
Покажем, что утверждение выполняется для
γ =
X
′
γ
, где |
′
γ
| = n, X ∈ V
N
∪ V
T
.
Согласно
алгоритму 3.2 LR(k)-ситуация [A → β
1
.β
2
, u] ∈
V
G
k
(γ) в общем
случае может быть получена следующим образом:
rm rm
*
,SAw w
12
⇒α ⇒αββ
11
= FIRST ( ),
G
k
v δ
11
rm
*
w∃ δ ⇒
221
= FIRST ( ),
G
k
vvδ
22
rm
*
,w∃ δ ⇒
rm
*
⇒
FIRST ( ) { }.
G
k
wu=
rm
⇒

Страницы