Основы конструирования компиляторов

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


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).



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