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

UptoLike

ВУЗ: 

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

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

Рубрика: 

187
Сопоставляя определения функций
**
TT
lm
*
T
*
*
() { , , FIRST()} è
FOLLOW ( ) { FIRST ( )},
kG
k
GG
kk
G
ALV AwAwVL
AwV SAw
σ=⊆ ∃⇒α∈ = α
=∈ ∃⇒γα,∈ α
где A∈V
N
,
нетрудно сообразить, что
()
()
FOLLOW .
G
k
LA
A
L
∈σ
=
∪
Это равенство — ключ к модификации алгоритма вычисления σ(A), дающей
алгоритм вычисления
Алгоритм 2.7: вычисление
()
FOLLOW
G
k
A
.
Вход: G
= (V
N
,V
T
,P,S) — контекстно-свободная грамматика.
Выход:
()
FOLLOW
G
k
A
для всех A ∈V
N
.
Метод.
Определим вспомогательную функцию
*
T
*
(){ FIRST()},
,
k
G
k
G
A
Aw Bw
B
V
ϕ
=∈ ∃⇒
γ
α, ∈ α
где A,B ∈V
N
.
Очевидно, что FOLLOW ( ) ,
G
k
ASA
=
ϕ( ). Остаётся определить алгоритм для
вычисления функции ϕ(A, B).
Вычисление значения ϕ(A, B) производится по следующим шагам:
1. ϕ
0
(A, B)={w ∈V
T
*
k
|∃ A →γBα∈P, α,γ∈V
*
, w =
FIRST
G
k
(α)}.
2. Пусть значения ϕ
0
(A,B), ϕ
1
(A,B),…, ϕ
i
(A,B) уже построены для всех
(A, B)∈V
N
× V
N
. Тогда
*
1
T12 N
1
1
( , ) ( , ) { ... ... , ,
( , ) FIRST ( ... )}.
k
pp p
m
ii
G
pp
km
ik
AB AB w V A XX X X X PX V
wXB XX
+
+
+
ϕ=ϕ∪∈∃→ ∈∈
∈ϕ ⊕
3. Шаг 2 повторяется до тех пор, пока при некотором i = j не окажется
ϕ
j +1
(A, B)=ϕ
j
(A, B) для всех (A, B) ∈V
N
× V
N
. Такое j существует, ибо ϕ
0
(A, B) ⊆
⊆ ϕ
1
(A, B) ⊆…⊆ Σ
*
k
при том, что последнее множество является конечным.
И тогда ϕ(A,B)=ϕ
j
(A, B).
4. Полагаем для всех A∈V
N
\ {S} и
()
FOLLOW
G
k
S =
ϕ(S, S )∪{ε},
так как всегда , но может оказаться, что ε∉ϕ(S, S).
Пример 2.12. Пусть G = ({S, A}, {a, b}, P, S ), где
P = {S → aAaa, S → bAba, A → b, A → ε}.
Построим
множества
2
()
FOLLOW
G
S и
2
()
FOLLOW
G
A
, используя описанный
алгоритм (табл. 2.6).
Таблица. 2.6
N × N ϕ
0
ϕ
1
(S, S)
∅ ∅
FOLLOW ( ) .
G
k
A
()
,
FOLLOW
G
k
A
SA
=ϕ
(
)
()
FOLLOW
G
k
Sε
∈

Страницы