Контекстовільні мови. Дерева розбору. Неоднозначні граматики, страница 3

            Ліворекурсивна пара продукцій A→Aα | β може бути замінена неліворекурсивними продукціями:

            A → βA' ,

            A'→ αA'| ε

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

            Розглянемо таку граматику для арифметичних виразів:

            E→E+T | T ,

            F→T*F | F ,

            F→(E) | id .

            Після видалення рекурсії з продукцій для Eі T одержимо:

            E→TE' ,        E’→+TE' | ε ,

            T→ FT ' ,       T’→*FT ' | ε ,(3.1)

            F→(E) | id .

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

            A → Aα₁ | Aα₂ | ... | Aα_m | β₁ | β ₂ | .... | β _n ,

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

            A → β₁A' | β ₂A' | .... | β _n A',

            A'→ α₁A' | α₂A' | .... | α_mA' | ε .

            Нетермінал A породжує ті самі рядки, що і раніше, але тепер немає лівої  рекурсії. За  допомогою цієї  процедури видаляються  всі безпосередні  ліві   рекурсії, але не  видаляється  ліва рекурсія, що включає  два або  більше кроків породження. Розглянемо, наприклад, граматику:

            S→ Aa | b ;

            A→ Ac | Sd |  ε .

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

            Наведений  нижче алгоритм дозволяє  видалити   всі  ліві   рекурсії  з граматики.

            Алгоритм 3.1  Видалення лівої рекурсії

            Крок 1  Упорядковуємо нетермінали в довільному порядку  A₁, A₂, …, A_n.

            Крок 2

for і:=1 to n do begin

      for j:=1 to і-1 do begin

      Замінити всі продукції вигляду A_i → A_jγ

            продукціями A_i → δ₁γ | δ₂γ | ... | δ_kγ,

            де A_j → δ₁ | δ₂ | ... | δ_k – всі поточні A_j-продукції

      end

       Видалити безпосередню ліву рекурсію серед

      A_i- продукцій

end

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

              Розглянутий алгоритм гарантовано працює з граматиками, які не мають циклів (породжень типу AA) і ε-продукцій (продукцій типу A → ε). Як цикли, так   і   ε-продукції можуть бути вилучені попередньо.

3.4 Ліва факторизація

            Ліва факторизація являє собою перетворення граматики у форму, придатну для предиктивного аналізу.

            Основна ідея лівої факторизації полягає у тому, що, коли незрозуміло, яку з двох альтернативних продукцій  потрібно  використовувати  для  розгортання нетермінала A,  потрібно переробити A-продукції так, щоб відкласти рішення доти,  поки із вхідного потоку не буде прочитано достатньо символів для правильного вибору.

            Наприклад, якщо є дві продукції

            stmt → if expr then stmt else stmt

                        | if expr then stmt ,

то, після знаходження у вхідному потоці if, ми не можемо відразу вибрати ні одну з них. У загальному випадку, якщо  A→αβ₁ | αβ₂ – дві A-продукції  і  вхідний  потік починається з непорожнього рядка, виведеного з α, ми  не можемо сказати, буде використовуватися перша чи друга продукція. Однак можна відкласти рішення, розширивши   A до αA'. У цьому випадку, після розгляду вхідного потоку,  що виводиться з α, ми працюємо з A', розширюючи його до β₁ або до β₂. Таким чином, лівофакторизовані продукції наберуть вигляду: