Теория и реализация языков программирования

         

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


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)-грамматикой.



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