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

UptoLike

ВУЗ: 

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

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

Рубрика: 

158
Остаётся сопоставить эти два левосторонних вывода с теми, которые
участвуют в определении
LL(k)-грамматик. Здесь в роли цепочки x использу-
ется
zu, а в роли цепочки y — zv.
Очевидно, FIRST ( ) FIRST ( ) ,
GG
kk
x
yz==но β≠γ, что противоречит предпо-
ложению о том, что G — LL(k)-грамматика.
В частности, если
|z| < k и u = v = ε, то имеем два разных левосторонних
вывода одной и той же терминальной цепочки wz. Это означает, что G — не
однозначная грамматика и, естественно, не LL(k) ни при каком k.
Необходимость доказана.
II. Достаточность. Пусть условие теоремы выполнено, но G — не LL(k)-
грамматика. Это значит, что существуют два левосторонних вывода:
1) S wA
α wβα wx,
2) S wA
α wγα wy,
в которых
FIRST
G
k
(x)=
FIRST
G
k
(y), но β≠γ.
Пусть Имеем
βα
x и γα
y. Согласно опре-
делению функции FIRST
G
k
из существования этих двух выводов заключаем, что
FIRST ( ) FIRST ( ),
FIRST ( ) FIRST ( )
GG
kk
GG
kk
zx
zy
∈⊆βα
∈⊆γα
и, следовательно,
FIRST ( ) FIRST ( ) ,
GG
kk
z ∈βα∩γα≠∅
что входит в противоречие с первоначальным предположением о том, что
условие
теоремы выполняется. Достаточность доказана, а вместе с ней и вся
теорема.
Определение 2.7. Пусть G =(V
N
, V
T
, P, S) — контекстно-свободная грам-
матика, и
β∈V
*
. Определим функцию
*
*
T
FOLLOW ( ) { FIRST ( )}.
GG
kk
G
wV S w
β
=∈ ⇒γβα, ∈ αЗдесь k ≥0 — целое.
Теорема 2.2. Чтобы контекстно-свободная грамматика G = (V
N
, V
T
, P, S)
была
LL(1)-грамматикой, необходимо и достаточно, чтобы
11 11
FIRST ( FOLLOW ( )) FIRST ( FOLLOW ( ))
GG GG
AAβ∩γ=∅
для
всех A∈ V
N
, β,γ∈ (V
N
∪ V
T
)
*
, таких, что существуют правила A →β,
A
→γ∈P, β≠γ.
Доказательство.
Требуется пояснить, что в формулировке условия
теоремы аргумент функции
G
1
FIRST — не цепочка, как было определено ранее,
а множество
цепочек. Расширение области определения этой функции на
множества производится естественным образом:
11
FIRST ( ) FIRST ( ),
GG
sW
Ws
∈
=
∪
где
*
.WV
⊆
Обе части теоремы доказываются методом “от противного”. Как и ранее, не
нарушая общности рассуждений, будем считать грамматику G приведённой.
l m
*
⇒
l m
*
⇒
l m
*
⇒
lm
⇒
l m
*
⇒
lm
⇒
l m
*
⇒
l m
*
⇒
FIRST ( ) FIRST ( ) .
GG
kk
x
yz==

Страницы