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

UptoLike

ВУЗ: 

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

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

Рубрика: 

214
б)
Замыкание
V
G
k
(ε): если [A → .Bα, u]∈
V
G
k
(ε), где B ∈ V
N
, и существует
B →β∈ P, то LR(k)-ситуация [B → .β, v], где v ∈
FIRST
G
k
(αu), тоже включается
в множество
V
G
k
(ε).
в) Шаг б) повторяется до тех пор, пока во множестве
V
G
k
(ε) не будут
просмотрены все имеющиеся в нём LR(k)-ситуации. Замыкание завершается за
конечное число шагов, так как множества P и V
T
*
k
конечны.
2. Строится следующий элемент последовательности. Пусть множества
V
G
k
(X
1
X
2
...X
i
), где 0≤ i < m, уже построены. Покажем, как построить
следующее множество
V
G
k
(X
1
X
2
...X
i +1
).
а)
Инициализация: если [A →β
1
.X
i +1
β
2
, u]∈
V
G
k
(X
1
X
2
...X
i
), то LR(k)-ситуация
[A →β
1
X
i +1
.β
2
, u] включается в множество
V
G
k
(X
1
X
2
...X
i +1
).
б)
Замыкание
V
G
k
(X
1
X
2
...X
i +1
): если {[A →β
1
.Bβ
2
, u] ∈
V
G
k
(X
1
X
2
...X
i +1
), где
B∈ V
N
, и существует B →β∈P, то [B → .β, v], где v ∈
FIRST
G
k
(β
2
u), тоже
включается во множество
V
G
k
(X
1
X
2
...X
i +1
).
в) Шаг б) повторяется до тех пор, пока во множестве
V
G
k
(X
1
X
2
...X
i +1
) не
будут просмотрены все имеющиеся в нём LR(k)-ситуации. Замыкание
завершается за конечное число шагов, так как множества P и V
T
*
k
конечны.
3. Шаг 2 повторять до тех пор, пока i < m.
4. Процесс завершается при i = m.
Утверждается, что
V
G
k
(γ)=
V
G
k
(X
1
X
2
... X
m
) (см. теорему 3.2 далее).
Замечание 3.2. Алгоритм 3.2 не требует использования пополненной грамматики.
Определение 3.9. Пусть G = (V
N
, V
T
, P, S) — контекстно-свободная грамма-
тика. На множестве LR(k)-ситуаций в этой грамматике определим функцию
, где — некоторое множество LR(k)-ситуаций, до-
пустимых для активного префикса γ ∈ (V
N
∪ V
T
)
*
; X ∈ V
N
∪ V
T
,
Очевидно, что эта функция строится попутно с построением множеств
()
G
k
V γ на шаге 2 алгоритма 3.2.
Если множество
V
G
k
(X
1
X
2
...X
i
) уже построено, то
V
G
k
(X
1
X
2
...X
i
X
i +1
) = GOTO(
V
G
k
(X
1
X
2
...X
i
), X
i +1
).
Остаётся ввести лишь обозначения: γ = X
1
X
2
...X
i
, X = X
i +1
, S =
V
G
k
(X
1
X
2
...X
i
),
′
S
=
V
G
k
(X
1
X
2
...X
i
X
i +1
), чтобы увидеть, как это делается.
Замечание 3.3. Важно отметить, что результат функции GOTO (S, X )=
,
′
S
где
S =
V
G
k
(X
1
X
2
...X
i
), зависит не от X
1
X
2
...X
i
, а от
V
G
k
(X
1
X
2
...X
i
).
Пример 3.9. Рассмотрим пополненную грамматику примера 3.1,
содержащую правила: 0)
S
′
→ S, 1) S → SaSb, 2) S →ε. Построим множества
V
G
1
(ε),
V
G
1
(S),
V
G
1
(Sa).
1: Построение множества
V
G
1
(ε).
а)
V
G
1
(ε) = {[
S
′
→ .S, ε]}.
GOTO( , )X
′
=
SS
().
G
k
VX
′
=γ
S
()
G
k
V=γS

Страницы