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

UptoLike

ВУЗ: 

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

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

Рубрика: 

171
Доказательство.
I.
Пусть
1
().
FIRST
G
w∈αβ
Докажем,
что тогда () ().
FIRST
FIRST
G
G
k
k
k
w
∈
α⊕ β
Обозначим
112
1
FIRST ( ), ( ).
FIRST
G
G
LL=α=β Из того, что
1
(),
FIRST
G
w∈αβ
следует,
что
1
(),
FIRST
G
wuv∈ если
**
,.
uvαβ
⇒⇒
Последние два вывода
означают, что
1
() () .
FIRST FIRST
GG
kk
x
uL
∈
∈α=
Аналогично
2
() () .
FIRST FIRST
GG
kk
yv L∈∈β=Учитывая определение
опера-
ции
⊕
k
,
заключаем, что
2
1
1
FIRST ( ) .
G
k
x
yL L∈⊕
Остаётся убедиться в том, что () (){}.
FIRST FIRST
GG
kk
x
yuvw∈=
Так как то u = xu
’ и v = yv’ при некоторых u’,
v
’∈V
T
*
, причём если |x | < k, то u’ = ε, и если | y | < k, то v’ = ε. Итак, имеем uv = xu’yv’.
Если
| x | = k, то
11
(){} ().
FIRST FIRST
GG
wuvx xy∈==
Если
| x | < k, то u’= ε и
11
() ( ),
FIRST FIRST
GG
wuv xyv
′
∈= причём, если | y | < k,
то v
’= ε и тогда
11
() (),
FIRST FIRST
GG
wuv xy∈=
если же
| y | = k, то
11 1
() ( ) ().
FIRST FIRST FIRST
GG G
w uv xyv xy
′
∈= =
Итак,
1
2
11 1 1
() () () ().
FIRST FIRST FIRST FIRST
GG G G
kk
wuv xyLL∈=∈⊕=α⊕β
II.
Пусть
11
() ().
FIRST FIRST
GG
k
w∈α⊕ β Докажем, что тогда
1
().
FIRST
G
w∈αβ
Согласно определению операции
⊕
k
существуют цепочки FIRST ( ),
G
k
x ∈α
FIRST() è FIRST( ).
GG
kk
ywxy∈β∈
Кроме того, согласно определению
FIRST
G
k
имеем
**
,
x
uyvαβ
⇒⇒
при некоторых u, v ∈V
T
*
и
() ().
FIRST
FIRST
G
G
kk
xuyv ∈αβ
Остаётся убедиться в том, что
() ().
FIRST
FIRST
G
G
kk
x
uyv xy∈
Если
|x | = k, то () (){}.
FIRST
FIRST
G
G
kk
x
uyv xy x∈=
Если
|x | < k, то u = ε и
() ()
FIRST
FIRST
G
G
kk
uyv xyv∈
причём, если
| y | < k, то v = ε и
FIRST
G
k
(xuyv)=
FIRST
G
k
(xy), в противном случае от v ничего не зависит и
FIRST
G
k
(xuyv)=
FIRST
G
k
(xy). Следовательно, FIRST ( ) FIRST ( ) FIRST ( ).
GG G
kk k
wxy xuyv
∈
=∈αβ
Из рассуждений I и II следует утверждение леммы. Что и требовалось.
§ 2.5. Анализ в LL(k)-грамматиках
В общем случае анализа в LL(k)-грамматиках по нетерминалу и
аванцепочке невозможно однозначно определить правило для построения
очередной сентенциальной формы.
Рассмотрим, например, LL(2)-грамматику из примера 2.3:
S
→ aAaa | bAba; A → b | ε.
Согласно
алгоритму 2.1 для замены нетерминала A в выводе S
wAα wx
следует применять правило A
→ β, если аванцепочка
2
FIRST ( )
G
ux∈ принад-
l m
*
⇒
(),a
(),
FIRST
FIRST
G
G
k
k
uy
v
x
∈
∈
l m
*
⇒

Страницы