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

UptoLike

ВУЗ: 

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

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

Рубрика: 

182
1
2
2
1
2
1
( ) ( ) ... ( )
FIRST ( ) FIRST ( ) ... FIRST ( )
FIRST ( ... ) FIRST ( ),
kkk
nn nm
GG G
kkk
m
kk k
GG
m
kk
xFY FY FY
YY Y
YY Y A
∈⊕ ⊕⊕ ⊆
⊆⊕ ⊕⊕ =
=⊆
поскольку A → Y
1
Y
2
…Y
m
∈P. Что и требовалось доказать.
II. Покажем теперь, что
FIRST
G
k
(A) ⊆ F
j
(A).
Пусть
FIRST ( ).
G
k
x
A∈
По определению этой функции существует вывод
, где |x | = k и y ∈V
T
*
либо |x | < k и y = ε. Индукцией по длине вывода l
покажем, что если FIRST ( )
G
k
x
A∈ благодаря существованию такого вывода, то
x ∈F
j
(A).
База. Пусть l =1. Имеем A ⇒ xy, где |x | = k и y ∈V
T
*
либо |x | < k и y = ε.
Тогда
существует правило A → xy ∈P и согласно шагу 2 алгоритма 2.5 x ∈F
0
(A) ⊆
F
j
(A). База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех l ≤ n (n ≥ 1).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно для l = n + 1.
Пусть
12
2
1
... ...
n
m
m
AYYY yyy⇒⇒— вывод длиной n +1, где y
i
∈V
T
*
, ,
i
ii
n
Yy⇒
n
i
≤ n, i =1,2,…,n и
1
2
( ... ) ( ).
FIRST FIRST
GG
m
kk
x
yy y A=∈
Ясно, что
1
2
2
1
1
2
1
2
FIRST ( ... ) FIRST ( ) FIRST ( ) ... FIRST ( )
FIRST ( ) FIRST ( ) ... FIRST ( )
( ) ( ) ... ( ).
GGGG
kkk
m
m
kkkk
GG G
kkk
m
kk k
kkk
nn n
m
xyyy y y y
YY Y
FY FY FY
∈=⊕⊕⊕⊆
⊆⊕ ⊕⊕ ⊆
⊆⊕ ⊕⊕
Последнее вложение множеств имеет место в соответствии со следствием
из индукционной гипотезы, применённой к выводам c учётом
того, что при n
i
=0 имеем Y
i
= y
i
.
Итак,
существует правило A → Y
1
Y
2
…Y
m
∈P и x ∈F
n
(Y
1
) ⊕
k
F
n
(Y
2
) ⊕
k
…⊕
k
F
n
(Y
m
). Согласно шагу 3 алгоритма: 2.5 заключаем, что x∈F
n +1
(A) ⊆ F
j
(A). Что
и требовалось доказать.
Из рассуждений I и II следует равенство F
j
(A)=
FIRST
G
k
(A), что
равнозначно утверждению теоремы.
§ 2.8. Вычисление функции σ(A)
Обратимся теперь к описанию алгоритма вычисления функции σ(A).
Алгоритм 2.6: вычисление σ(A) для A∈V
N
.
Вход: G
= (V
N
, V
T
, P, S) — контекстно-свободная грамматика.
Выход: σ(A) для всех A∈V
N
.
Метод.
, ,
i
n
i
ii
Yynn⇒≤
*
*
T
T
lm
*
() , ().
FIRST
{}
k
G
k
ALV SwAw L
V
⊆
σ= ∃⇒α,∈ = α
*
Axy⇒

Страницы