5.3. Ll(k) - грамматики

Выше анализаторы были определены как недетерминированные МП-преобразователи. Попытка их реализации для широкого класса КС-грамматик приводит к так называемым алгоритмам с “возвратами” которые требуют слишком больших затрат времени. На практике обычно ограничивают классы грамматик таким образом, чтобы сделать процесс разбора полностью детерминированным. Оказывается, что эти ограниченные классы КС-грамматик адекватно отражают все синтаксические черты языков программирования и пригодны для описания проблемно-ориентированных языков. Требованиям детерминированности левых анализаторов наилучшим образом удовлетворяют так называемые LL(k)-грамматики, для которых левый анализатор работает детерминировано, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции. Входная цепочка считывается таким анализатором один раз слева направо и в процессе анализа не происходит возвратов к уже прочитанной части цепочки. Такие анализаторы называются однопроходными.

Для определения LL(k)-грамматики введем функцию FIRST_k(a).

Определение. Для КС-грамматики G=(N,S,P,S) определим функцию

FIRST_k(a)={xÎS^* | a Þ _l^* xB и |x|=k или a Þ^* x и |x| < k}

Иначе говоря, множество FIRST_k(a) состоит из всех терминальных префиксов длины k (или меньше, если из a выводится терминальная цепочка длины, меньшей k) терминальных цепочек, выводимых из a. ¨

Пример 5.4. Пусть грамматика имеет одно правило S®Sa|b. Определим FIRST₃(Sa).

Из Sa можно вывести следующие цепочки: ba, baa, baaa,... и т.д.

Из определения следует:

FIRST₃(Sa)={ba, baa}.

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

(1) S Þ _l^*w Aa Þ_l w ba Þ ^*w x,

2. S Þ_l ^*w Aa Þ_l w ga Þ ^*w y

связаны условием: если FIRST_k(x) = FIRST_k(y), то b=g. ¨

Говоря менее формально, G будет LL(k)-грамматикой, если для данной цепочки w AaÎ(NUE)^* и первых k символов (если они есть), выводящихся из Aa, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминальными символами.

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

Пример 5.5. Пусть G состоит из правил

1. S ® aAS,

2. S ® b,

3. A ® a,

4. A ® bSA

и дана цепочка w = abbab, которую нужно вывести. Левый вывод этой цепочки имеет вид

S₁ Þ aAS₄ Þ abSAS₂ Þ abbAS₃ Þ abbaS₂ Þ abbab

Очевидно, что данная грамматика является LL(1) - грамматикой, так как на каждом шаге вывода для каждой пары (нетерминал, терминал) можно однозначно указать какое правило нужно применить.

Эта грамматика служит примером так называемой простой LL(1)-грамматики (или разделенной грамматики).

Определение. КС-грамматика G=(N,S,Р,S) без e-правил называется простой LL(1)-грамматикой (или разделенной грамматикой), если для каждого AÎ N все его альтернативы начинаются различными терминальными символами. ¨

Условия (признаки), при которых КС-грамматика является LL(k) грамматикой, формулируются в форме следующей теоремы.

Теорема 5.1. КС-грамматика G=(N, å, Р, S) является LL(k) - грамматикой тогда и только тогда, когда для двух различных правил А ® b и А ® g из множества P пересечение

FIRST_k(ba) Ç FIRST_k(ga) = Æ

для всех таких w Aa, что S Þ^* w Aa.

Здесь a — произвольная цепочка (a Î (NUå)^*) , которая может появиться в выводах справа от А. ¨

Пример 5.6. Дана грамматика G:

S ® aAaa | bAba,

A ® b | e.

Определить, является ли G LL(2) - грамматикой .

Для первой пары правил имеем:

b = aAaa, g = bAba, а роль А играет S, следовательно, a = e и

FIRST₂(aAaa) Ç FIRST₂ (bAba) = {ab,aa} Ç {bb} = Æ.

Для второй пары имеем:

b = b, g = e, роль А играет А, следовательно, a = {aa, ba},

тогда

FIRST₂(baa) Ç FIRST₂ (aa) = Æ для a = аа,

