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

Oсновная идея левой факторизации в том, что в том случае, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно изменить A-правила так, чтобы отложить решение до тех пор, пока не будет достаточно информации для принятия правильного решения.

Если A

?1 | ?2 - два A-правила и входная цепочка начинается с непустой строки, выводимой из , мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув A A'. Тогда после анализа того, что выводимо из , можно развернуть по A' ?1 или по A' ?2. Левофакторизованные правила принимают вид

A

A'

A'

?1|?2

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

Вход. КС-грамматика G.

Выход. Левофакторизованная КС-грамматика G', эквивалентная G.

Метод. Для каждого нетерминала A найти самый длинный префикс

, общий для двух или более его альтернатив. Если e, то есть существует нетривиальный общий префикс, заменить все A-правила

A

?1|?2| ... |?n|z,

где z обозначает все альтернативы, не начинающиеся с

, на

A

A'|z

A'

?1|?2| ... |?n

где A' - новый нетерминал. Применять это преобразование, пока никакие две альтернативы не будут иметь общего префикса.

Пример 4.9. Рассмотрим вновь грамматику условных операторов из примера 4.6:

S

if E then S | if E then S else S | a E b

После левой факторизации грамматика принимает вид

S

if E then SS' | a S' else S | e E b

К сожалению, грамматика остается неоднозначной, а значит, и не LL(1)-грамматикой.

Содержание раздела

---

---