4.4. Левая рекурсия и ее устранение

Правило порождения вида A → Aγ в КС-грамматике называется леворекурсивным, и тогда говорят, что в грамматике имеется левая рекурсия. В дальнейшем будем считать, что грамматика приведенная, т.е. в ней обнаружены и из нее удалены все бесполезные нетерминалы.

При функционировании МПА, построенного по КС-грамматике с левой рекурсией, когда имеется правило порождения вида A → Aγ, выполнение соответствующего правила перехода (λ, A, q₀) → (λ, Aγ^–1, q₀) будет повторяться бесконечно. Для НМПА это не страшно, так как другие варианты выполнения НМПА все равно найдут (если оно существует) левое каноническое порождение анализируемой цепочки символов. Если же требуется построить ДМПА, который может проверять только единственный вариант левого канонического порождения, такая ситуация недопустима. Поэтому рассмотрим устранение левой рекурсии без изменения порождаемого грамматикой языка.

Пусть имеется правило вида A → Aγ. Но тогда должно быть также правило вида A → α, где первый символ цепочки α не совпадает с A, так как в противном случае символ A – бесполезный. Цепочки символов, порождаемые этими двумя правилами следующие: α, αγ, αγγ и т.д. Эти же цепочки можно получить другими правилами: A → αA’, A’ → γA’| λ, где A’ – новый нетерминал.

Рассмотренный случай называют непосредственной рекурсией, ее легко обнаружить. Более сложен случай косвенной рекурсии, когда имеется совокупность правил вида A → B₁γ₁, B₁ → B₂γ₂, …, B_n → Aγ_n. Тогда вначале косвенную рекурсию нужно свести к непосредственной, сделав следующую замену этой группы правил на правило: A → Aγ_n … γ₂γ₁. При этом надо учесть и другие совокупности правил, аналогичные рассмотренным, в которые входят какие-либо из нетерминалов B₁, …, B_n.

Пример 6. Пусть задана грамматика простых арифметических выражений (S – начальный нетерминал):

S → S + T | T

T → T * F | F

F → (S) | a

Устранив левую рекурсию рассмотренным способом, получим правила:

S → TU

U → + TU | λ

T → FV

V → * FV | λ

F → (S) | a

Конец примера.

4.5. Преобразование кс-грамматики к обобщенной нормальной форме Грейбах

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

Преобразование начинается с нахождения тех порождающих правил, правые части которых начинаются с терминалов или пусты. Эти порождающие правила остаются без изменения. Пусть имеется правило вида A → Bα, тогда нетерминал B надо заменить совокупностью правых частей правил B → γ₁ | … | γ_n. В результате получатся правила:

A → γ₁α | … | γ_nα.

Если какие-либо из цепочек γ₁α, …, γ_nα начинаются с нетерминального символа, то аналогичную замену правых частей правил для нетерминала A следует продолжать. Так как леворекурсивных правил в грамматике нет, то такой процесс обязательно закончится, и в преобразованных правилах правые части будут начинаться с терминальных символов.

После этого надо отыскать оставшиеся правила вида A’ → B’α’, и продолжить процесс замен. Когда все подобные замены будут сделаны, все правые части правил будут начинаться с терминальных символов или будут пустыми.

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

Пример 7. Пусть задана грамматика простых арифметических выражений с устраненной левой рекурсией:

S → TU

U → + TU | λ

T → FV

V → * FV | λ

F → (S) | a

После ее преобразования к обобщенной нормальной форме Грейбах получим:

S → (S)VU | aVU

U → + TU | λ

T → (S)V | aV

V → * FV | λ

F → (S) | a

Конец примера.