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

UptoLike

ВУЗ: 

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

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

Рубрика: 

186
11 11
112
2
lm lm lm
11
12
lm
***
*
... ... ... ...
... ... .
ppp ppp
mm
pp p
m
A XX X XX X ww w XX X
ww w w B X X
−+ −+
−+
⇒⇒⇒
⇒γ
Согласно определению
1
(),
FIRST
...
G
kp
m
AB
XX
+
γ
′
∈
σ( ). Кроме того,
11
1
()( ()
FIRST FIRST FIRST
... ...
( ) .
FIRST
...
GGG
k
kkk
pp
mm
G
k
kp
m
XX XX
LXL
X
++
+
γγ
=)⊕ =
′
=⊕ =
Итак,
(,).LAB
′
∈σ
Что и требовалось.
II. Покажем теперь, что σ
’(A, B)⊆σ’
j
(A, B).
Пусть
,LAB
′
∈σ( ). Это значит, что существует левосторонний вывод
Индукцией по длине вывода l покажем, что
База. Пусть l =1, т.е. Тогда
существует
правило A → wBα и согласно шагу 1 алгоритма 2.6
База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно для l = n +1. Пусть
1
11 11
112
2
lm lm lm
11
12
lm
... ... ... ...
... ...
n
ppp ppp
mm
pp p
m
AXXXXX X wwwXX X
ww w w B X X
wB
−
−+ −+
−+
⇒⇒⇒
⇒γ
=α
— вывод длиной n + 1, где
1
12
... , , ... ,
pp
pp
m
wwwwX wB P X X
+
=
→γ∈α=γ и
где
FIRST ( ).
G
k
L
′
=γ
Именно благодаря этому обстоятельству
(,).LAB
′
∈σ
Одновременно согласно шагу 2 алгоритма
2.6 из существования вывода
следует
по определению, что FIRST ( )
G
p
k
LXB
′′
=
γ∈σ( , ), а по
индукционному предположению, что и, следовательно,
(,).
jp
LXB
′′
∈σ
Кроме того, имеется правило A → X
1
X
2
…X
p
X
p +1
…X
m
∈P.
Согласно
шагу 2 алгоритма 2.6 где
(,)
j
p
LXB
′′
∈σ
есть элемент
1
(,).
j
A
B
+
′
σ
Но
Итак,
Из рассуждений I и II следует равенство и утверждение
теоремы.
§ 2.9. Алгоритм вычисления
функции
()
FOLLOW
G
k
A
11
() FIRST
FIRST
() (),
FIRST
... ...
G
G
G
k
k
kpp
mm
k
LL
X
XXX
++
γ
′
α=
==⊕
lm
*
,
p
pp
X
wB l n⇒γ,≤
1
(),
FIRST
...
G
k
kp
m
LL
X
X
+
′
=⊕
pp
j
BXB
′
′
σ
(,)⊆σ(,)
1
(,) (,).
jj
AB AB
+
′
′
σ=σ
(,).
j
LAB
′
=σ
*
T
lm
и FIRST ( )
G
k
AwBwV L⇒α,∈ = α.
0
FIRST ( ) ( , ) ( , ).
G
j
k
LABAB
′′
=α∈σ⊆σ
(,).
j
LAB
′
∈
σ
lm
*
pp
X
wB⇒γ, FIRST ( ).
G
k
L
′
=
γ
(,) (,)
j
AB AB
′
′
σ
=σ
T
*
и FIRST ( )
l
G
k
lm
AwBwV L⇒α,∈ = α.

Страницы