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

UptoLike

ВУЗ: 

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

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

Рубрика: 

178
Индукционная гипотеза. Предположим, что утверждение выполняется
для всех l
≤ n (n ≥ 1).
Индукционный переход. Докажем утверждение для l = n +1.
Пусть
00
,
*
*
(,$,)( ,$,) (,$,)
( , $, ) ( , $, ) ( , $, ),
AL
xy T x y T y
yT y i y
′′ ′ ′ ′
ε= ε −− α π =
′′ ′
=γπ−−γπ−−απ
β

где π=π’i, |π’ |= n.
Завершающие pop-движения предполагают, что y’ = zy, βγ = zα.
Кроме того, мы имеем xy = x
’y’ = x’zy, откуда x = x’z.
Так как
′
α
= T
A,L
γ
, то последнее движение типа 1 было выполнено благо-
даря элементу M(T
A,L
, u) = (
β
, i) для u ∈
FIRST
G
k
(y’), что предполагает суще-
ствование правила A
→ β под номером i.
Воспользовавшись индукционной гипотезой в применении
к переходу
(x’y’, T
0
$, ε) (y’, α’$, π’), поскольку
( ) FIRST( ) FIRST( ) FIRST( )
FIRST
( ) FIRST ( ),
FIRST
GGG
G
kkk
k
G
G
k
k
yzyz
A
′
=
⊆α=βγ⊆
′
⊆γ=α
получаем как следствие
Здесь
α, β, γ — гомо-
морфные образы
α
,
β
,
γ
соответственно. Что и требовалось.
Из рассуждений I и II при y =
α = ε заключаем, что S
x тогда и только
тогда, когда (x, T
0
$, ε) (ε, $, π). А это и означает, что k-предсказывающий
алгоритм анализа, построенный согласно алгоритму 2.3, является правильным
для LL(k)-грамматики G. Что и требовалось доказать.
Теорема 2.6. Число шагов, выполняемых k-предсказывающим алгоритмом
анализа, линейно зависит от длины анализируемой цепочки.
Доказательство. Поскольку k-предсказывающий алгоритм анализа
применим только к LL(k)-грамматикам, а они не могут быть леворекурсивными
(теорема
2.3), то максимальное число шагов в любом левостороннем выводе вида
A
B
α меньше, чем некоторая константа c, зависящая от грамматики. Во
всяком случае, если бы существовал
вывод такого вида, длина которого была
бы больше числа нетерминалов грамматики
A
⇒ B
1
α
1
⇒ B
2
α
2
⇒…⇒ B
m
α
m
= Bα,
то какие-то два нетерминала (B
i
и B
j
при i ≠ j) неизбежно оказались бы одина-
ковыми. Другими словами, мы имели бы вывод B
i
α
i
B
j
α
j
при B
i
= B
j
, что
означало бы леворекурсивность грамматики.
Поскольку согласно теореме 2.3 LL(k)-анализатор аккуратно воспроизводит
в своем магазине открытые части сентенциальных форм левостороннего
вывода входной цепочки, то участкам вывода вида B
1
α
1
⇒ B
2
α
2
⇒…⇒ B
m
α
m
соответствуют движения типа 1, следующие непосредственно друг за другом, и
их число не превосходит c.
Пусть цепочка x
∈L(G), где G — LL(k)-грамматика и n = |x|. Разбирая
цепочку x, k-предсказывающий алгоритм анализа, построенный для граммати-
ки G, совершает ровно n pop-движений и не более c движений типа 1 перед
*
−−
()
lm
l m
i
Sx xA x xz x
π
′′ ′ ′ ′
⇒α= γ⇒ γ= α=α.
β
*
−−
l m
+
⇒
l m
+
⇒
l m
π
⇒

Страницы