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

UptoLike

ВУЗ: 

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

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

Рубрика: 

207
Рассмотрим правосторонний вывод В сентенциальной форме C осно-
вой является C. Эта форма имеет два активных префикса: ε и C. Для активного
префикса ε допустима LR(0)-ситуация [S → .C, ε], а для активного префикса C
— LR(0)-ситуация [S → C., ε].
Рассмотрим выводы, дающие активный префикс aaaa, и LR(0)-ситуации,
допустимые для него:
1) S
rm
*
⇒
aaaC
rm
⇒
aaa a C , αβ
1
= aaaa, [C → a.C, ε];
2) S
rm
*
⇒
aaaaC
rm
⇒
aaaa b , αβ
1
= aaaa, [C → .b, ε];
3) S
rm
*
⇒
aaaD
rm
⇒
aaa a D , αβ
1
= aaaa, [D → a.D, ε];
4) S
rm
*
⇒
aaaaD
rm
⇒
aaaa c , αβ
1
= aaaa, [D → .c, ε].
Во всех случаях правый контекст основы пуст.
Лемма 3.2. Пусть G = (V
N
, V
T
, P, S) — не LR(k)-грамматика. Тогда
существуют два правосторонних вывода в пополненной грамматике:
1)
2) такие, что x, y, w ∈ V
T
*
и
а)
б) γBx ≠ αAy,
в) |γδ| ≥ |αβ|.
Доказательство. Если G — не LR(k)-грамматика, то условия а) и б)
выполняются как прямое следствие из определения LR(k)-грамматик. Условие
в) неформально означает, что правая граница основы в последней сентен-
циальной форме второго вывода удалена от её начала, по крайней мере, не
менее, чем удалена основа в последней сентенциальной форме в первом
выводе. Это условие не столь очевидно. Простой обмен ролями этих двух
выводов ничего не даёт, так как этим приёмом мы добъёмся только
выполнения условий а) и в), но не очевидно, что при этом будет выполнено
условие б).
Предположим, что выводы 1) и 2) удовлетворяют условиям а) и б), но
условие в) не выполнено, т.е. что |γδ| < |αβ|. Покажем, что тогда найдется
другая пара выводов, которые удовлетворяют всем трём условиям.
Поскольку γδx = αβy, то |γδx| = |αβy|, и, учитывая, что |γδ| < |αβ|,
заключаем, что |x | > |y |, т.е. x = zy при некотором z ∈ V
T
+
, |z | > 0.
α
β
β
1
β
2
α
β
β
1
β
2
α
β
α
β
β
1
β
2
β
1
β
2
rm
.SC⇒
rm rm
*
;SAw w
′
⇒α ⇒αβ
rm rm
*
,SBx x y
′
⇒γ ⇒γδ =αβ
FIRST ( ) FIRST ( ),
GG
kk
wy=

Страницы