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

UptoLike

ВУЗ: 

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

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

Рубрика: 

161
Следствие 2.1. Теорему 2.2 можно переформулировать следующим обра-
зом: КС-грамматика G является LL(1)-грамматикой тогда и только тогда, когда
для каждого множества A-правил: A →α
1
|α
2
|…|α
n
— выполняются
следующие условия:
11
*
11
1) FIRST ( ) FIRST ( ) , 1 , ;
2) если то FIRST ( ) FOLLOW ( ) : 1 ,
.
GG
ij
GG
ij
G
при ij ijn
A для всех jjnji
α∩ α =∅ ≠ ≤ ≤
α⇒ε, α ∩ =∅ ≤ ≤ ≠
Определение 2.8. Контекстно-свободная грамматика G =(V
N
,V
T
,P,S) назы-
вается сильной LL(k)-грамматикой, если она удовлетворяет условию теоремы
2.2:
для всех
*
NNT
, , , , ( ) ,AA P AV VV→β →γ∈ β≠γ, ∈ βγ∈ ∪ таких, что существу-
ют правила A →β, A →γ ∈ P, β≠γ.
Следствие 2.2. Каждая LL(1)-грамматика является сильной. Однако
следующий пример показывает, что для k >1 не всякая LL(k)-грамматика
является сильной.
Пример 2.3. Рассмотрим cfg G =({S, A}, {a, b}, P, S), где
P =
{S → aAaa | bAba, A → b | ε}.
Используя теорему 2.1, проверим, что грамматика G — LL(2).
I. Проведем тестирование относительно нетерминала S:
2
2
22
FIRST ( ) { , },
FIRST ( ) { } независимо от ,
FIRST ( ) FIRST ( ) { , } { } .
G
G
GG
aAaa aa ab
bAba bb
aAaa bAba aa ab bb
α=
α= α
α∩ α= ∩ =∅
II. Проведем тестирование относительно нетерминала A. При этом следует
учесть, что
и , так что {,}. Тогда при S aAaa S bAba aa ba aa⇒⇒ α∈ α=
2
2
22
FIRST ( ) { },
FIRST ( ) { },
FIRST( ) FIRST( ){}{} ;
G
G
GG
baa ba
aa aa
baa aa ba aa
=
=
∩=∩=∅
при α = ba
2
2
22
FIRST ( ) { },
FIRST ( ) { },
FIRST( ) FIRST(){}{} .
G
G
GG
bba bb
ba ba
bba ba bb ba
=
=
∩=∩=∅
Так что G — действительно LL(2)-грамматика. Но поскольку, очевидно, что
2
FOLLOW ( ) { },
G
S
=
ε то, учитывая существование выводов S ⇒aAaa и S ⇒bAba,
заключаем, что
2
FOLLOW ( ) { , }.
G
Aaaba=
Проверка условия сильной LL(2)-грамматики показывает, что для S:
22
FIRST ( { }) FIRST ( { }) { , } { } ,
GG
aAaa bAba aa ab bbε∩ ε= ∩ =∅
а для
A:
22
FIRST ( { , }) FIRST ( { , }) { , } { , } { } .
GG
baaba aaba babb aaba ba∩ε=∩=≠∅
Таким образом, грамматика G — LL(2), но не сильная LL(2)-грамматика.
FIRST ( FOLLOW ( )) FIRST ( FOLLOW ( ))
GG GG
kk kk
AAβ∩γ=∅

Страницы