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

UptoLike

ВУЗ: 

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

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

Рубрика: 

212
Представим вывод 2) иначе, выделив в нем явно начальный участок, на
котором получается последняя цепочка, причём её открытая часть не длиннее
|αβ|+1:
11
rm rm rm
**
2) .SAx y y
1112
′′
⇒α ⇒αββ ⇒αβ
Здесь |α
1
A
1
|≤|αβ|+1 или, что то же самое, |α
1
|≤|αβ|≤|γδ|, A
1
→β
1
β
2
∈ P.
Цепочка β
1
β
2
— основа сентенциальной формы α
1
β
1
β
2
y
1
, причём β
1
— её
префикс такой длины, что выполняется равенство |α
1
β
1
| = |αβ|.
Отметим, что активный префикс длины |αβ|, для которого допустима хотя
бы какая-нибудь LR(k)-ситуация, не может получиться из сентенциальной
формы, открытая часть которой длиннее |αβ|+ 1. Действительно, если,
например, |α
1
A
1
| > |αβ| + 1, т.е. |α
1
| > |αβ|, то крайний левый символ основы
β
1
β
2
находился бы в позиции, по меньшей мере, |αβ| + 2, и эта основа не имела
бы никакого
касательства к префиксу длиной |αβ|.
Очевидно, что в выводе и α
1
β
1
= αβ.Таким образом, вывод
2)
′
можно переписать в следующем виде:
11 1 1
rm rm rm
**
2) .SAy y y y
1112 2
′′ ′
⇒α ⇒αββ =αββ ⇒αβ
Из факта
существования вывода 1) следует, что LR(k)-ситуация [A →β., u],
где
FIRST ( ),
G
k
uw∈
допустима для активного префикса αβ правосентенциаль-
ной формы αβw.
Аналогично из факта существования вывода
2)
′
′
следует, что LR(k)-ситуа-
ция [A
1
→β
1
.β
2
, v], где
1
FIRST ( ),
G
k
vy∈
допустима для активного префикса αβ
правосентенциальной формы αββ
2
y
1
.
Учитывая условие a), вывод и заключаем,
что
21 2 1
22 2
FIRST() FIRST() FIRST( ) FIRST( ) FIRST( )
FIRST ( ) { } FIRST ( ) FIRST ( ) FIRST ( ).
GGG G G
k
kkk k k
GGGG
kk
kkkk
uw y y y
vvv
∈=⊆β=β⊕ =
=β⊕=β⊕ =β
Остаётся
показать, что u∈
EFF
G
k
(β
2
v).
Действительно, если бы u ∉
EFF
G
k
(β
2
v), то только потому, что цепочка β
2
начилась бы с нетерминала, который на последнем шаге вывода за-
мещался бы ε-цепочкой.
Сопоставим
исходное представление вывода 2) с его же представлением в
виде
2)
′′
:
и
11 1 1
rm rm rm
**
2) .SAy y y y
1112 2
′′ ′
⇒α ⇒αββ =αββ ⇒αβ
Последним замещаемым нетерминалом в этом выводе является B, причём
эта-то последняя замена и даёт цепочку αβy. На завершающем участке этого
вывода используется так что, если β
2
= A
2
α
2
и последнее используемое
правило есть B → ε, то вывод
2)
′
′
можно переписать следующим образом:
1
2
rm
*
2) yy
′
⇒
β
1
2
rm
*
2)
yy⇒
′
β
1
2
rm
*
yy⇒
β
rm rm
*
2) SBx x y
′
⇒γ ⇒γδ =αβ
1
2
rm
*
,yy⇒
β
1
FIRST ( ),
G
k
vy∈

Страницы