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

UptoLike

ВУЗ: 

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

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

Рубрика: 

217
Случай 2: β
1
= ε.
Имеем
S αAw αβ
1
β
2
w = αβ
2
w, причём на последнем шаге вывода при-
менено правило A →β
2
∈ P, а γ = α =
X
′
γ
и |γ|= n +1, т.е.
′
γ
∈ (V
N
∪ V
T
)
*
,
| | = n, X ∈ V
N
∪ V
T
. Здесь Надо показать, что LR(k)-ситуация
[A→.β
2
, u]∈
V
G
k
(γ).
Рассмотрим подробнее этот вывод, чтобы показать, как впервые появляется
символ X, завершающий цепочку α, и как образуется правосентенциальная
форма αAw. В общем случае он имеет следующий вид:
21
rm
X
Aw
12 2
′
⇒αα δ
12
( , = ),AXAP
22 12
′
′′
∃
→α δ ∈ αα γ
221
rm
*
XA w w
′
⇒γ
2
2
rm
*
( ),w∃δ ⇒
…
11 21
rm
...
mm m
X
Aww
−− −
′
⇒γ δ
(∃ A
m –2
→ A
m –1
δ
m –1
∈ P),
11 21
rm
*
...
mmm
XA w w w
−−−
′
⇒γ
11
rm
*
( ),
mm
w
−−
∃δ ⇒
121
rm
...
mm m m
X
Aww w
−−
′
⇒γ δ
(∃ A
m –1
→
A
m
δ
m
∈ P),
12
1
rm
*
...
mmm m
XA w w w w
−−
′
⇒γ
(∃δ
m
rm
*
⇒
w
m
),
X
Aw
′
=γ
(A
m
= A, w
m
w
m –1
…w
1
= w),
2
rm
.
X
ww
2
′
⇒γ β =γβ
2
( , = ).
PX
′
∃
→β ∈ γ γ
Отметим, что в сентенциальной форме
21
XA w
12 2
′
α
αδ
за префиксом
X
12
′
γ=αα
может следовать только нетерминал, ибо иначе основа β
2
не могла
бы появиться в рассматриваемом выводе непосредственно за этим префиксом,
и LR(k)-ситуация [A → .β
2
, u] не была бы допустима для префикса γ.
По определению
12221
[., ],
A
XA v
′
→α δ
где
11
FIRST ( ),
G
k
vw∈
есть LR(k)-си-
туация, допустимая для
′
γ.
Поскольку |
′
γ
| = n, то в соответствии с индукционной гипотезой можно
утверждать, что
12221
[., ]),
G
k
AXAvV
′′
→α δ ∈ (γ
а тогда согласно шагу 2a алго-
ритма LR(k)-ситуация
12221
[., ])).
GG
kk
AXAvVXV
′′
→α δ ∈ (γ = (γ
Поскольку существуют правило A
2
→ A
3
δ
3
и вывод δ
2
w
2
, то согласно шагу
2б [A
2
→ .A
3
δ
3
, v
2
]∈ где
Рассуждая далее аналогичным образом, приходим к выводу, что
[A
m –1
→ .A
m
δ
m
, v
m –1
]∈
)
G
k
V (γ
, где v
m –1
∈
FIRST
G
k
(w
m –1
v
m –2
)=
FIRST
G
k
(w
m –1
…w
1
).
Наконец, согласно шагу 2б, поскольку A
m
= A и существуют правило A →β
2
и вывод δ
m
rm
*
⇒
w
m
, заключаем, что LR(k)-ситуация [A → .β
2
, v
m
]∈
G
k
V
(γ), где
Итак, [A → .β
2
, u]∈
G
k
V
(γ). Что и требовалось доказать.
rm
*
⇒
rm
⇒
′
γ
FIRST ( ) { }.
G
k
wu=
11
rm
*
SAw
1
⇒α
G
k
V (γ),
221 21
FIRST ( ) FIRST ( ).
GG
kk
vwv ww∈=
rm
*
⇒
11
1
FIRST ( ) = FIRST ( ... ) = FIRST ( ) { }.
GG G
mmm mm
kk k
vwv www wu
−−
∈=

Страницы