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

       

Следствия определения LL(k)- грамматики


Теорема 4.6. КС-грамматика G = (N, ?, P, S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил A

? и A
? из Р пересечение FIRSTk(?
)
FIRSTk(?
) пусто при всех таких ?A
, что
.

Доказательство. Необходимость. Допустим, что ?, A,

, ? и ? удовлетворяют условиям теоремы, а FIRSTk(?
)
FIRSTk(?
) содержит x. Тогда по определению FIRST для некоторых y и z найдутся выводы

(Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных нетерминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k; то y = z = e. Так как ?

?, то G не LL(k)-грамматика.

Достаточность. Допустим, что G не LL(k)-грамматика.

Тогда найдутся такие два вывода

что цепочки x и y совпадают в первых k позициях, но ?

?. Поэтому A
? и A
? - различные правила из P и каждое из множеств FIRSTk(?
) и FIRSTk(?
) содержит цепочку FIRSTk(x), совпадающую с цепочкой FIRSTk(y).

Пример 4.8. Грамматика G, состоящая из двух правил S

aS | a, не будет LL(1)-грамматикой, так как

FIRST1(aS) = FIRST1(a) = a.

Интуитивно это можно объяснить так: видя при разборе цепочки, начинающейся символом a, только этот первый символ, мы не знаем, какое из правил S

aS или S
a надо применить к S. С другой стороны, G - это LL(2)-грамматика. В самом деле, в обозначениях только что представленной теоремы, если
, то A = S и
= e. Так как для S даны только два указанных правила, то ? = aS и ? = a. Поскольку FIRST2(aS) = aa и FIRST2(a) = a, то по последней теореме G будет LL(2)-грамматикой.



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