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

UptoLike

ВУЗ: 

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

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

Рубрика: 

230
Остаётся лишь убедиться в том, что X
1
X
2
...X
m
X
m +1
x
w. Так как
x
′
= X
m +1
x,
то X
1
X
2
... X
m
X
m +1
x = X
1
X
2
...X
m
по индукционной гипотезе.
Случай 2
: reduce i -движение.
Имеем
конфигурацию, достигнутую за первые n движений:
(T
0
X
1
T
1
X
2
...X
m
T
m
,, ).
R
x
′′
π Далее совершается последнее движение: свертка
верхней части магазина по i-у правилу. Оно происходит благодаря тому, что
T
m
=(f
m
, g
m
), f
m
()u
′
= reduce i для
FIRST ( ).
G
k
ux
′
′
∈
Согласно
алгоритму построения анализатора T
m
= T(A
m
), A
m
=
V
G
k
(X
1
X
2
...X
m
),
и существуют LR(k)-ситуация [A→Y
1
Y
2
...Y
p
.
,]u
′
∈A
m
и правило A → Y
1
Y
2
...Y
p
под
номером i, такое, что
Y
1
Y
2
...Y
p
= X
m – p +1
...X
m –1
X
m
. Имеем:
(T
0
X
1
T
1
X
2
...X
m
T
m
,, )
R
x
′′
π =
=(T
0
X
1
T
1
X
2
...X
m – p
T
m– p
Y
1
T
m – p +1
Y
2
T
m – p +2
...Y
p
T
m
,)
R
x
′
′
π
(T
0
X
1
T
1
X
2
...X
m – p
T
m – p
A
–
+1mp
T
'
,, ),
R
x
i
′
′
π
где
–
+1mp
T
'
= g
m – p
(A), если T
m – p
=(f
m – p
, g
m – p
).
Остаётся убедиться лишь в том, что X
1
X
2
... X
m – p
A Действительно,
X
1
X
2
...X
m – p
A X
1
X
2
...X
m – p
Y
1
Y
2
...Y
p
x
′
=
= X
1
X
2
A ’ ... X
m–p
X
m–p+1
... X
m–1
X
m
причём первый шаг вывода выполняется при помощи упомянутого правила, а
завершение вывода обеспечено индукционной гипотезой. Вспомогательное
утверждение II доказано.
В частности, при α = S и x = ε заключаем, что если (T
0
, w, ε)
(T
0
ST, ε, π
R
),
где последняя конфигурация — принимающая, то
Из рассуждений I и II следует утверждение теоремы.
Теорема 3.6. Если G =(V
N
, V
T
, P, S) — LR(k)-грамматика, то грамматика
G — синтаксически однозначна.
Доказательство ведется от противного. Пусть G — LR(k)-грамматика, но
она не является синтаксически однозначной. Это значит, что существуют два
разных правосторонних вывода одной и той же терминальной цепочки:
1) S = α
0
rm
⇒
α
1
rm
⇒
…
rm
⇒
α
m
= w,
2) S = β
0
rm
⇒
β
1
rm
⇒
…
rm
⇒
β
n
= w, w∈ V
T
*
,
и существует i >0 (i < m, i < n), такое, что α
m – i
≠β
n – i
, но α
m – j
= β
n – j
при j < i.
В более детальном представлении эти выводы имеют вид
где δ = β
1
β
2
, γβ
1
= αβ, β
2
y = x, β
2
∈ V
T
*
, причём так как α
m – i
≠ β
n – i
, то α ≠ γ ∨ A ≠ B ∨ x ≠ y.
Из вывода 1
’
) очевидно, что [A → β., u]∈ , где
FIRST ( ).
G
k
ux∈
rm
π
⇒
rm
x
w
′
π
′
⇒
rm
.
i
x
w
′
π
′
⇒
()
rm
i
x
′
⇒
rm
,
x
w
′
π
′
⇒
rm
.Sw
π
⇒
δ
x
αβ
β
n – i
1
rm
rm rm
**
2) ,SBy y y xw
2
′
⇒γ ⇒γδ =γββ =αβ ⇒
rm rm rm
**
1) ,SAx xw
′
⇒α ⇒αβ ⇒
α
m−i
()
G
k
V
α
β
_
_
A
_
_
A
*
_
_
A

Страницы