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

UptoLike

ВУЗ: 

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

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

Рубрика: 

183
По определению
Введём в рассмотрение ещё одну вспомогательную функцию, определя-
емую для пары нетерминалов следующим образом:
*
*
T
T
lm
*
( , ) , , ( ) .
FIRST
{}
k
G
k
AB L V A wB w L
V
⊆
′
σ= ∃⇒α∈= α
Очевидно, что () (,)ASA
′
σ=σ .Таким образом, достаточно дать алгоритм
вычисления
функции (,)
A
B
′
σ для любых A, B∈V
N
. Мы будем вычислять (,)
A
B
′
σ
методом последовательных приближений, параллельно выстраивая последова-
тельности множеств
(,)
i
A
B
′
σ для всех возможных пар (A, B)∈V
N
× V
N
следую-
щим образом:
1.
*
*
0
TN
(,) ; , ().
FIRST
{}
k
G
k
AB L V A B P L
V
⊆
′
=
∃→βα∈ β,α∈ = α
σ
Пусть
0
1
( , ), ( , ), ..., ( , )
i
A
BAB AB
′′ ′
σσ σ
вычислены для всех пар нетерминалов.
2. Положим
*
T
1
2
1
,
N
1 2
( , ) ( , ) ... ;
( , ),
FIRST ( ... )}.
{
1 ;
k
i
i
m
p
p
i
G
k
kp p m
AB AB L V A XX X P
LXBXV
LL XX X
pm
+
++
⊆
′′
σ=σ∪ ∃→ ∈
′′
∈σ ∈
′
⊕
≤≤ =
3. Повторять шаг 2 до тех пор, пока при некотором i = j не окажется, что
1
(,) (,)
jj
A
BAB
+
′′
σ=σ
для всех (A,B) ∈V
N
× V
N
. Такое j существует, потому что
T
*
0
1
( , ) ( , ) ... .
2
k
V
AB AB
′
′
σ⊆ ⊆⊆
σ
4. Полагаем ,(,).
j
AB AB
′
′
σ( )=
σ
5. Наконец, ( , ).ASA
′
σ( ) = σ Если окажется, в частности, что (,),SS
′
{ε}∉σ
то ( , ) {{ }}.SSS
′
σ( ) = σ ∪ ε
Пример 2.11. Пусть G = ({S, A}, {a, b}, P, S ), где
P = {S → AS, S → ε, A → aA, A → b}.
Таблица 2.5
Вычислим функции σ(S) и σ(A) при k =1. Сначала получаем
1
()
FIRST
G
S
=
{ε, a, b}
и
1
FIRST
G
(A)={a,b}. Затем построим последовательности σ’
i
(X,Y ), где
(X, Y )∈V
N
× V
N
(табл. 2.5). За два шага получаем σ(S)={{ε}}, σ(A)={{ε, a, b}}.
Поясним построение этих последовательностей.
Шаг 1. Построение σ
0
’(S, S): имеем правило для S → AS, в котором
нетерминал S встречается слева и справа. Вычисляется
1
() {},
FIRST
G
ε=ε
σ
i
’
i = 0 i = 1
(S, S)
{{
ε}} {{ε}}
(S, A)
{{
ε, a, b}} {{ε, a, b}}
(A, S)
∅ ∅
(A, A)
{{
ε}} {{ε}}

Страницы