FIRST₂(bba) Ç FIRST₂ (ba) = Æ для a = bа.

Таким образом, условия теоремы выполняются для обеих пар правил грамматики G, следовательно, это LL(2) - грамматика.

Если усилить условия теоремы, то можно сузить класс LL(k)-грамматик и получить класс сильно (или строго) LL(k)-грамматик. Для этого введем множество

FOLLOW_k(b) = {w | S Þ^*abg и w Î FIRST_k(g)}.

Другими словами, это множество терминальных цепочек длины k, которые могут встречаться в выводимых цепочках непосредственно справа от А.

Определение. КС-грамматика G, в которой для двух различных правил А ® b и А ® g

FIRST_k(bFOLLOW_k(A))Ç FIRST_k (g FOLLOW_k(A))= Æ,

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

Пример 5.7. Дана грамматика G:

S ® aAS | AbSc | e,

A ® cbA | a.

Определить: является ли G сильно LL(2)-грамматикой.

Вначале найдем:

FOLLOW₂(S) = {e, c, cc}, FOLLOW₂(A)= {e, aa, ac, cb, ab, ba, bc}

Для первой строки правил, согласно определению, имеем:

FIRST₂(aASFOLLOW₂(S))Ç FIRST₂(AbScFOLLOW₂(S))Ç

Ç FIRST₂(FOLLOW₂(S))= FIRST₂(aAS, aASc, aAScc) Ç

Ç FIRST₂(AbSc, AbScc, AbSccc) Ç FIRST₂(c, cc)=

={ac, aa} Ç {cb, ab} Ç {c, cc} = Æ;

для второй строки

FIRST₂(cbAFOLLOW₂(A))Ç FIRST₂(aFOLLOW₂(A))=

= {cb} Ç FIRST₂(a, aaa, aac, acb, aab, aba, abc} =

{cb} Ç {a, aa, ac, ab} = Æ.

Вывод - это сильно LL(2)-грамматика.

Можно показать, что грамматика G из примера 5.6 не является сильно LL(2)- грамматикой (выполните это в качестве упражнения).

В языках программирования многие синтаксические конструкции описываются LL(1)- грамматиками. Сформируем признаки LL(1)- грамматик, вытекающие из теоремы 5.1.

Грамматика G является LL(1) - грамматикой тогда и только тогда, когда для любых ее правил вида

А ® a₁| a₂| ... |a_n

выполняются условия:

1) множества FIRST₁(a₁), FIRST₁(a₂), ... , FIRST₁(a_n) попарно не пересекаются;

2) если грамматика содержит e - правила (т. е. a_i Þ ^*e), то FIRST₁(a_j) Ç FOLLOW₁(A) = Æ для 1 £ j £ n, i ¹ j.

Пример 5.8. Проверим, какая из грамматик является LL(1)-грамматикой:

1) S ® A | B,

A ® aA | a,

B ® bB | b.

Здесь нет e-правил, поэтому проверим только условие (1):

FIRST(A)Ç FIRST(B) = {a} Ç {b} = Æ – выполняется;

FIRST(aA)Ç FIRST(a) = {a} Ç {a} ¹ a – не выполняется.

Вывод - это не LL(1)-грамматика.

2) S ® AB,

A ® Ba | c,

B ® Cb | C,

C ® c | e.

Здесь имеется е - правило, поэтому начнем проверку с условия 2. Для второго правила в данной грамматике имеем:

FIRST(Ba) Ç FOLLOW(A) = {a, b, c} Ç {b, c}={b,c} – не выполняется.

Вывод - это не LL(1)-грамматика.

3) S ® aAaB | bAbB,

A ® S | cb,

B ® cB | a.

Здесь нет е-правил, проверяем условие (1):

FIRST(aAab)Ç FIRST(bAbB) = {a} Ç {b} = Æ – выполняется,

FIRST(S)Ç FIRST(cb) = {a, b} Ç {c} = Æ – выполняется,

FIRST(cB)Ç {a} = {c} Ç {a} = Æ – выполняется.

Вывод - это LL(1)-грамматика.