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

UptoLike

ВУЗ: 

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

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

Рубрика: 

181
2
1
(){, } ();
*
FT FT
′′
=ε=
2
1
() {(, } ().FF a FF==
Так как F
2
(E ) ≠ F
1
(E ) придётся ещё раз проделать шаг 3, что даёт, наконец,
3
2
() {(, } ();FE a FE==
3
2
(){, } ();FE FE
′′
=+ε=
3
2
() {(, } ();FT a FT==
3
2
(){, } ();
*
FT FT
′′
=ε=
3
2
() {(, } ().FF a FF==
Таким образом, окончательно получаем:
111
() () () {(,};
FIRST FIRST FIRST
GGG
ET Fa===
1
(){, };
FIRST
G
E
′
=
+ε
1
(){, }.
FIRST
*
G
T
′
=
ε
Теорема 2.7. Пусть G = (V
N
,V
T
,P,S) — контекстно-свободная грамматика.
Алгоритм 2.5 правильно вычисляет функцию ()
FIRST
G
k
β
для любой цепочки
β∈V
*
и k ≥ 0.
Доказательство.
Фактически достаточно показать, что F
j
(A) =
FIRST
G
k
(A),
если F
i
(A) = F
j
(A) при i > j для всех A ∈V
N
. Не нарушая общности рассуждений,
будем предполагать, что G — приведённая грамматика.
I. Покажем сначала, что F
j
(A) ⊆
FIRST
G
k
(A).
Пусть x ∈F
l
(A) при l ≤ j. Индукцией по l покажем, что тогда x ∈
FIRST
G
k
(A).
База. Пусть l =0 и x ∈F
0
(A). Тогда согласно шагу 2 алгоритма 2.5
существует правило вида A → xα∈P, где x ∈V
T
*
k
и |x | = k, либо |x | < k и α = ε.
Следовательно, , где |x | = k и y ∈V
T
*
, либо |x | < k и y = ε. Согласно
определению функции
FIRST
G
k
заключаем, что ().
FIRST
G
k
x
A∈ База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех l ≤ n (0 ≤ n ≤ j).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно для l = n +1.
Пусть x ∈F
n +1
(A). Согласно алгоритму 2.5
либо x∈F
n
(A) и тогда в соответствии с индукционным предположением
x ∈
FIRST
G
k
(A),
либо существует правило вида
A →Y
1
Y
2
…Y
m
∈P и x ∈F
n
(Y
1
) ⊕
k
F
n
(Y
2
) ⊕
k
…⊕
k
F
n
(Y
m
).
Если Y
i
∈V
N
, то в соответствии с индукционной гипотезой
() FIRST().
G
ni
i
k
FY Y⊆ Если же Y
i
∈V
T
, то согласно определению множеств F
n
и
функции
FIRST
G
k
заключаем, что
() {} FIRST().
G
ni
ii
k
FY Y Y==
Итак, в любом случае справедливо
() FIRST()
G
ni
i
k
FY Y⊆
для Y
i
∈V
N
∪ V
T
.
Тогда
*
Axy⇒

Страницы