4.5.2 Усунення лівої рекурсії

Граматика є ліворекурсивною, якщо в ній є нетермінал А, такий, що існує породження А →⁺ Аα для деякого рядка α. Методи спадного розбору не в змозі працювати з ліворекурсивными граматиками, тому потрібне перетворення граматики, що усунуло б з неї ліву рекурсію. Наприклад, ліворекурсивна пара продукцій

A ::= Aα|β

може бути замінена не ліворекурсивними продукціями

А ::= βА'

А' ::= αА'|ε

без зміни множини рядків, породжуваних з А. Цього правила досить для багатьох граматик.

Приклад 4.7. Розглянемо наступну граматику для арифметичних виразів.

Е ::= Е+Т | Т

Т ::= T*F | F (4.I0)

F ::= (Е) | id

Усунувши безпосередню ліву рекурсію (продукції виду А ::= Аα) із продукцій для Е і Т, ми одержимо

Е ::= ТЕ'

Е' ::= +TЕ' | ε

T ::= FТ' (4.I1)

Т' ::= * FТ' | ε

F ::= (Е) | id

Приклад 4.8. Майже у всіх мовах програмування використовуються переліки (списки, послідовності, тощо) якіхось конструктівмови, наприклад: перелік полів після ключового слова select в мові SQL, список параметрів функії в мові Pascal, тощо. Дамо узагальнену назву таким перелікам item_list і нехай роздільником між цими конструктами є кома, хоча може бути й інший символ. Розглянемо наступну ліворекурсивну граматику для такого переліка:

<item_list> ::= <item_list> , <item> ǀ <item>

Усунувши безпосередню ліву рекурсію (продукції виду А ::= Аα) із продукцій для <item_list>, ми одержимо:

<item_list> ::= <item> <new_item_list>

<new_item_list>> ::= , <item> <new_item_list> ǀ ɛ

Як бачимо, до нової граматики додаться новий нетермінал, і вона стає праворекурсивною по відношенню до нового нетермінала.

Не важливо, яке загальна кількість А-продукцій. Ми можемо усунути безпосередню ліву рекурсію з них за допомогою наступної технології. Спочатку групуємо А-продукції

А ::= Аα1| Аα2|…|Аαm|β1| β2|…|βn

де βi не починаються з А. Потім замінимо ці А-продукції на

А ::= β1 А' | β2 А' |…|βn А'

А' ::= α₁ А'| α₂ А'|…|α_m А'|ε

Нетермінал А породжує ті ж рядки, що й раніше, але без лівої рекурсії. Ця процедура усуває всі безпосередні ліві рекурсії із продукцій для А и А' (за умови, що жоден рядок α_i не є ε), але не усуває ліву рекурсію, викликану двома або більше кроками породження. Розглянемо, наприклад, граматику

S ::= Аа|b

А ::= Ac|Sd| ε (4.12)

Нетермінал S ліворекурсивен, оскільки S → Аа → Sda, але ця рекурсія не є безпосередньою.

Алгоритм 4.1, наведений нижче, видаляє із граматики ліву рекурсію. Він гарантированно працює із граматиками, що не мають циклів (породжень типу А →⁺ А) і ε-продукцій (продукцій типу А ::= ε). Із граматики можуть бути також вилучені й цикли, і ε-продукції.

Алгоритм 4.1. Усунення лівої рекурсії

Вхід. Граматика G без циклів й ε-продукцій.

Вихід. Еквівалентна граматика без лівої рекурсії.

Метод. Застосувати алгоритм, наведений на рис. 4.15. Зверніть увагу, що підсумкова граматика без лівих рекурсій може мати ε-продукції.

1. Розташувати нетермінали в деякому порядку A_1, А₂,...,An

2. for i:=l to n do begin

for j:=l to і-1 do begin

Замінити кожну продукцію виду A_i ::= A_jγ продукціями А_i ::= δ1γ| δ2γ|… |δkγ ,

де А_j δ::= δ1| δ2|… |δk - всі альтернативи поточної А_j-продукції

end

Усунути безпосередню ліву рекурсію серед A_i-продукцій

end

Рис. 4.15. Алгоритм усунення лівої рекурсії із граматики

Обґрунтування працездатності наведеного на рис. 4.9 алгоритму засноване на тому, що після (i-1)-й ітерації зовнішнього циклу for кроку (2) у будь-якій продукції виду A_k ::= A_iα, k<i, повинне бути l>к. У результаті при наступній ітерації внутрішнього циклу (по j) росте нижня межа m всіх продукцій виду А_i ::= А_mα доти, поки не буде досягнуте m ≥ i. Потім з A-продукцій усувається безпосередня ліва рекурсія, внаслідок чого досягається m >i.

Приклад 4.9. Застосуємо описану процедуру до граматики (4.12). Технічно через наявність ε-продукції алгоритм може не працювати, але в цьому випадку продукція А_i ::= ε не заважає роботі.

Ми розташовуємо нетермінал у порядку S, А. Безпосередньої лівої рекурсії серед S-продукцій немає, так що в процесі роботи кроку (2) при i=1 нічого не відбувається. Для i=2 ми підставляємо S-продукцію в А ::= Sd для одержання наступної А-продукції: A ::= Ac | Aad | bd | ε .

Усунення безпосередньої лівої рекурсії дає граматику

S ::= Аа | b

А ::= bd A' | A'

A' ::= cA' | ad A' | ε