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

Ліва факторизація (left factoring) являє собою перетворення граматики, що придатна для предиктивного аналізу. Основна ідея лівої факторизації полягає в тім, що коли не ясно, яка із двох або більше альтернативних продукцій повинна використатися для нетермінала А, А-продукції можна переписати так, щоб відкласти ухвалення рішення доти, поки із вхідного потоку не буде прочитано достатньо символів для правильного вибору.

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

stmt ::= if expr then stmt else stmt

| if expr then stmt

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

А ::= α А'

А' ::= β1 | β2

Алгоритм 4.2. Ліва факторизація граматики

Вхід. Граматика G.

Вихід. Еквівалентна лівофакторизована граматика.

Метод. Для кожного нетермінала А знаходимо найдовший префікс α, загальний для двох або більшого числа альтернатив. Якщо α≠ε, тобто є нетривіальний загальний префікс, замінимо усі продукції А ::= αβ1|αβ2...|αβn|γ, де γ представляє усі альтернативи, що не починаються з α, продукціями

А ::= αА'| γ

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

Tут А' – новий нетермінал. Виконуємо це перетворення до тих пір, поки ніякі дві альтернативи не будуть мати загальний префікс.

Приклад 4.10. Наступна граматика абстрагує проблему "else, що кочує":

S ::= iEtS | EtSeS| a

Е ::= b (4.13)

Тут i, t й е означають if, then й else, Е й S відповідають expr й stmt. Будучи лівофакторизованою, ця граматика приймає наступний вид:

S ::= iEtSS' | a

S' ::= еS| ε

Е ::= b (4.14)

Таким чином, при одержанні на вході i ми використаємо продукцію iEtSS' і чекаємо, поки iEtS не буде переглянута, щоб потім вирішити, чи розширювати S' до εS або ε. Звичайно, і граматика (4.13), і граматика (4.14) неоднозначні, і при вхідному символі ε неясно, яка з альтернатив для S' повинна бути обрана, але існують шляхи рішення цієї дилеми.

36