Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 53 стр.

                                                                          53
                                  Факторизация


      Во многих ситуациях грамматики, не обладающие признаком LL(1),
можно    преобразовать      в   LL(1)-грамматики   с   помощью    процесса
факторизации. Рассмотрим пример такой ситуации.
      P → begin D ; С end                     С→s;С
      D→d,D                                   С→s
      D→d
      В процессе факторизации мы заменяем несколько правил для одного
нетерминала в левой части, правая часть которых начинается с одного и того
же символа (цепочки символов) на одно правило, где в правой части за
общим началом следует дополнительно вводимый нетерминал. Также
грамматика дополняется правилами для дополнительного нетерминала,
согласно которым из него выводятся различные «остатки» первоначальной
правой части правила. Для приведенной выше грамматики это даст
следующую LL(1)-грамматику:
P → begin D ; С end
D→dX       (вводим дополнительный нетерминал X)
X→,D       (по 1-му правилу для D исходной грамматики за d следует , D)
X→ε        (по 2-му правилу для D исходной грамматики за d ничего нет
           (пустая строка))
С→sY       (вводим дополнительный нетерминал Y)
Y→;С       (по 1-му правилу для C исходной грамматики за s следует ; C)
Y→ε        (по 2-му правилу для C исходной грамматики за s ничего нет
           (пустая строка))
Аналогичным образом, порождающие правила
             S → aSb                               S→ε
             S → aSc
можно преобразовать путем факторизации в правила