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

UptoLike

ВУЗ: 

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

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

Рубрика: 

180
Метод. Согласно лемме 2.1
так что задача сводится к вычислению ()
FIRST
G
k
X
для X ∈V.
Если
X ∈V
T
∪{ε}, то вычислять нечего, так как в этом случае
(){}.
FIRST
G
k
X
X=
Остаётся найти способ вычисления для X
∈V
N
.
Мы будем использовать метод последовательных приближений и строить
последовательности множеств F
i
(X ) для всех X ∈V
N
∪ V
T
, i = 0,1,2,... .
1. F
i
(a) = {a} для всех a ∈V
T
и i ≥ 0.
2. F
0
(A) = {x ∈V
T
*
k
| ∃ A → xα∈P, где |x | = k, либо |x | < k и α = ε}.
3. Предположим, что F
0
(A), F
1
(A),…, F
i –1
(A) уже построены для всех A∈V
N
.
Тогда
*
1
1
2
T
1
2
11
1
() () { ... ,
( ) ( ) ... ( )}.
kk
k
k
i
i
m
m
i
i
i
FA F A x A YY Y P
V
xF Y F Y F Y
−
−
−
−
=∪∈∃→ ∈
∈⊕ ⊕⊕
4. Так как
*
1
T
() ()
k
i
i
FAFA
V
−
⊆⊆ для всех A ∈V
N
и i >0, то шаг 3 требуется
повторять до тех пор, пока при некотором i = j не окажется F
j
(A)=F
j +1
(A) для
всех A
∈V
N
. Очевидно, что тогда F
j
(A)=F
j +1
(A)=F
j +2
(A)=… .
5. Остаётся только положить
() ().
FIRST
G
j
k
A
FA=
Пример 2.10. Рассмотрим ещё раз LL(1)-грамматику из примера 2.6:
({ , , , , },{ , , ,(,)}, , ),
*
GEETTFa PE
′′
=+
где
P = { (1) ,ETE
′
→
(2) ,ETE
′
′
→+
(3) ,E
′
→ε (4) ,TFT
′
→
(5)
,
*
TFT
′′
→
(6)
,T
′
→ε
(7) F → (E), (8) F → a},
и построим функцию
1
()
FIRST
G
A для всех {, ,, , }.
A
EETT F
′
′
∈
Прежде всего согласно шагу 2 алгоритма 2.5 получаем
00 0 0 0
( ) ( ) , ( ) { , }, ( ) ( , ), ( ) {(, }.
*
FE FT FE FT FF a
′′
==∅ =+ε =ε =
Далее шаг 3 даёт
11
00 0
0
1
() () ( ) () {, } ();FE FT FE F E FE
′
=⊕ ∪=∅⊕+ε∪∅=∅=
11
11
00 00
0
1
0
() () () () () ()
{ } { , } { } { , } { , } ( );
FE F FT FE F FE
FE
′′′
=+⊕ ⊕ ∪ε∪ =
′
+⊕∅⊕+ε∪ε∪+ε=+ε=
11
00 0
0
1
() () ( ) () {(,} {,} {(,} ();
*
FT FF FT FT a a FT
′
=⊕ ∪=⊕ε∪∅=≠
11
11
0000
0
1
0
() () () () () ()
*
{ } {(, } { , } { } { , } { , } ( );
*
**
*
FT F F F FT F FT
aFT
′′′
=⊕ ⊕ ∪ε∪ =
⊕⊕ε∪ε∪ε=ε=
11
11
0000
0
1
0
()(()()())()()
{(} {)} { } {(, } {(, } ( ).
FF F FE F Fa FF
aaaFF
=⊕ ⊕∪ ∪ =
⊕∅⊕ ∪ ∪ = =
Поскольку процесс не сошелся для всех нетерминалов, необходимо
повторить шаг 3, что даёт
1
11
1
2
() () ( ) () {(,} {,} {(,} ();
k
k
FE FT FE FE a a FE
′
=⊕ ∪=⊕+ε∪∅=≠
21
(){, } ();FE FE
′′
=+ε=
2
1
() {(, } ();FT a FT==
()
FIRST
G
k
X
12
FIRST() FIRST( ) FIRST( ) ... FIRST( ),
GG G G
kkkkkkkn
X
XXβ= ⊕ ⊕ ⊕

Страницы