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

UptoLike

ВУЗ: 

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

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

Рубрика: 

188
Получаем
Покажем теперь, что алгоритм 2.7 действительно вычисляет функцию
()
FOLLOW
G
k
A
для любого нетерминала A.
Теорема 2.9. Пусть G = (V
N
,V
T
,P,S) — контекстно-свободная грамматика.
Алгоритм 2.7 правильно вычисляет функцию
()
FOLLOW
G
k
A
для любого A ∈V
N
и
k ≥ 0.
Доказательство. Фактически достаточно показать, что ϕ
j
(A, B) = ϕ(A, B),
если ϕ
i
(A, B) = ϕ
j
(A, B) при i > j для всех A, B∈V
N
.
I. Покажем сначала, что ϕ
j
(A, B) ⊆ϕ(A,B) или, что то же самое, если
w ∈ϕ
l
(A, B) при l ≤ j, то w ∈ϕ(A, B), используя индукцию по l.
База. Пусть l =0. Имеем w ∈ϕ
0
(A, B). Согласно шагу 1 алгоритма 2.7
существует правило A →γBα∈P, α,γ∈V
*
, и
().
FIRST
G
k
w
α
∈
Это правило
позволяет построить вывод
G
A
B⇒γ α,
причём любая цепочка
()
FIRST
G
k
w
α
∈
также является элементом множества
ϕ(A,B) — .таково определение этой
функции, т.е. w
∈ϕ(A,B). База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех l
≤ n (0 ≤ n ≤ j).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно для l = n +1.
Итак, пусть
w ∈ϕ
n +1
(A, B). Согласно шагу 2 алгоритма 2.7 либо w∈ϕ
n
(A, B) и
тогда
согласно индукционной гипотезе w∈ϕ(A, B), либо существует правило
A
→ X
1
X
2
…X
p
X
p + 1
…X
m
∈P и w ∈ϕ
n
(X
p
, B) ⊕
k
FIRST
G
k
(X
p + 1
…X
m
), где X
p
∈V
N
,
1
≤ p ≤ m. Иначе говоря, по определению операции ⊕
k
существуют w
1
∈ϕ
n
(X
p
, B),
В соответствии с индукционным
предположением из того, что w
1
∈ϕ
n
(X
p
, B), следует, что w
1
∈ϕ(X
p
, B). Это
значит, что
Кроме того,
12 1 2
11
FIRST ( ) FIRST ( ) FIRST ( )
FIRST ( ) FIRST ( ... ) FIRST ( ... )
GGG
k
kkk
GG G
pp
km m
kk k
www w w
X
XXX
++
∈=⊕⊆
⊆α⊕ =α
и при этом существует вывод
Следовательно, w ∈ϕ(A, B).
(S, A) {aa, ba} {aa, ba}
(A, S)
∅ ∅
(A, A)
∅ ∅
1
*
и ().
FIRST
G
p
k
G
XB
w
⇒
γ
α α
∈
12
1
2
().
( ... ) и FIRST
FIRST
G
G
pm
k
k
ww
XXw
w
+
=
∈
11
11
22
*
... ... ... ... .
pp p
mm
GG
A
XX X X X XX B X X
++
⇒⇒γα
22
() ()
(,) {} (, ) { , }.
FOLLOW FOLLOW
GG
S S S A S A aa ba
00
=ϕ ∪ ε = =ϕ =

Страницы