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

UptoLike

ВУЗ: 

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

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

Рубрика: 

210
Рассуждая от противного, предположим, что [A
1
→β
1
.β
2
, v] — другая LR(k)-
ситуация, допустимая для активного префикса αβ, причём EFF ( ).
G
k
uv
2
∈β
Согласно определению LR(k)-ситуации, допустимой для активного
префикса αβ, существует вывод вида
1
rm rm rm
**
2) ,SAx x yy
111211
′
⇒α ⇒αββ ⇒αβ =αβ
в котором применено правило A
1
→ β
1
β
2
,
и α
1
β
1
= αβ,
Кроме того, выполняется условие
3)
Условие 3) EFF ( )
G
k
uv
2
∈β означает согласно определению функции ,
что вывод вида в котором | u | = k и z∈ V
T
*
или | u | < k и z = ε, причём
если предпоследняя сентенциальная форма в этом выводе начинается с
нетерминала, то он заменяется непустой терминальной цепочкой.
Рассмотрим
три возможных варианта состава цепочки β
2
:
1) β
2
= ε, 2) β
2
∈ V
T
+
, 3) β
2
содержит нетерминалы.
Вариант 1
: β
2
= ε. В этом случае из условия 3) следует, что
EFF ( )
G
k
uv∈
и,
следовательно, u = v. Соответственно вывод 2) фактически имеет вид
111
rm
rm
*
2) .SAx xy
1
′′
⇒α ⇒αβ =αβ
Отсюда α
1
β
1
= αβ и x = y. Соответственно,
FIRST ( ) FIRST ( ) { } { }.
GG
kk
y xvu===
Так как
FIRST ( ) { },
G
k
wu=
то имеем два правосторонних вывода: 1) и
2,
′
в
которых
По предположению [A →β., u] ≠ [A
1
→β
1
.β
2
, v], причём u = v. Следова-
тельно, либо A ≠ A
1
, либо β≠β
1
(ведь β
2
= ε). Но так как G — LR(k)-грамматика,
то должно выполняться равенство
α
1
A
1
x = αAy, (3.4)
в котором x = y. При A ≠ A
1
это невозможно. Если же A = A
1
, то имеем α
1
≠α,
поскольку в этом случае
β≠β
1
при том, что α
1
β
1
= αβ. Итак, условие (3.4) не
соблюдаётся, и G — не LR(k)-грамматика вопреки первоначальному предполо-
жению. Полученное противоречие доказывает необходимость сформулирован-
ного в теореме условия в данном частном случае.
Вариант 2
: β
2
= z, z ∈ V
T
+
(β
2
— непустая терминальная цепочка).
В этом случае вывод 2) имеет вид
так что α
1
β
1
= αβ, y = zx и, кроме того, предполагается, что
т.е.
FIRST ( ).
G
k
uy∈
Итак, в выводах 1) и 2) имеет место
Чтобы грамматика G была LR(k)-грамматикой, должно быть α
1
A
1
x = αAy
или, что то же самое, α
1
A
1
x = αAzx, но это невозможно при z ≠ε. Получается,
что G — не LR(k)-грамматика, а это противоречит исходному предположению.
2
rm
*
,FIRST().
G
k
x
yv xβ⇒ ∈
*
,
rm
vuzβ⇒
EFF
G
k
FIRST ( ) EFF ( ).
GG
kk
uw v
2
∈⊆β
FIRST ( ) FIRST ( ).
GG
kk
wy=
1121
rm rm
*
2) ,SAx xzxy
11 1
′′ ′
⇒α ⇒αββ =αβ =αβ
3 ) EFF ( ) EFF ( ) EFF ( ) FIRST ( ),
GGG G
kkk k
uxzxy y
2
′′
∈β= = =
FIRST ( ) FIRST ( ).
GG
kk
wy=

Страницы