5. Однопроходный синтаксический анализ без возвратов

Как уже отмечалось, рассмотренные выше недетерминированные, переборные алгоритмы синтаксического анализа с возвратами способны анализировать практически все КС-языки, но их эффективность оставляет желать много лучшего. В общем случае время работы таких алгоритмов экспоненциально зависит от длины анализируемой цепочки. В этой главе мы рассмотрим классы КС-грамматик, для которых можно построить эффективные анализаторы, тратящие на обработку цепочек линейное время. За эту эффективность приходится платить тем, что такие анализаторы не могут обрабатывать все КС-языки без исключения. Однако эти ограниченные классы грамматик и языков адекватно отражают синтаксические черты всех известных языков программирования.

Излагаемые в этой главе алгоритмы разбора характеризуются тем, что входная цепочка считывается один раз слева направо и процесс разбора полностью детерминирован. Другими словами класс КС-грамматик здесь ограничивается так, чтобы для них можно было построить детерминированный левый или правый анализатор.

5.1. Ll(k) языки и грамматики

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

Дадим вначале неформальное определение LL(k) грамматики. Напомним, что в левостороннем анализаторе дерево вывода цепочки  строится по заданной грамматике, начиная от корня (аксиомы грамматики), сверху вниз. Пусть на каком-то шаге анализа уже построено частичное дерево вывода с кроной A (см. рис. 5.1). Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A. Если для однозначного выбора этого правила окажется достаточно знать только  и первые k символов цепочки , то заданная грамматика является LL(k)–грамматикой.

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

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

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

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

1. S  ^ A    ^ 

и

2. S  ^ A    ^ ,

для которых FIRST _k ()  FIRST _k (), следует, что .

Пример 5.1. Пусть грамматика G₁ состоит из правил S  aASb , A  abSA . Интуитивно G₁ является LL(1) грамматикой, так как если дан самый левый нетерминал C в левовыводимой цепочке и следующий входной символ с, то существует не более одного правила, применимого к C и приводящего к терминальной цепочке, начинающейся символом c. Переходя к определению LL(1) грамматики мы видим, что если S  ^ S    ^  и S  ^ S    ^  и цепочки  и  начинаются символом a, то в выводе участвует правило S  aAS и  =  = aAS. Альтернатива S  b здесь невозможна. С другой стороны, если  и  начинаются с b, то должно применяться правило S  b и  =  = b. Заметим, что случай  =  =  здесь невозможен, так как из S не выводится пустая цепочка .

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

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

Допустим, что S  ^ S    ^  и S  ^ S    ^  и первые два символа цепочки  (если они есть) совпадают с первыми двумя символами цепочки . Нетрудно видеть, что здесь нет иных возможностей, кроме  =  = ,  и  начинается с aa,  и  начинается с ab. В первых двух случаях в обоих выводах применяется правило S   и  =  = . В третьем случае должно применяться S  abA и  =  = 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)-грамматики, положим     ,   A,   B,   a^k0b^k и   a^k1b^{2 k}. Тогда выводы

S ⁰ S  A ^a^k0b^k

S ⁰ S  B ^a^k1b^{2 k}

соответствуют выводам (1) и (2) определения. Первые k символов цепочек  и  совпадают, однако заключение    ложно. Так как k здесь выбрано произвольно, то G₃ не является LL-грамматикой. Можно показать, что для языка L(G₃) вообще не существует LL(k)-грамматики. 

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

Теорема 5.1. КС-грамматика G = (N, , P, S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил A   и A   из P пересечение FIRST_k()  FIRST_k() пусто при всех таких A, что S ^A. 

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

Пример 5.4. Пусть грамматика G определяется двумя правилами S  Sab. Возьмем, как и в теореме 5.1, вывод S  ⁱ Sa ⁱ, где i  0, A = S,  = ,  = Sa и  = 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  ₁₂ _n из P таково, что FIRST₁(₁), FIRST₁(₂), , FIRST₁(_n) попарно не пересекаются. (Отсутствие -пра­вил здесь существенно).

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

Теорема 5.2. КС-грамматика G = (N, , P, S) является LL(1)-грамматикой тогда и только тогда, когда для двух различных правил A   и A   пересечение FIRST₁(FOLLOW ₁ (A))  FIRST₁(FOLLOW ₁ (A)) пусто при всех AN. 

Другими словами G является LL(1)-грамматикой, если для каждого множества A-правил A  ₁₂ _n

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

(2) если  _i  , то FIRST₁( _j)  FOLLOW ₁ (A) = 0 для 1  j  n, i  j.

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

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

следует выбрать правило A  , если а входит в 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

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

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

S  aA

A  S

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