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

UptoLike

ВУЗ: 

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

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

Рубрика: 

222
Теорема 3.3. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грамматика.
Множество LR(k)-ситуаций
A ∈ S тогда и только тогда, когда существует
активный префикс γ ∈ (V
N
∪ V
T
)
*
, такой, что
V
G
k
(γ)=A.
Доказательство.
I. Докажем сначала, что если
A ∈ S, то существует активный префикс
γ∈ (V
N
∪ V
T
)
*
, такой, что
V
G
k
(γ)=A.
Согласно алгоритму 3.3 элементы множества
S образуются в определенной
последовательности. Именно, полагается, что и сначала строится
множество
0
00
(){},
G
k
V
=
=εSAA
а элементы из множества S
i +1
строятся по
элементам множества
S
i
следующим образом:
если
() ,
G
i
k
V
′′
=γ∈
AS
то
1
GOTO( , ) ( ) ,
G
i
k
XV X
+
′′
==γ∈
AA S
где X ∈ V
N
∪ V
T
.
Доказательство проведём индукцией по номеру i множества
S
i
, которому
принадлежит элемент
A.
База. Пусть i =0. Имеем
A ∈ S
0
. Согласно алгоритму 3.3 A
0
=
V
G
k
(ε), и по
теореме 3.2 о корректности алгоритма построения функции
V
G
k
(γ) цепочка γ = ε
— как раз такой активный префикс грамматики G, что
V
G
k
(ε) = A
0
= A ∈ S
0
⊆ S.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех i ≤ n (n < m).
Индукционный
переход. Покажем, что аналогичное утверждение
выполняется для i = n +1.
Пусть A ∈ S
n +1
. В соответствии с алгоритмом 3.3 существуют
n
′
∈
ASи X∈ V
N
∪
V
T
,
такие, что
GOTO( , ) ( ) ( ).
GG
kk
XV XV
′′
=
=γ=γAA
Согласно теореме 3.2 цепочка γ является активным префиксом грамматики
G, таким, что
A =
V
G
k
(γ). Утверждение I доказано.
II. Докажем теперь, что если γ ∈ (V
N
∪ V
T
)
*
— активный префикс
грамматики G и A =
V
G
k
(γ), то A ∈ S.
Индукция по l = |γ|.
База. Пусть l =0, γ = ε. Имеем
Согласно алгоритму 3.3 A
0
включается в множество S на первом же шаге.
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех γ: l = |γ|≤n (n ≥ 0).
Индукционный переход. Покажем, что такое утверждение выпол-
няется для l = n +1. Пусть γ =
X
′
γ
, где |
′
γ
| = n, X∈ V
N
∪ V
T
и
γ — активный
префикс грамматики G. Это значит, что существует правосторонний вывод
вида
S αAw
αβ
1
β
2
w = γβ
2
w =
,Xw
2
′
γβ
где αβ
1
= γ =
.
X
γ
Следовательно,
′
γ
— тоже активный префикс грамматики G и |
′
γ
| = n.
0
,
m
i
i =
=
∪
SS
rm
*
⇒
rm
⇒
0
() .
G
k
V
′
=ε=AA

Страницы