Преобразование грамматик в 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α 1, A → Aα 2,..., A → Aα r

A → β 1, A → β 2,..., A → β s

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

 

 

Неформальное доказательство заключается в том, что до и после преобразования A генерирует регулярное выражение (β 1 | β 2 |... | β s) (α 1 | α 2 |... | α r) *

 

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

 

17.Преобразование грамматик в 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 1

P 1 → Qmx

P 1 → Rny

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

P 1 → sQmmx

P 1 → qmx

P 1 → sRnny

P 1 → rny

 

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

P 1 → qmx

P 1 → rny

P 1 → sP 2

P 2 → Qmmx

P 2 → Rnny

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