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

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

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

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

FIRST_k()={x^* |   _l^* xB и |x|=k или  ^* x и |x| < k}

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

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

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

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

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

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

(1) S  _l^* A _l    ^* x,

2. S _l ^* A _l    ^* y

связаны условием: если FIRST_k(x) = FIRST_k(y), то =. 

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

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

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

1. S  aAS,

2. S  b,

3. A  a,

4. A  bSA

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

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

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

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

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

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

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

FIRST_k()  FIRST_k() = 

для всех таких  A, что S ^*  A.

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

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

S  aAaa | bAba,

A  b | e.

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

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

 = aAaa,  = bAba, а роль А играет S, следовательно,  = e и

FIRST₂(aAaa)  FIRST₂ (bAba) = {ab,aa}  {bb} = .

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

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

тогда

FIRST₂(baa)  FIRST₂ (aa) =  для  = аа,

FIRST₂(bba)  FIRST₂ (ba) =  для  = bа.

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

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

FOLLOW_k() = { | S ^* и   FIRST_k()}.

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

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

FIRST_k(FOLLOW_k(A)) FIRST_k ( FOLLOW_k(A))= ,

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

Пример Дана грамматика 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) - грамматикой тогда и только тогда, когда для любых ее правил вида

А  ₁| ₂| ... |_n

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

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

2) если грамматика содержит e - правила (т. е. _i  ^*e), то FIRST₁(_j)  FOLLOW₁(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)-грамматика.