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

UptoLike

ВУЗ: 

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

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

Рубрика: 

228
Индукционный переход. Покажем, что утверждение I выполняется для
l = n +1.
Имеем
Очевидно, что x заканчивается цепочкой w,
т. е. x = zw. Здесь
′
α,
α∈ (V
N
∪ V
T
)
*
, w, x, z∈ V
T
*
,
,i
′
π
=π
A → β∈ P — (i)-е
правило.
Кроме того,
,wxzw
′
αβ =α =α
и потому
.z
′
α
β=α
Рассмотрим
исходную конфигурацию
(T
0
X
1
T
1
X
2
…X
j
T
j
X
j +1
T
j +1
…X
m
T
m
, zw, ε).
В ней
′
α
= X
1
X
2
... X
j
,
′
β
= X
j +1
...X
m
,
,z
′
β
=β
′
′
α
=αβ,
x = zw. Поэтому имею-
щийся вывод представим в виде
Поскольку
,
zP
′
→β=β ∈
то
′
′
α
β
— активный префикс провосентенциальной
формы α
’β’zw, причём и потому
[,],
m
Azu
′
→β. ∈A где
Пусть z = a
1
a
2
...a
p
. Согласно алгоритму построения LR(k)-таблиц имеем
T
m
= T(A
m
)=(f
m
,g
m
),
f
m
(v
1
)=shift для v
1
∈
EFF
G
k
(zu)=
FIRST
G
k
(a
1
a
2
...a
p
w)=
FIRST
G
k
(x),
g
m
(a
1
)=T
m +1
, где T
m +1
= T(A
m +1
),
A
m +1
=
1
G
k
Va
′
′
(
αβ );
T
m+1
=(f
m+1
,g
m+1
),
f
m +1
(v
2
)=shift для v
2
∈
FIRST
G
k
(a
2
...a
p
u)=
FIRST
G
k
(a
2
...a
p
w),
g
m +1
(a
2
)=T
m +2
, где T
m +2
= T(A
m +2
),
A
m +2
=
1
G
k
Vaa
2
′′
(
αβ );
...
T
m + p –1
= T(A
m + p –1
) = ( f
m + p –1
,g
m + p –1
), A
m + p –1
=
1
1
G
kp
Vaaa
2
−
′′
(
α β ... );
f
m + p –1
(v
p
) = shift для v
p
∈
EFF
G
k
(a
p
u)=
FIRST
G
k
(a
p
u)=
FIRST
G
k
(a
p
w),
g
m + p –1
(a
p
)=T
m + p
= T(A
m + p
),
где A
m + p
=
1
1
)).
GGG
p
kpkk
VaaaaVzV
2
−
′′ ′′ ′
(α β ... )= (α β = (α β
T
m + p
= ( f
m + p
, g
m + p
), f
m + p
(u) = reduce i, (i) A → β∈ P, u∈
FIRST
G
k
(w).
Используя существующие LR(k)-таблицы, канонический LR(k)-анализатор
совершает следующие движения, начиная с исходной конфигурации:
(T
0
X
1
T
1
X
2
...X
m
T
m
, x, ε) = (T
0
X
1
T
1
X
2
...X
m
T
m
, zw, ε) =
=(T
0
X
1
T
1
X
2
...X
m
T
m
, a
1
a
2
...a
p
w, ε)
(T
0
X
1
T
1
X
2
...X
m
T
m
a
1
T
m +1
, a
2
...a
p
w, ε)
...
...
(T
0
X
1
T
1
X
2
...X
m
T
m
a
1
T
m +1
a
2
...a
p
T
m + p
, w, ε) =
= (T
0
X
1
T
1
X
2
...X
j
T
j
X
j +1
T
j +1
...X
m
T
m
a
1
T
m +1
a
2
...a
p
T
m + p
, w, ε)
(T
0
X
1
T
1
X
2
...X
j
T
j
AT
’
j +1
, w, i)
00
( , , ) ( , , ).
R
R
TST i TST
′
ε
π= επ
Последний переход обоснован индукционной гипотезой с учётом того, что
1j
T
+
'
= T ( ), =
12
( ), ... .
G
j
k
VA XXX
′′
αα=
Вспомогательное утверждение I доказано.
()
rm rm
.
i
SAw wx
′
π
′′
⇒α ⇒αβ =α
()
rm rm
.
i
SAw w zw
′
π
′
′′′
⇒α ⇒αβ =αβ
,
GG
m
kk
VV
′′
(α β ) = (α) =
A
FIRST ( ).
G
k
uw∈
1j
A
+
'
1j
A
+
'
β
α
x
α
’
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
_
_
A
*
_
_
A

Страницы