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




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


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

(1)

S \Rightarrow^*_i \; \omega A \alpha \Rightarrow_l \omega \beta \alpha \Rightarrow^* \omega x

(2)

S \Rightarrow^*_i \; \omega A \alpha \Rightarrow_l \omega \gamma \alpha \Rightarrow^* \omega x
для которых

и

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

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

\omega A \alpha \in (N \cup \Sigma)^*
и первых 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. Тогда выводы

\begin{align*} &S \Rightarrow^0_l S \Rightarrow_l A \Rightarrow^*_l a^k0b^k \\ &S \Rightarrow^0_l S \Rightarrow_l B \Rightarrow^*_l a^k1b^{2k} \end{align*}

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




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