LL(k) ЯЗЫКИ И ГРАММАТИКИ

Грамматики, для которых левый разбор работает детерминированно, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции, принято называть LL(k) -грамматиками. (Первая буква L (Left - левый) относится к просмотру входной цепочки слева направо, вторая - к используемому левому выводу.)

Дадим вначале неформальное определение LL(k) грамматики. Напомним, что в левостороннем анализаторе дерево вывода цепочки abg строится по заданной грамматике, начиная от корня (аксиомы грамматики), сверху вниз. Пусть на каком-то шаге анализа уже построено частичное дерево вывода с кроной aAj (см. рис. 5.1). Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A®b. Если для однозначного выбора этого правила окажется достаточно знать только a и первые k символов цепочки bg, то заданная грамматика является LL(k) –грамматикой.

Дадим более строгое определение. Определим два множества цепочек:

FIRST _k (a) - множество терминальных цепочек, выводимых из a, укороченных до k символов.

FOLLOW _k (A) - множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A в выводимых цепочках.

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

(1) S Þ ^* wAa Þ wba Þ ^* wj

и

(2) S Þ ^* wAa Þ wga Þ ^* wy,

для которых FIRST _k (j) = FIRST _k (y), следует, что b=g.

Пример 5.1. Пусть грамматика G₁ состоит из правил S ® aASôb, A ® aôbSA. Интуитивно G₁ является LL(1) грамматикой, так как если дан самый левый нетерминал C в левовыводимой цепочке и следующий входной символ с, то существует не более одного правила, применимого к C и приводящего к терминальной цепочке, начинающейся символом c. Переходя к определению LL(1) грамматики мы видим, что если
S Þ ^* wSa Þ wba Þ ^* wj и S Þ ^* wSa Þ wga Þ ^* wy и цепочки j и y начинаются символом a, то в выводе участвует правило S ® aAS и b = g = aAS. Альтернатива
S ® b здесь невозможна. С другой стороны, если j и y начинаются с b, то должно применяться правило S ® b и b = g = b. Заметим, что случай b = g = e здесь невозможен, так как из S не выводится пустая цепочка e.

Когда рассматриваются два других вывода с нетерминалом A, то рассуждение аналогично. Ÿ

Пример 5.2. Рассмотрим более сложный случай - грамматику G₂, определяемую правилами S ® eôabA, A ® Saaôb. Это не LL(1) грамматика, так как, пройдя часть левого вывода S Þ abA Þ abSaa для входных цепочек abaa или ababbaa и, имея на входе символ a, не ясно какое правило надо применить: S ® e или S ® abA. Покажем, что G₂ – это LL(2) -грамматика.

Допустим, что S Þ ^* wSa Þ wba Þ ^* wj и S Þ ^* wSa Þ wga Þ ^* wy и первые два символа цепочки j (если они есть)совпадают с первыми двумя символами цепочки y. Нетрудно видеть, что здесь нет иных возможностей, кроме j = y = e, j и y начинается с aa, j и y начинается с ab. В первых двух случаях в обоих выводах применяется правило S ® e и b = g = e. В третьем случае должно применяться S ® abA и
b = g = abA. Ÿ

Пример 5.3. Рассмотрим грамматику G₃ = ({S, A, B}, {0, 1, a, b}, P₃, S), где P₃ состоит из правил:

S ® AôB

A ® aAbô0

B ® aBbbô1

Здесь L(G₃) = {aⁿ0bⁿôn ³ 0}È{ aⁿ1b^{2 n}ôn ³ 0}. G₃ не является LL(k) -грамматика ни для какого k. Интуитивно, если мы начинаем с чтения достаточно длиной цепочки, начинающейся с символов a, то не знаем, какое из правил S ® A или S ® B было применено первым, пока не встретим 0 или 1. Обращаясь к точному определению LL(k) -грамматики, положим w = a = e, b = A, g = B, j = a^k0b^k и y = a^k1b^{2 k}. Тогда выводы

