Специальная математика. Соловьев А.Е. - 84 стр.

                               7.13. LL(1) - грамматики.
                                        (left - leftmost)

LL(1) - грамматики относятся к нисходящим грамматикам (сверху - вниз).
Они отличаются от q-грамматик тем, что правые части могут начинаться с нетерминальных
символов, но таких, которые после подстановок терминальных символов обеспечивают
однозначность выбора грамматических правил.
В LL(1) - грамматиках разворачиваются самые левые нетерминальные символы
сентенциальной формы и анализируется очередной самый левый терминальный входной
строки. Возможен анализ k самых левых символов входной строки, Тогда грамматику
называют LL(k) - грамматикой. Но, поскольку грамматики LL(k) и LL(1) эквивалентны в
плане порождаемых языков, остановимся на рассмотрении только последней.

F() - множество терминальных символов, стоящих первыми (First)) в цепочках, выводимых
из строки .
N(А) - множество терминальных символов, следующих (Next) в цепочках за данным
нетерминальным символом А.

   Множество выбора для каждого правила формируется с учетом множества первых и
множества следующих символов.
  LL(1) - это такая грамматика, у которой для правил с одинаковыми левыми частями
множества выбора не пересекаются.

1. S  AbB   E(1) = F(AbB) = {a, b, c, e}
2. S  d     E(2) = {d}
3. A  CAb   E(3) = F(CAb) = {a, e}
4. A  B     E(4) = F(B)  N(A) = {c}  {b} = {c, b}
5. B  cSd   E(5) = F(cSd) = {c}
6. B       E(6) = F()  N(B) = {}  {b, d, ┤}
7. C  a     E(7) = {a}
8. C  ed    E(8) = {e}

             S          A           B             C         b   D        
   a     1          3                         7
         AbB        CAB
                       >   <
   b     1          4     B     6
         AbB            > <               >
                                <
   c     1          4     B     5       Sd
         AbB            > <

   d     2                      6
                                          >
                                <
   e     1          3                         8       d
         AbB        CAB


                                              — 84 —