LL(k)-грамматики

Определение. КС-грамматика G = (N, ?, P, S) называется LL(k)-грамматикой для некоторого фиксированного k, если из

(1)

(2)

для которых

и

FIRSTk(x) = FIRSTk(y), вытекает, что ? = ?.

Говоря менее формально, G будет LL(k)- грамматикой, если для данной цепочки

и первых k символов (если они есть), выводящихся из A, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки,

Рис. 4.4. 

начинающейся с ? и продолжающейся упомянутыми k терминалами.

Грамматика называется LL(k)-грамматикой, если она LL(k)-грамматика для некоторого k.

Пример 4.7. Рассмотрим грамматику G = ({S, A, B}, {0, 1, a, b}, P, S), где P состоит из правил

S

A | B, A aAb | 0, B aBbb | 1.

Здесь L(G) = an0bn | n

0 an1b2n | n 0. G не является LL(k)-грамматикой ни для какого k. Интуитивно, если мы начинаем с чтения достаточно длинной цепочки, состоящей из символов a, то не знаем, какое из правил S A и S B было применено первым, пока не встретим 0 или 1.

Обращаясь к точному определению LL(k)-грамматики, положим ? =

= e; ? = A; ? = B; x = ak0bk и y = ak1b2k. Тогда выводы

соответствуют выводам (1) и (2) определения. Первые k символов цепочек x и y совпадают. Однако заключение ? = ? ложно. Так как k здесь выбрано произвольно, то G не является LL-грамматикой.

Содержание раздела

---

---