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

UptoLike

ВУЗ: 

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

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

Рубрика: 

227
3. Если в конфигурации, указанной в п.2, f
j
(u) = reduce i и A → Y
1
Y
2
...Y
p
—
правило с номером i, то цепочка X
j –p +1
...X
j –1
X
j
в магазине должна совпадать с
Y
1
Y
2
...Y
p
, так как множество ситуаций, по которому построена таблица T
j
,
содержит ситуацию [A→Y
1
Y
2
...Y
p
., u]. Таким образом, на шаге свёртки не
обязательно рассматривать символы верхней части магазина, надо просто
выбросить из магазина 2p символов грамматики и LR(k)-таблиц.
4. Если f
j
(u) = accept, то u = ε. Содержимое магазина в этот момент имеет
вид: T
0
ST
1
, где T
1
— LR(k)-таблица, соответствующая множеству LR(k)-ситуа-
ций, в которое входит ситуация [
S
′
→ S., ε].
§ 3.7. Корректность LR(k)-анализаторов
Теорема 3.5. Пусть G=(V
N
, V
T
, P, S) — LR(k)-грамматика и пусть A —
LR(k)-анализатор,
построенный по грамматике G согласно алгоритму 3.5.
Утверждается, что вывод существует тогда и только тогда, когда
0
(, ) Tw,ε где T = ( f, g)∈ T, причём f (ε) = accept.
Доказательство.
I. Индукцией по l = | π | покажем теперь, что если где α∈(V
N
∪ V
T
)
*
,
x∈V
T
*
, то (T
0
X
1
T
1
X
2
... X
m
T
m
, x, ε) (T
0
ST, ε, π
R
), где X
1
X
2
... X
m
= α, T
0
= T(A
0
),
A
0
=
V
G
k
(ε), а T
i
= T(A
i
), A
i
=
V
G
k
(X
1
X
2
... X
i
), i =1, 2,..., m.
База. Пусть l =1, т.е. π = i. Имеем Следовательно, существует
правило (i) S → αx∈ P.
Пусть x = a
1
a
2
... a
p
, a
j
∈ V
T
, j = 1, 2, … , p. Согласно определению активных
префиксов и допустимых для них LR(k)-ситуаций имеем
[S → α.a
1
a
2
... a
p
, ε]∈ A
m
=
V
G
k
(α) =
V
G
k
(X
1
X
2
... X
m
),
[S → αa
1
.a
2
... a
p
, ε]∈ A
m+1
=
V
G
k
(αa
1
),
…
[S → αa
1
a
2
... a
p–1
.a
p
, ε]∈ A
m+p–1
=
V
G
k
(αa
1
a
2
... a
p–1
),
[S → αa
1
a
2
... a
p
., ε] = [S → αx., ε]∈ A
m+p
=
V
G
k
(αa
1
a
2
... a
p
) =
V
G
k
(αx).
Тогда
согласно алгоритму построения LR(k)-таблиц T
m + j
= T(A
m+ j
)=(f
m + j
, g
m + j
),
f
m+j−1
(u
j
) = shift для u
j
∈
EFF
G
k
(a
j
a
j +1
...a
p
ε) = (a
j
a
j +1
...a
p
);
g
m+j–1
(a
j
)=T
m + j
(j =1, 2,…, p); а T
m + p
= (f
m+p
, g
m+p
) и f
m+p
(ε) = reduce i.Поэтому
(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
, a
1
a
2
...a
p
, ε)
(T
0
X
1
T
1
X
2
...X
m
T
m
a
1
T
m +1
a
2
T
m +2
...a
p
T
m + p
, ε, ε) (T
0
ST, ε, i ).
Здесь
сначала выполняется p раз сдвиг, затем один раз свертка по i -му
правилу; X
1
X
2
...X
m
a
1
a
2
...a
p
= αx, T = T(
V
G
k
(S)) = ( f, g), причём очевидно, что
[
S
′
→ S., ε]∈
V
G
k
(S) и потому согласно алгоритму 3.5 f (ε) = accept.
База доказана.
Индукционная гипотеза. Предположим, что утверждение I выполняется
для всех l ≤ n (n ≥ 1).
rm
Sw
π
⇒
rm
,Sx
π
⇒α
()
rm
.
i
Sx⇒α
*
−
−
A
*
−−
A
−
−
A
0
( , ),
R
TST ε,π
FISRT
G
k
*
_
_
A
*
_
_
A

Страницы