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

Правило порождения вида 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

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

Дата добавления: 2015-07-26; просмотров: 223; Нарушение авторских прав

Мы поможем в написании ваших работ!