Теория и реализация языков программирования

         

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-грамматикой.



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий