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

UptoLike

ВУЗ: 

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

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

Рубрика: 

156
Говорят, что грамматика, в которой каждый левосторонний вывод имеет
это свойство, есть LL(k)-грамматика.
Будет показано, что для каждой LL(k)-грамматики можно построить детер-
минированный левосторонний анализатор, который действует за линейное
время.
2.1.2. Формальное определение
Определение 2.3. Пусть G =(V
N
,V
T
,P,S) — контекстно-свободная грамма-
тика. Определим функцию
FIRST ( )
G
k
α={w ∈ V
T
*
| либо |w| < k и
либо
|w| = k и для некоторой цепочки x∈ V
T
*
}.
Здесь
k ≥0 — целое, α∈ (V
N
∪ V
T
)
*
.
Отметим, что эта функция определена, в частности, и для терминальной
цепочки, и тогда, когда она пуста. При этом верхний индекс грамматики не
существен, так как никакие правила для вывода терминальной цепочки из
такого аргумента не требуются.
Определение 2.4. Пусть G=(V
N
,V
T
,P,S) — контекстно-свободная
грамматика. Говорят, что G есть LL(k)-грамматика для некоторого фиксирован-
ного
k, если для любых двух левосторонних выводов вида
1)
S wAα wβα wx,
2)
S wAα wγα wy,
в которых
() (),
FIRST FIRST
GG
kk
x
y=
имеет место равенство β = γ.
Определение 2.5. Говорят, что контекстно-свободная грамматика G есть
LL-грамматика, если она LL(k) для некоторого k ≥0.
Пример 2.2. Пусть G = ({S, B}, {a, b}, P, S), где P = {S → aBS | b, B → a | bSB}.
По определению грамматика
G — LL(1), если
1)
S wAα wβα wx,
2)
S wAα wγα wy,
и если
x и y начинаются на один и тот же символ, то должно быть β = γ.
Рассмотрим два левосторонних вывода, в которых роль нетерминала
A
играет символ
S.
Имеем (1)
S
lm
⇒
aBS и (2) S
lm
⇒
b. Тогда w = α = ε, β = aBS, γ = b.
Ясно, что любая цепочка
x, выводимая из βα = aBS, начинается на a, а
цепочка
y, выводимая из γα = b, равна b. Поэтому если первый символ цепочки,
следующей за закрытой частью сентенциальной формы (
w = ε), есть a, то для
замены нетерминала
S следует использовать первую альтернативу. Если она
начинается на
b, то вторую.
Рассмотрим два левосторонних вывода, в которых роль нетерминала A
играет символ
B:
Имеем
(1) S
lm
⇒
aBS
lm
⇒
aaS и (2) S
lm
⇒
aBS
lm
⇒
abSBS .
lm
*
⇒
lm
*
⇒
lm
*
⇒
lm
*
⇒
lm
⇒
lm
⇒
lm
*
⇒
lm
⇒
lm
*
⇒
lm
*
⇒
lm
⇒
lm
*
⇒
*
,
G
wα⇒
*
G
wxα⇒

Страницы