Следствия определения 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)-грамматикой.

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

---

---

---

Главная сайта

---