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

UptoLike

ВУЗ: 

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

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

Рубрика: 

162
Теорема 2.3. Если G =(V
N
, V
T
, P, S) — контекстно-свободная грамматика,
и
G — леворекурсивна, то G — не LL(k)-грамматика ни при каком k.
Доказательство будем проводить в предположении приведенности
грамматики G, поскольку, как отмечалось ранее, бесполезные нетерминалы не
влияют на выполнение LL(k)-критерия.
Так как грамматика G леворекурсивна, то существует вывод вида A
Aρ,
где ρ ≠ ε, хотя и не исключается, что ρ
ε. Напомним, что A
Aρ означает,
что существует вывод вида A
β
Aρ.
Отметим, что независимо от того, β = Aρ или β≠Aρ, должно существо-
вать ещё какое-то правило для A, скажем, A →γ (γ≠β), ибо в противном случае
ничего, кроме A
Aρ
i
, где i ≥ 0, вывести из нетерминала A было бы невоз-
можно, что противоречило бы приведенности грамматики G.
В
любом случае вывод A
Aρ в общем случае состоит из шагов вида
A
G
⇒
A
1
α
1
G
⇒
A
2
α
2
α
1
G
⇒
...
G
⇒
A
m –1
α
m –1
...α
1
G
⇒
A
m
α
m
...α
1
= Aρ,
где
A
m
= A, ρ = α
m
...α
1
. Очевидно, что в этом выводе были использованы
правила A → A
1
α
1
, A
1
→ A
2
α
2
,…, A
m –1
→ A
m
α
m
, где A
m
= A. Хотя бы одно из этих
правил должно иметь альтернативу, не начинающуюся ни на один из
нетерминалов A
1
, A
2
,…, A
m
(иначе грамматика G была бы неприведённой).
Пусть, например, существует A
j
→ A
j +1
α
j +1
| γ , где γ≠A
j +1
α
j +1
.
Так как грамматика G — приведённая, существует сентенциальная форма,
в частности, левостороннего вывода, в которой участвует нетерминал A,
например S
wAα, который может быть продолжен следующим образом:
S
wAα
wAρ
i
α
wA
1
α
1
ρ
i
α
…
wA
j
α
j
…α
1
ρ
i
α.
Далее этот вывод можно продолжить двумя способами:
1)
wA
j +1
α
j +1
α
j
…α
1
ρ
i
α
wA
m
α
m
…α
1
ρ
i
α = wAρ
i +1
α
wA
j
α
j
…α
1
ρ
i +1
α
wγα
j
…α
1
ρ
i +1
α
wzx
j
…x
1
r
i +1
t,
2)
wγα
j
…α
1
ρ
i
α
wzx
j
… x
1
r
i
t,
предполагая, что ввиду приведённости грамматики существуют выводы
γ
z, α
j
x
j
,…, α
1
x
1
, ρ
r , α
t, где w, z, x
j
, …, x
1
, r, t ∈ V
T
*
.
Эти два вывода можно сопоставить с теми, которые фигурируют в
определении LL(k)-грамматик. Здесь x = zx
j
…x
1
r
i +1
t, а y = wzx
j
…x
1
r
i
t.
Если r ≠ε, то каким бы большим ни было k, всегда путем выбора i можно
добиться, чтобы FIRST ( ) FIRST ( )
GG
kk
x
y= при том, что в точке, где эти два
вывода
разошлись, были применены различные альтернативы для раскрытия
нетерминала A
j
:
A
j
→ A
j +1
α
j + 1
| γ, γ≠A
j +1
α
j +1
.
Если r = ε, то имеем два разных левосторонних вывода одной и той же
терминальной цепочки wzx
j
…x
1
t. То и другое означает, что грамматика G — не
LL(k) ни при каком k.
x
y
G
+
⇒
*
G
⇒
G
+
⇒
G
⇒
*
G
⇒
*
G
⇒
G
+
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
*
l m
⇒
lm
⇒
lm
⇒
lm
⇒
lm
⇒
lm
⇒
lm
⇒

Страницы