Определение LL(1)-грамматики.

 

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

Преобразование грамматик в LL(1)-форму.

 

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

· устранение левой рекурсии

· факторизация

 

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

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

A ® Aa (левая рекурсия в A)

A® a

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

A® BC

B ® CD

C ® AE

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

S ® Aa

A ® Bb

B ® Cc

C ® Dd

C ® e

D ® Az

которая имеет левый рекурсивный цикл, вовлекающий A, B, C, D. Чтобы заменить этот цикл прямой левой рекурсией, упорядочим нетерминалы следующим образом: S, A, B, C, D.

Рассмотрим все порождающие правила вида

Xi ® Xj γ,

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

D ® Az

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

D ® Bbz

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

D ® Ccbz

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

D ® ecbz

D ® Ddcbz

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

S ® Aa

A ® Bb

B ® Cc

C ® Dd

C ® e

D ® Ddcbz

D ® ecbz

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

D ® ecbz

D® Ddcbz

на

D ® ecbz

D ® ecbzZ

Z ® dcbz

Z ® dcbzZ

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

(ecbz) (dcbz)*

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

A ® Aα ₁, A ® Aα ₂,..., A ® Aα _r

A ® β ₁, A ® β ₂,..., A ® β _s

то эти правила можно заменить на следующие:

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

(β ₁ | β ₂ |... | β s) (α ₁ | α ₂ |... | α _r) *

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

Факторизация.

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

P ® begin D; С end

D ® d, D

D ® d

С ® s; С

С ® s

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

P ® begin D; С end

D ® d X (вводим дополнительный нетерминал X)

X ®, D (по 1-му правилу для D исходной грамматики за d следует, D)

X ® ε (по 2-му правилу для D исходной грамматики за d ничего нет (пустая строка))

С ® s Y (вводим дополнительный нетерминал Y)

Y ®; С (по 1-му правилу для C исходной грамматики за s следует; C)

Y ® ε (по 2-му правилу для C исходной грамматики за s ничего нет (пустая строка))

Аналогичным образом, порождающие правила

S ® aSb

S ® aSc

S ® ε

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

S ® aSX

S ® ε

X ® b

X ® c

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

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

1. P ® Qx

2. P ® Ry

3. Q ® sQm

4. Q ® q

5. R ® sRn

6. R ® r

Оба множества направляющих символов для двух вариантов P содержат s, и, пытаясь "вынести s за скобки", мы замещаем Q и R в правых частях правил 1 и 2:

P ® sQmx

P ® sRny

P ® qx

P ® ry

Эти правила можно заменить следующими:

P ® qx

P ® ry

P ® sP ₁

P ₁ ® Qmx

P ₁ ® Rny

Правила для P₁ аналогичны первоначальным правилам для P и имеют пересекающиеся множества направляющих символов. Мы можем преобразовать эти правила так же, как и правила для P:

P ₁ ® sQmmx

P ₁ ® qmx

P ₁ ® sRnny

P ₁ ® rny

Факторизуя, получаем

P ₁ ® qmx

P ₁ ® rny

P ₁ ® sP ₂

P ₂ ® Qmmx

P ₂ ® Rnny

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