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

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

тех пор, пока не будет достаточно информации для принятия правильного решения.

Если A

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

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

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

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

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

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

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

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

Пример 4.7. Рассмотрим вновь грамматику условных

операторов из примера 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).

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

---

---

---

Главная сайта

---