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

UptoLike

ВУЗ: 

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

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

Рубрика: 

170
Индукционный переход. Докажем утверждение для l = n +1.
Пусть
(xy, S$, ε) = (x’y’, S$, ε) (y’, α’$, π’)=
= (y
’, Aγ$, π’) (y’, βγ$, π’i) (y, α$, π),
где π = π
’i, |π’| = n, xy = x’y’, α’= Aγ. Завершающие pop-движения показывают,
что y
’= zy, βγ = zα; т.к. xy = x’y’ = x’zy, то x = x’z.
Последнее
движение типа 1 было выполнено благодаря элементу M(A, u’) =
(β, i) для
1
FIRST ( ),
G
uy
′′
∈ что предполагает существование правила A → β под
номером i, а также выполнение условия
11
FIRST (FOLLOW ( )).
GG
uA
′
∈ Оно дей-
ствительно выполняется, поскольку
11 1
111
FIRST ( ) FIRST ( ) FIRST ( )
FIRST ( ) FIRST ( FOLLOW ( )).
GG G
GGG
uy zyz
A
′′
∈∈∈α=
⊆
=βγ β
Одновременно можно воспользоваться индукционной гипотезой в
применении к (x
’y’, S$, ε) (y’, α’$, π’), поскольку
11 1
111
FIRST ( ) FIRST ( ) FIRST ( )
FIRST ( ) FIRST ( ) FIRST ( ).
GG G
GGG
yzyz
A
′
∈∈α=
⊆
′
=
βγ γ = α
и получить как следствие S x
’α’ = x’Aγ x’βγ = x’zα = xα.
Что и требовалось.
Из утверждений I и II при y = α = ε заключаем, что S
x тогда и только
тогда, когда (x, S$, ε)
(ε, $, π). А это и означает, что 1-предсказывающий
алгоритм анализа, построенный согласно алгоритму 2.1, является правильным
для LL(1)-грамматики G.
Теорема доказана.
Замечание 2.1. Алгоритм 2.1 пригоден для построения анализаторов для
LL(k)-грамматик и при k >1, если только они сильные. При его применении к сильным
LL(k)-грамматикам всюду, где используется параметр 1, следует использовать
значение
k.
Прежде чем перейти к обсуждению LL-анализа при k > 1,
введём в
рассмотрение ещё одну полезную операцию над языками
.
Определение 2.11. Пусть Σ — некоторый алфавит и L
1
, L
2
⊆ Σ
*
. Положим
Пример 2.7. Пусть L
1
= {ε, abb} и L
2
= {b, bab}. Тогда L
1
⊕
2
L
2
= {b, ba, ab}.
Операция ⊕
k
подобна инфиксной операции.
Лемма 2.1. Для любой контекстно-свободной грамматики G=(V
N
,V
T
,P,S)
и любых цепочек α,β∈V
*
имеет место тождество
.
−−
*
−
−
*
−−
l m
π
⇒
*
−−
w ∈Σ
*
k
x ∈L
1
, y ∈L
2
, w =
x
y, если
|
xy
|
k,
()
FIRST
G
k
x
y
в противном случае
2
1
k
LL⊕=
() () ().
FIRST FIRST FIRST
GGG
k
kkk
αβ = α ⊕ β
l m
π
⇒
'
l m
()i
⇒
*
−−

Страницы