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

UptoLike

ВУЗ: 

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

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

Рубрика: 

216
Следовательно, w = w
m
w
m –1
...w
1
, A = A
m
и существуют правила
S → A
1
α
1
, A
1
→ A
2
α
2
,..., A
m –1
→ A
m
α
m
= Aα
m
, A →β
2
.
Кроме того,
FIRST ( ) FIRST ( ),
GG
ii
kk
w ∈α
поскольку α
i
rm
*
⇒
w
i
, i =1, 2,…, m.
Согласно алгоритму 3.2
[S → .A
1
α
1
, ε]∈ (),
G
k
V ε
[A
1
→.A
2
α
2
,v
1
]∈
()
G
k
V ε
для любой v
1
∈
FIRST
G
k
(α
1
ε),
в частности для v
1
∈
FIRST
G
k
(w
1
);
[A
2
→ .A
3
α
3
,v
2
]∈ ()
G
k
V ε для любой v
2
∈
FIRST
G
k
(α
2
v
1
),
в частности для v
2
∈
FIRST
G
k
(w
2
v
1
)=
21
FIRST ( );
G
k
ww
...
[A
m –1
→ A
m
α
m
, v
m –1
]∈
V
G
k
(ε) для любой v
m –1
∈
FIRST
G
k
(α
m –1
v
m –2
),
в частности для v
m –1
∈
FIRST
G
k
(w
m –1
v
m –2
)=
FIRST
G
k
(w
m –1
…w
1
).
Наконец, поскольку A
m
= A и имеется правило A → β
2
, то [A →. β
2
, v
m
]∈
V
G
k
(ε)
для любой терминальной цепочки v
m
∈
FIRST
G
k
(α
m
v
m –1
), в частности, для
111
FIRST ( ) FIRST ( ... ).
GG
mmm mm
kk
vwv wvw
−−
∈=
Принимая во внимание, что w = w
m
w
m –1
...w
1
и что
FIRST ( ),
G
k
uw∈
заклю-
чаем, что v
m
= u и [A → .β
2
, u]∈
V
G
k
(ε). База доказана.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех активных префиксов γ, таких, что |γ|≤n (n ≥ 0).
Индукционный переход. Покажем, что утверждение выполняется для γ,
таких, что |γ|≤n +1.
Пусть
,
X
′
γ
где |
′
γ
| = n, а X∈ V
N
∪ V
T
. Поскольку γ — активный префикс, то
существует вывод такой сентенциальной формы, где γ участвует в этой роли:
в котором на последнем шаге применялось правило A →β
1
β
2
, и αβ
1
= γ =
.
X
′
γ
Случай 1: β
1
≠ε.
Поскольку αβ
1
=
X
′
γ
и β
1
≠ε, то именно β
1
заканчивается символом X, т.е.
X
1
1
′
β=β
при некоторой
′
β
∈ (V
N
∪ V
T
)
*
. В этом случае имеем
rm
rm
*
,S Aw w Xw Xw
12 1 2 2
′′
⇒α ⇒αββ =αβ β =γ β
где
,
1
′′
γ=αβ
|
′
γ
| = n.
В соответствии с индукционным предположением, поскольку
′
γ
является
активным префиксом
последней сентенциальной формы и |
′
γ
| = n,
[A →
1
′
β
.Xβ
2
, u]∈
G
k
V
′
(γ ),
где
FIRST ( ).
G
k
uw∈
Шаг 2a алгоритма 3.2 даёт [
.,
A
Xu
2
1
′
→β β
]=[A →β
1
.β
2
, u]∈
V
G
k
)
X
′
(γ
=
V
G
k
(γ), что и требовалось доказать.
rm
rm
*
,SAw w wXw
12 2 2
′
⇒α ⇒αββ =γβ =γ β

Страницы