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

UptoLike

ВУЗ: 

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

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

Рубрика: 

159
I. Необходимость. Пусть G — LL(1)-грамматика, но условие не выполне-
но, т.е. существуют правила A
→β, A →γ∈P, β≠γ, c ∈(V
T
∪ {ε}), такие, что
11
FIRST ( FOLLOW ( ))
GG
cA∈β и
11
FIRST ( FOLLOW ( )).
GG
cA∈γ
Это
означает, что существуют
1
,FOLLOW(),
G
ab A∈ такие, что
1
FIRST ( )
G
ca∈βи
1
FIRST ( ),
G
cb∈γи cогласно определению функции
1
FIRST
G
существуют выводы:
если c
∈ V
T
, или если c = ε.
Случай 1
: c ∈V
T
, βa
*
G
⇒cu
'
a = cu, β
*
G
⇒cu
'
, u
'
∈ V
T
*
; γb
*
G
⇒cv
'
b, γ
*
G
⇒cv
'
, v
'
∈V
T
*
.
Так
как грамматика G — приведённая, то существует вывод, в частности
левосторонний, который порождает сентенциальную форму, содержащую A:
S
wA
α, который может быть продолжен двумя способами:
где
вывод существует также в силу приведенности грамматики G.
Итак, имеем два левосторонних вывода 1) и 2), фигурирующие в опреде-
лении LL(k)-грамматик, в которых в роли цепочки x используется cu
'
z, в роли
цепочки
y — cv
'
z, причём
но
β≠γ. Следовательно, грамматика G — не LL(1), что противоречит
первоначальному предположению.
Случай 2
: γb
cv
'
b, γ
cv
'
, v
'
∈V
T
*
.
Согласно определению означает, что существует вывод, в
частности левосторонний, вида такой, что или, что то
же самое, существует вывод при некотором z
∈ V
T
*
. Продолжим лево-
сторонним образом вывод двумя способами:
Получили
два вывода 1) и 2), фигурирующие в определении LL(k)-грам-
матик,
с цепочкой cz в роли x и цепочкой cv
'
cz в роли y.
Имеем
11 11
() ( ) {}, () ( ) {},
FIRST FIRST FIRST FIRST
GG GG
x
cz c y cv cz c
′
== = =
т.е. но
β≠γ. Следовательно, грамматика G — не LL(1),
что противоречит первоначальному предположению.
Случай 3
:
Он разбирается аналогично предыдущему.
Случай 4
:
x
x
y
v
v
l m
*
⇒
*
G
⇒
*
G
⇒
y
11 11
() ( ) {}, () ( ) {},
FIRST FIRST FIRST FIRST
GG G G
x
cu z c y cv z c
′′
== ==
11
() (),
FIRST FIRST
GG
x
y=
**
T1
, , , , FOLLOW ( ).
G
GG
cV abcc A∈β⇒εγ⇒ε== ∈
v
u
v
1
FOLLOW ( )
G
cA∈
**
è ,
GG
acu vcvβ⇒ γ⇒
**
и ,
GG
ab
β
⇒ε γ ⇒ε
1
FIRST (
G
c
∈
α)
*
T1
, , FOLLOW ( );
G
G
cV a ca A∈β⇒ε,= ∈
*
lm
SwA⇒α,
*
lm
czα⇒
*
lm
SwA⇒α
***
lm lm lm lm
1) ,SwA w w wcz⇒ α⇒ βα⇒ α⇒
***
lm lm lm lm
2) .SwA w wcv wcvcz
′
′
⇒α⇒γα⇒ α⇒
*
*
**
TT 1
, , , ; , FOLLOW ( ).
G
G
GG
cV a cua cuu V b cb A
′′′
∈β⇒ β⇒ ∈γ⇒ε, = ∈
***
lm lm lm lm
2) ,SwA w wcv wcvz
′′
⇒ α⇒ γα⇒ α⇒
***
lm
lm lm
lm
1) ,SwA w wcu wcuz
′
′
⇒α⇒βα⇒ α⇒
*
T
lm
, ,zz V
∗
α⇒ ∈
u

Страницы