Ll(k) - грамматики
Выше анализаторы были определены как недетерминированные МП-преобразователи. Попытка их реализации для широкого класса КС-грамматик приводит к так называемым алгоритмам с “возвратами” которые требуют слишком больших затрат времени. На практике обычно ограничивают классы грамматик таким образом, чтобы сделать процесс разбора полностью детерминированным. Оказывается, что эти ограниченные классы КС-грамматик адекватно отражают все синтаксические черты языков программирования и пригодны для описания проблемно-ориентированных языков. Требованиям детерминированности левых анализаторов наилучшим образом удовлетворяют так называемые LL(k)-грамматики, для которых левый анализатор работает детерминировано, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции. Входная цепочка считывается таким анализатором один раз слева направо и в процессе анализа не происходит возвратов к уже прочитанной части цепочки. Такие анализаторы называются однопроходными.
Для определения LL(k)-грамматики введем функцию FIRSTk().
Определение. Для КС-грамматики G=(N,,P,S) определим функцию
FIRSTk()={x* | l* xB и |x|=k или * x и |x| < k}
Иначе говоря, множество FIRSTk() состоит из всех терминальных префиксов длины k (или меньше, если из выводится терминальная цепочка длины, меньшей k) терминальных цепочек, выводимых из .
Пример Пусть грамматика имеет одно правило SSa|b. Определим FIRST3(Sa).
Из Sa можно вывести следующие цепочки: ba, baa, baaa,... и т.д.
Из определения следует:
FIRST3(Sa)={ba, baa}.
Определение. КС-грамматика G=(N, , Р, S) называется LL(k)-грамматикой для некоторого фиксированного k, если любые два левых вывода
(1) S l* A l * x,
S l * A l * y
связаны условием: если FIRSTk(x) = FIRSTk(y), то =.
Говоря менее формально, G будет LL(k)-грамматикой, если для данной цепочки A(NUE)* и первых k символов (если они есть), выводящихся из A, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с и продолжающейся упомянутыми k терминальными символами.
Грамматика называется LL-грамматикой, если она LL(k)-грамматика для некоторого k.
Пример Пусть G состоит из правил
S aAS,
S b,
A a,
A bSA
и дана цепочка = abbab, которую нужно вывести. Левый вывод этой цепочки имеет вид
S1 aAS4 abSAS2 abbAS3 abbaS2 abbab
Очевидно, что данная грамматика является LL(1) - грамматикой, так как на каждом шаге вывода для каждой пары (нетерминал, терминал) можно однозначно указать какое правило нужно применить.
Эта грамматика служит примером так называемой простой LL(1)-грамматики (или разделенной грамматики).
Определение. КС-грамматика G=(N,,Р,S) без e-правил называется простой LL(1)-грамматикой (или разделенной грамматикой), если для каждого A N все его альтернативы начинаются различными терминальными символами.
Условия (признаки), при которых КС-грамматика является LL(k) грамматикой, формулируются в форме следующей теоремы.
Теорема 5.1. КС-грамматика G=(N, , Р, S) является LL(k) - грамматикой тогда и только тогда, когда для двух различных правил А и А из множества P пересечение
FIRSTk() FIRSTk() =
для всех таких A, что S * A.
Здесь — произвольная цепочка ( (NU)*) , которая может появиться в выводах справа от А.
Пример . Дана грамматика G:
S aAaa | bAba,
A b | e.
Определить, является ли G LL(2) - грамматикой .
Для первой пары правил имеем:
= aAaa, = bAba, а роль А играет S, следовательно, = e и
FIRST2(aAaa) FIRST2 (bAba) = {ab,aa} {bb} = .
Для второй пары имеем:
= b, = e, роль А играет А, следовательно, = {aa, ba},
тогда
FIRST2(baa) FIRST2 (aa) = для = аа,
FIRST2(bba) FIRST2 (ba) = для = bа.
Таким образом, условия теоремы выполняются для обеих пар правил грамматики G, следовательно, это LL(2) - грамматика.
Если усилить условия теоремы, то можно сузить класс LL(k)-грамматик и получить класс сильно (или строго) LL(k)-грамматик. Для этого введем множество
FOLLOWk() = { | S * и FIRSTk()}.
Другими словами, это множество терминальных цепочек длины k, которые могут встречаться в выводимых цепочках непосредственно справа от А.
Определение. КС-грамматика G, в которой для двух различных правил А и А
FIRSTk(FOLLOWk(A)) FIRSTk ( FOLLOWk(A))= ,
называется сильно (строго) LL(k)-грамматикой.
Пример Дана грамматика G:
S aAS | AbSc | e,
A cbA | a.
Определить: является ли G сильно LL(2)-грамматикой.
Вначале найдем:
FOLLOW2(S) = {e, c, cc}, FOLLOW2(A)= {e, aa, ac, cb, ab, ba, bc}
Для первой строки правил, согласно определению, имеем:
FIRST2(aASFOLLOW2(S)) FIRST2(AbScFOLLOW2(S))
FIRST2(FOLLOW2(S))= FIRST2(aAS, aASc, aAScc)
FIRST2(AbSc, AbScc, AbSccc) FIRST2(c, cc)=
={ac, aa} {cb, ab} {c, cc} = ;
для второй строки
FIRST2(cbAFOLLOW2(A)) FIRST2(aFOLLOW2(A))=
= {cb} FIRST2(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) - грамматикой тогда и только тогда, когда для любых ее правил вида
А 1| 2| ... |n
выполняются условия:
1) множества FIRST1(1), FIRST1(2), ... , FIRST1(n) попарно не пересекаются;
2) если грамматика содержит e - правила (т. е. i *e), то FIRST1(j) FOLLOW1(A) = для 1 j n, i j.
Пример . Проверим, какая из грамматик является 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)-грамматика.