S Þ⁰ S Þ A Þ^*a^k0b^k

S Þ⁰ S Þ B Þ^*a^k1b^{2 k}

соответствуют выводам (1) и (2) определения. Первые k символов цепочек j и y совпадают, однако заключение b = g ложно. Так как k здесь выбрано произвольно, то G₃ не является LL -грамматикой. Можно показать, что для языка L(G₃) вообще не существует LL(k) -грамматики. Ÿ

Из определения LL(k) грамматики может показаться, что для определения нужного правила надо помнить уже всю проанализированную часть входной цепочки w. Но это не так. Рассмотрим теорему, очень важную для понимания LL(k) -грамматик, которая тривиально доказывается исходя из определения LL(k) -грамматики.

Теорема 5.1. КС-грамматика G = (N, S, P, S) является LL(k) -грамматикой тогда и только тогда, когда для двух различных правил A ® b и A ® g из P пересечение FIRST_k(ba) Ç FIRST_k(ga) пусто при всех таких wAa, что S Þ^*wAa. €

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

Пример 5.4. Пусть грамматика G определяется двумя правилами S ® Saôb. Возьмем, как и в теореме 5.1, вывод S Þ ⁱ Sa ⁱ, где i ³ 0, A = S, a = e, b = Sa и g = b. Тогда для i ³ k

FIRST _k (Saa ⁱ ) Ç FIRST_k(ba ⁱ ) = ba ^k-1

Таким образом, G не может быть LL(k) -грамматикой ни для какого k. €

Еще одно следствие теоремы 5.1 состоит в том, что если КС-грамматика G не содержит аннулирующих правил, то она будет LL(1) -грамматикой только в том случае, когда для всех AÎN каждое множество A -правил A ® a₁ôa₂ô¼ôa _n из P таково, что FIRST₁(a₁), FIRST₁(a₂), ¼, FIRST₁(a_n) попарно не пересекаются. (Отсутствие
e -пра­вил здесь существенно).

Введенная выше функция FOLLOW _k (A) как раз и нужна для грамматик с аннулирующими правилами. Для LL(1) -грамматик справедливо следующее утверждение.

Теорема 5.2. КС-грамматика G = (N, S, P, S) является LL(1) -грамматикой тогда и только тогда, когда для двух различных правил A ® b и A ® g пересечение FIRST₁(bFOLLOW ₁ (A)) Ç FIRST₁(gFOLLOW ₁ (A)) пусто при всех AÎN. €

Другими словами G является LL(1) -грамматикой, если для каждого множества A -правил A ® a₁ôa₂ô¼ôa _n

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

(2) если a _i Þ e, то FIRST₁(a _j) Ç FOLLOW ₁ (A) = 0 для 1 £ j £ n, i ¹ j.

Таким образом, в случае k = 1 для однозначного выбора правила для нетерминала А, достаточно знать только нетерминал A и а – первый символ нерассмотренной части входной цепочки j:

следует выбрать правило A ® b, если а входит в FIRST₁(b)

следует выбрать правило A ® e, если а входит в FOLLOW₁(A).

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

Пример 5.5. Пусть G – леворекурсивная грамматика S ® Saôb, которая, как видно из примера 5.4 не является LL -грамматикой. Устраняя левую рекурсию, заменим два эти правила на следующие три:

S ® bS¢

S¢ ® aS¢ôe

получив при этом эквивалентную грамматику G¢. С помощью теоремы 5.2 легко показать, что G¢ – LL(1) -грамматика. €

Пример 5.6. Рассмотрим LL(2) -грамматику G – с двумя правилами S ® aSôa. Проведем левую факторизацию, “вынеся влево за скобку” символ a и, записав правила в виде S ® a(Sôe). Иными словами, мы считаем, что операция конкатенации дистрибутивна относительно операции выбора альтернативы. Заменив эти правила на

S ® aA

A ® Sôe

получим тем самым эквивалентную LL(1) -грамматику. €

Поиск по сайту: