S->0S0

S->1S1

S->e

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

Насколько важен этот результат на практике? Оказывается, что «очевидной» грамматикой для большинства языков программирования является не LL(1). - грамматика. Однако обычно очень большое число контекстно-свободных средств языка программирования можно представить с помощью LL(1). - грамматики. Проблема заключается в том, чтобы, имея грамматику, которая не обладает признаком LL(1)., найти эквивалентную ей LL(1). -грамматику. Так как алгоритм, позволяющий определить, существует ли такая LL(1). - грамматика или нет, отсутствует значит, отсутствует и алгоритм, который мог бы определить, существуют ли соответствующие преобразования, и выполнить их. В некоторых случаях, однако, эти преобразования легко наметить. Например, преобразование для грамматики, приведенной в начале раздела 4.2. весьма просты. Многие разработчики компиляторов, обладающие достаточным опытом, не испытывают затруднений в преобразовании грамматик в ручную с целью устранения их свойств, отличных от LL(1). Тем не менее с ручным преобразованием связаны серьезные опасения. Основное из них заключается в том, что человек, выполняющий это преобразование с самыми лучшими намерениями, может случайно изменить язык, генерируемый данной грамматикой. Если в наши задачи входит создание надежных компиляторов, то нам по мере возможности желательно избегать преобразование вручную.

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

1. Устранение левой рекурсии

Грамматика, содержащая левую рекурсию, не является LL(1) -грамматикой. Рассмотрим правила

ААа( левая рекурсия в А)

Здесь а есть символ - предшественник для обоих вариантов нетерминала А. Аналогично грамматика, содержащая левый рекурсивный цикл, не может быть Ы(1)-грамматикой, например

А->ВС B->CD С->АЕ

Можно показать, что грамматику, содержащ;ую левый рекурсивный цикл, нетрудно преобразовать в грамматику, содержащую только прямую левую рекурсию, и далее, за счет введения дополнительных нетерминалов, левую рекурсию можно исключить полностью (в действительности она заменяется правой рекурсией, которая не представляет проблемы в отношении LL(1) -свойства). Из теоремы о нормальной форме Грейбаха, упоминавшейся в разд. 4.1, вытекают два следствия.

В качестве примера обратимся к грамматике с порождающими правилами

S->Aa C->Dd

А->Bb C->е

В->Сс D->Az

которая имеет левый .рекурсивный цикл, вовлекающий А, В, С, D. Чтобы заменить этот цикл на прямую левую рекурсию, мы можем действовать следующим образом. Упорядочим нетерминалы, а именно S, А, В, С, D. Рассмотрим все порождающие правила вида

Xi->Xiy

где Xi и Xj - нетерминалы, а у - строка терминальнтх и нетерминальных символов. В отношении правил, для которых j>=i, никакие действия не производятся. Однако это неравенство не выдерживается для всех правил, если есть левый рекурсивный цикл. При выбранном нами порядке мы имеем дело с единственным правилом:

D->Az

так как А предшествует D в этом упорядочении. Теперь начнем замещать А, пользуясь всеми правилами, имеющими А в левой части. В результате получаем

D->Bbz

Поскольку В предшествует D в упорядочении, процесс повторяется, что дает правило:

D->Ccbz

Затем он повторяется еще раз и дает два правила: D->ecbz

D->Ddcbz

Теперь преобразованная грамматика выглядит следующим образом:

S->Aa C->e A->Bb D->ecbz

B->Cc D->Ddcbz C->Dd

Все эти порождающие правила имеют требуемый вид; а левый рекурсивный цикл заменен прямой левой рекурсией.

Чтобы исключить прямую левую рекурсию, введем новый нетерминальный символ Z и заменим правила

D->ecbz

D->Ddcbz

D->ecbz D->ecbzZ Z->dcbz Z->dcbzZ

Заметим, что до и после преобразования D генерирует регулярное выражение

(ecbz) (dcbz)*

Обобщая, можно показать, что если нетерминал А появляется в левых частях r + s порождающих правил, r из которых используют прямую левую рекурсию, a s - нет, т. е.

A->Aa1,A->Aa2,,A->Aar

A->P1,A->P2,,A->Ps то эти правила можно заменить на следующие [27]:

A->Pi lZ->ai

J 1<i<s J 1<i<s

A->piZ Z->aiZ

Неформальное доказательство заключается в том, что до и после преобразования А генерирует регулярное выражение

(P1P2IPs)(a1a2ar) Другой метод исключения левой рекурсии (по Фостеру) приводится в

[22].

Левую рекурсию всегда можно исключить из грамматики, и нетрудно написать программу для общего случая. 2. Факторизация

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

S->aSb S->aSc S->e

можно преобразовать путем факторизации в правила

S->aSX S->e X->b X->c

и полученныой в результате грамматикой будет LL(1).

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

Рассмотрим правила

1. P->PQx 4. Q->q

2. P->Ry 5. R->sRn

3. Q->sQm 6. R->r