известному методу разбора сверху вниз, применение которого позволяет избежать большинства указанных недостатков. Этот метод рассматривается в следующем разделе.

4.3. LL(1)-ГPAMMATИKИ

ЬЬ(1)-грамматика - это грамматика такого типа, на основании которой можно получить детерминированный синтаксический анализатор, работающий по принципу сверху вниз. Прежде чем определить Ы(1)-грамматику более точно, введем понятие s-грамматики.

Определение, s-грамматика представляет собой грамматику, в которой:

1) правая часть каждого порождающего правила начинается с терминала;

2) в тех случаях, когда в левой части более чем одного порождаю щего правила появляется нетерминал, соответствующие правые части начинаются с разных терминалов.

Первое условие аналогично утверждению, что грамматика находится в нормальной форме Грейбаха, только за терминалом в начале каждой правой части правила могут следовать нетерминалы и/или терминалы.

Второе условие помогает нам написать детерминированный нисходящий анализатор, так как при выводе предложения языка всегда можно сделать выбор между альтернативными порождающими правилами для самого левого нетерминала в сентенциальной форме, предварительно исследовав один следующий символ.

Грамматика с порождающими правилами S->pX X->x S->qY Y->aYd X->aXb Y->y

представляет собой s-грамматику, тогда как следующая грамматика, которая генерирует тот же язык, не является ею:

S->R Х->а S->T X->x R->pX Y->aYd T->qY Y->y

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

Рассмотрим проблему разбора строки

paaaxbbb

с помощью s-грамматики. Начав с символа S, попытаемся генерировать строку. Применим левосторонний вывод. Результат приводится ниже.

При выводе начальные терминалы в сентенциальной форме сверяются с символами в исходной строке. Стрелка показывает, до какой точки на каждом этапе был считан исходный текст и проверены начальные терминалы. Там, где допускается замена самых левых терминалов в сентенциальной форме с помощью более чем одного порождающего правила, всегда можно выбрать соответствующее порождающее правило, исследовав следующий символ во входной строке. Это связано с тем, что, поскольку мы имеем дело с s-грамматикой, правые части альтернативных порождающих правил будут начинаться с различных терминалов.

Таким образом, всегда можно написать детерминированный анализатор, осуществляющий разбор сверху вниз, для языка, генерируемого s-грамматикой. LL(1 )-грамматика является обобщением s-грамматики, и, как мы увидим далее, принцип ее обобщения все еще позволяет нам строить нисходящие детерминированные анализаторы.

Две буквы L в LL(1) означают, что строки разбираются слева направо и используются самые левые выводы, а цифра 1 - что варианты порождающих правил выбирается с помощью одного предварительно просмотренного символу. Эта терминология была введена Кнутом [36]. Свойства же LL(1)-грамматик изучались также Фостером [19]. Следует отметить, что, хотя правая часть порождающего правила и не начинается с терминала, заданный вариант какого-либо нетерминального символа может дать начало только тем строкам, которые начинаются с одного из конкретного множества терминалов. Например, на основании порождающих правил

S->RY S->TZ R->paXb T->qaYd

можно вывести, что порождающее правило S->RY желательно применять только в разборе сверху вниз (допуская, что для R нет других порождающих правил), когда предварительно просматриваемым символом является р. Аналогично порождающее правило S->TZ рекомендуется в тех случаях, когда таким символом окажется q.

Это приводит нас к идее множеств символов-предшественников, определяемых как

aeS(A)a aa

где А - нетерминальный символ, a- строка терминалов и/или нетерминалов, a S(A) обозначает множество символов-предшественников А. В грамматике с порождающими правилами

P->Ac A->aA

P->Bd B->b A->a B->Bb

a и b- символы-предшественники для P. Определим также множество символов-предшественников для строки терминалов и/или нетерминалов:

aeS(a)aaP

Здесь аи в есть строки терминалов и/или нетерминалов (Р может быть пустой строкой).

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

Следует проявлять осторожность в тех случаях, когда нетерминал в начале правой части может генерировать пустую строку. Например, в

P->AB A->e P->BG B->c A->aA B->bB

имеем

S(AB)={a,b,c} поэтому А может генерировать пустую строку и

S(BG) = {b, с} так что грамматика не будет LL(1). Рассмотрим также грамматику с порождающими правилами

T->AB Q->e

A->PQ B->bB

A->BC B->e

P->pP C->cC

P->e C->f

Q->qQ

которая дает

S(PQ)={p,q} S(BC)={b,e}

Однако так как PQ может генерировать пустую строку, следующим просматриваемым символом при применении порождающего правила A->PQ может быть b или е (вероятные символы, следующие за A), и одного следующего просматриваемого символа недостаточно, чтобы различить две альтернативные правые части для А. Последнее связано с тем, что b и е являются также символами-предшественниками для ВС.

Поэтому мы вводим направляющие символы, которые по Гриффитсу [22] определяются так: если А - нетерминал, то его направляющими символами будут S(A) + (все символы, следующие за А, если А может генерировать пустую строку).

В более общем случае для заданного варианта а нетерминала Р (P->a) имеем

DS (P,а) = (аае S(а) или (ае и a eF(P))} где F(P) есть множество символов, которые могут следовать за Р. Так, в приведенном ранее примере направляющие символы - это символы

DS (A.PQ)={p,q,b,e} DS (А.ВС) = {b,е}

Поскольку указанные множества пересекаются, данная грамматика не может служить основой для детерминированного нисходящего анализатора, использующего один предварительно просматриваемый символ для различения альтернативных правых частей.

Теперь мы готовы определить LL( 1) -грамматику. Грамматику называют Ы(1)-грамматикой, если для каждого нетерминала, появляющегося в левой части более одного порождающего правила, множества направляющих символов, соответствующих правым частям альтернативных порождающих правил, - непересекающиеся. Все LL(l)-rpaмматики можно разбирать детерминированно сверху вниз.

Существует алгоритм, который позволяет выяснить, представляет ли собой заданная грамматика Ы(1)-грамматику. Опишем этот алгоритм.