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

UptoLike

ВУЗ: 

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

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

Рубрика: 

185
11
11
1
1
(FIRST ( ) ) { , } { } { , },
(FIRST ( ) ) { } { } { },
G
G
AS L a b a b
L
⊕= ⊕ε=
ε⊕ =ε⊕ ε=ε
и тогда
1
11
(FIRST ( ) ) (FIRST ( ) ) { , } { } .
k
GG
AS L L a b⊕∩ ε⊕= ∩ε=∅
Имеем также два альтернативных правила A→aA, A → b для нетерминала A.
Требуется
вычислить (
1
FIRST
G
(aA) ⊕
1
L) ∩ (
1
FIRST
G
(b) ⊕
1
L), где L∈σ(A)=
{{ε,a,b}}. Получаем
11
11
1
1
(FIRST ( ) ) { } { , } { },
(FIRST ( ) ) { } { } { },
G
G
aA L a a b a
bLb b
⊕=⊕ε, =
⊕=⊕ε=
и тогда
11
11
(FIRST ( ) ) (FIRST ( ) ) { } { } .
GG
aA L b L a b⊕∩ ⊕= ∩=∅
Так как оба пересечения пусты, то данная грамматика G действительно
LL(1)-грамматика.
Теорема 2.8. Пусть G = (V
N
,V
T
,P, S) — контекстно-свободная грамматика.
Алгоритм 2.6 правильно вычисляет функцию σ(A) для любого нетерминала
A ∈V
N
и k ≥ 0.
Доказательство.
Фактически достаточно показать, что
(,) (,),
j
A
BAB
′′
σ
=σ
если при i > j для всех A, B∈V
N
.
Не нарушая общности рассуждений, будем предполагать, что G —
приведённая грамматика.
I. Покажем сначала, что (,) (,).
j
AB AB
′
′
σ
⊆σ
Индукцией по i покажем, что для любого i ≥ 0.
База. Пусть i =0, т.е.
0
(,).LAB
′
∈
σ Согласно шагу 1 алгоритма 2.6 суще-
ствует правило
A →βBα∈P, β, α∈V
*
,FIRST()
G
k
L
=
α. Поскольку грамматика G
приведённая, то существует вывод, в частности левосторонний,
Следовательно, по определению
FIRST ( ) ,
G
k
LAB
′
=
α∈σ( ).
База доказана.
Индукционная гипотеза. Предположим, что аналогичное утверждение
выполняется для всех i ≤ n (0 ≤ n ≤ j).
Индукционный переход. Докажем, что тогда аналогичное утверждение
верно для i = n +1.
Пусть
1
(,).
n
L
AB
+
′
∈σ
Согласно шагу 2 алгоритма 2.6 либо
(,)
n
L
AB
′
∈σ
и
тогда в соответствии с индукционной гипотезой (,),LAB
∈
σ либо существуют
правило A → X
1
X
2
…X
m
∈ P и
N
(,), , 1 ,
p
n
p
LXBXVpm
′
′
∈
σ∈≤≤ такие, что
1
2
FIRST ( ... ).
G
kp
pm
k
LL X X X
+
+
′
=⊕
Согласно индукционной гипотезе, применен-
ной
к
(,),
n
p
LXB
′′
∈σ
можем утверждать,
что
(,)
p
LXB
′
′
∈
σ
и что существует
левосторонний вывод вида а Тогда можно постро-
ить левосторонний вывод:
lm
*
AwB⇒α.
(,) (,)
i
AB AB
′
′
σ
⊆σ
(,) (,)
j
i
AB AB
′′
σ=σ

Страницы