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

UptoLike

ВУЗ: 

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

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

Рубрика: 

160
Согласно определению означает существование вывода
вида такого, что или, что то же самое, при
некотором
*
T
.zV∈
Теперь вывод продолжим левосторонним образом двумя способами:
Мы получили два левосторонних вывода (1) и (2), фигурирующих в
определении LL(k)-грамматик, в которых в роли цепочек x и y используются
одинаковые терминальные цепочки сz, функция от них даёт одинако-
вый результат, равный с, притом что β ≠ γ. Следовательно, грамматика G — не
LL(1), что противоречит первоначальному предположению
1
.
Случай 5
:
Как
и в случае 4, означает существование вывода
такого, что Его можно продолжить левосторонним образом двумя спо-
собами:
В роли цепочек x и y здесь используется ε.
Имеем
11
() () {},
FIRST FIRST
G
G
xy==εхотя по-прежнему β ≠ γ.
Следовательно, грамматика G — не LL(1), что противоречит первоначаль-
ному предположению
2
. Необходимость доказана.
II. Достаточность. Пусть условие теоремы выполнено, но грамматика G
— не LL(1). Тогда существуют два левосторонних вывода вида
1) S
wAα
wβα
wx,
2) S
wAα
wγα
wy,
в которых Поскольку то
11
11
FIRST ( ) FIRST ( ),
FIRST ( ) FIRST ( ),
GG
GG
x
y
⊆
βα
⊆
γα
и тогда заключаем, что
11 1 1
FIRST ( ) FIRST ( ) FIRST ( ) FIRST ( ) ,
GG G G
xy
⊆
=
βα ∩ γα ≠ ∅
что противоречит
первоначальному предположению о том, что условие
теоремы выполнено. Достаточность и теорема доказаны.
1
Противоречие можно видеть и в том, что существуют два разных левосторонних вывода
для одной и той же терминальной цепочки az.
2
Противоречие можно видеть и в том, что существуют два разных левосторонних вывода
для одной и той же терминальной цепочки w.
x
l m
*
SwA⇒α,
l m
*
czα⇒
l m
*
SwA⇒α
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
lm
⇒
lm
⇒
1
FIRST
G
**
1
, , , FOLLOW ( ).
G
GG
ab Aβ⇒ε γ⇒ε = =ε ε∈
1
FOLLOW ( )
G
Aε∈
*
,
G
SwA⇒α
*
lm
.α⇒ε
1
FOLLOW ( )
G
cA∈
1
FIRST ( )
G
c
∈
α
***
lm lm lm
lm
1) ,SwA w w wcz⇒α⇒βα⇒α⇒
***
lm lm lm
lm
2) .SwA w w wcz⇒α⇒γα⇒α⇒
y
***
lm lm lm
lm
***
lm lm lm
lm
1) ,
2) .
SwA w w w
SwA w w w
⇒α⇒βα⇒α⇒
⇒α⇒γα⇒α⇒
11
FIRST ( ) FIRST ( ), í î .
GG
xy=β≠γ
**
lm lm
è ,
x
yβα⇒ γα⇒

Страницы