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

                                                                      45
                         8. LL(1) - ГРАММАТИКИ
     LL(1)-грамматика – это грамматика такого типа, на основании
которой можно получить детерминированный синтаксический анализатор,
работающий по принципу сверху вниз. Прежде чем более точно определить
LL(1)-грамматику, введем понятие s-грамматики.
     S-грамматика представляет собой грамматику, в которой:
     1) правая часть каждого порождающего правила начинается с
терминала;
     2) в тех случаях, когда в левой части более чем одного порождающего
правила появляется один и тот же нетерминал, соответствующие правые
части начинаются с разных терминалов.
     Первое условие аналогично утверждению, что грамматика находится в
нормальной форме Грейбаха, только за терминалом в начале каждой правой
части правила могут следовать нетерминалы и/или терминалы.
     Второе условие позволяет написать детерминированный нисходящий
анализатор, так как при выводе предложения языка всегда можно сделать
выбор между альтернативными порождающими правилами для самого
левого нетерминала в сентенциальной форме, предварительно исследовав
один следующий символ.
     Грамматика с порождающими правилами
     S→ pX                                    X→x
     S→ qY                                    Y→ y
     X → aXb                                  Y→ aYd
     представляет собой s-грамматику, тогда как следующая грамматика,
которая генерирует тот же язык, не является ею:
     S→R                                      X → aXb
     S→T                                      X→x
     R → pX                                   Y → aYd
     T → qY                                   Y→y
поскольку правые части двух правил не начинаются с терминалов.