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

UptoLike

ВУЗ: 

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

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

Рубрика: 

215
б) Множество
V
G
1
(ε) пополняется ситуациями [S → .SaSb, ε], [S → ., ε];
множество
V
G
1
(ε) пополняется ситуациями [S → .SaSb, a], [S → ., a].
Другие шаги алгоритма 3.2 никаких других элементов в множество
V
G
1
(ε)
не добавляют. Окончательно получаем
V
G
1
(ε) = {[
S
′
→ .S, ε], [S → .SaSb, ε], [S → ., ε], [S → .SaSb, a], [S → ., a]}.
В
сокращенных обозначениях то же самое принято записывать следующим
образом:
V
G
1
(ε) = {[
S
′
→ .S, ε], [S → .SaSb, ε | a], [S → ., ε | a]}.
2: Построение множества
V
G
1
(S ).
а)
V
G
1
(S) = {[
S
′
→ S., ε], [S → S.aSb, ε | a]}.
Так
как точка ни в одной из этих ситуаций не стоит перед нетерминалом, то
шаг б) не выполняется ни разу. Попутно мы вычислили GOTO(
V
G
1
(ε), S)=
V
G
1
(S).
3: Построение множества
V
G
1
(Sa).
а)
V
G
1
(Sa) = {[S → Sa.Sb, ε | a]}.
б) Множество
V
G
1
(Sa) пополняется ситуациями [S → .SaSb, b] и [S → ., b];
множество
V
G
1
(Sa) пополняется ситуациями [S → .SaSb, a] и [S → ., a].
Здесь шаг б) замыкания выполнялся дважды.
Итак,
V
G
1
(Sa)={[S → Sa.Sb, ε | a], [S → .SaSb, a | b], [S → ., a | b]} и
GOTO(
V
G
1
(S), a)=
V
G
1
(Sa).
Теорема 3.2. Алгоритм 3.2 правильно вычисляет множество
V
G
k
(γ), где
γ∈(V
N
∪ V
T
)
*
— активный префикс правосентенциальной формы в грамматике G.
Доказательство. Фактически требуется доказать, что LR(k)-ситуация
[A → β
1
.β
2
, u] ∈
V
G
k
(γ) тогда и только тогда, когда существует правосторонний
вывод вида
в котором αβ
1
= γ (γ — активный префикс
правосентенциальной формы αβ
1
β
2
w), а FIRST ( ) { }
G
k
wu= , причём цепочка u
есть правый контекст основы β
1
β
2
в данной сентенциальной форме αβ
1
β
2
w.
I. Докажем
сначала, что если γ = αβ
1
— активный префикс сентенциальной
формы αβ
1
β
2
w в выводе то LR(k)-ситуация [A →β
1
.β
2
, u],
где
FIRST ( ),
G
k
uw∈
содержится в множестве
V
G
k
(γ).
Индукция по l = |γ|.
База. Пусть l =0, т.е. γ = ε.
Имеем вывод γ = αβ
1
= ε. Фактически α = β
1
= ε, и вывод
имеет вид где на последнем шаге применялось правило A →β
2
.
Во всех деталях он мог бы быть только таким:
S
rm
⇒
A
1
α
1
rm
*
⇒
A
1
w
1
rm
⇒
A
2
α
2
w
1
rm
*
⇒
A
2
w
2
w
1
rm
⇒
...
rm
⇒
A
m
α
m
w
m –1
...w
1
rm
*
⇒
A
m
w
m
w
m –1
...w
1
= Aw β
2
w.
rm
rm
*
,SAw w
12
⇒α ⇒αββ
rm
rm
*
,SAw w
12
⇒α ⇒αββ
rm rm
*
,SAw w
12
⇒α ⇒αββ
rm
rm
*
,SAw w
2
⇒⇒β
rm
*
⇒
rm
⇒

Страницы