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

UptoLike

ВУЗ: 

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

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

Рубрика: 

211
Данное противоречие доказывает неправомерность предположения о
существовании двух разных LR(k)-ситуаций, о которых шла речь.
Вариант 3
: цепочка β
2
не пуста и содержит, по крайней мере, один
нетерминал. Пусть B — самый левый из них, т.е. β
2
= u
1
Bδ, где u
1
∈ V
T
*
, B∈ V
N
,
δ ∈ (V
N
∪ V
T
)
*
. Имеем:
1)
rm rm
*
SAw w
′
⇒α ⇒αβ
и
FIRST ( ) { }.
G
k
wu=
2)
1
rm rm
*
,SAx x x
1112 2
′
⇒α ⇒αββ =αββ
где α
1
β
1
= αβ,
FIRST ( ) { }.
G
k
x
v=
3) EFF ( ).
G
k
uv
2
∈β
В этом варианте из условия 3) следует, что существует правосторонний
вывод вида
Здесь на последнем шаге используется правило B
1
→ u
2
, где u
2
∈ V
T
*
с
гарантией, что u
1
y
1
u
2
≠ ε. Действительно, если u
1
y
1
= ε, то в соответствии с
определением
EFF
G
k
должно быть
u
2
≠ε.
Продолжим
вывод 2), учитывая, что
1 1 1 3 11123
rm rm rm rm rm
112 23
rm
***
2)
,
SAx xuBxuBuxuyByux
uyu yux y
1112
′′
⇒α ⇒αββ =αβ δ ⇒αβ ⇒αβ ⇒
⇒αβ =αβ
где y = u
1
y
1
u
2
y
2
u
3
x,
FIRST ( ).
G
k
vx∈
Вычислим
112 23 112 23
FIRST ( ) FIRST ( ) FIRST ( ) { }.
GG G
kk k
y u yu yu x u yu yuv u===
Итак,
т.е.
и
Остаётся проверить, выполняется ли LR(k)-условие
αβu
1
y
1
B
1
y
2
u
3
x = αAu
1
y
1
u
2
y
2
u
3
x.
Для выполнения этого равенства необходимо, по крайней мере, чтобы
y
2
u
3
x = u
1
y
1
u
2
y
2
u
3
x, т.е. u
1
y
1
u
2
= ε, чего, как мы выяснили, нет, т.к. u
1
y
1
u
2
≠ε.
Таким образом, LR(k)-условие нарушено, и G — не LR(k)-грамматика
вопреки исходному предположению.
Рассмотренные варианты состава цепочки β
2
исчерпывающе доказывают
необходимость сформулированного условия.
Достаточность. Рассуждая от противного, предположим, что условие
теоремы выполнено, но G — не LR(k)-грамматика. Согласно лемме 3.2
существуют два вывода вида
1)
2) такие, что x, y, w ∈V
T
*
и
а)
б) γBx ≠αAy,
в) |γδ| ≥ |αβ|.
Не ограничивая общности рассуждений, можно считать, что αβ — одна из
самых коротких цепочек, удовлетворяющих описанным условиям.
rm rm
*
,SBx x y
′
⇒γ ⇒γδ =αβ
rm rm
*
;SAw w
′
⇒α ⇒α
β
2 1 1 3 11 123 112 23 112 23
rm rm rm
**
, { } FIRST ( ).
G
k
v uB v uBuv uyByuv uyu yuv u u uyu yuvβ= δ⇒ ⇒ ⇒ ∈ =
21 13 11223
rm rm
**
:uB uBu uyu yuβ= δ⇒ ⇒
FIRST ( ) :
G
k
y
FIRST() {}, FIRST() {},
GG
kk
wu yu==
FIRST ( ) FIRST ( ),
GG
kk
wy=
FIRST ( ) FIRST ( ),
GG
kk
wy=

Страницы