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

                                                                                     46
        Определить, используется ли в качестве заданной грамматики s-
грамматика, очень легко, и в некоторых случаях грамматику, которая не
является s-грамматикой, можно преобразовать в нее, не затрагивая при этом
генерируемый язык.
        Рассмотрим     проблему   разбора    строки      paaaxbbb        с     помощью
приведенной      выше     s-грамматики.   Начав    с    символа     S,       попытаемся
генерировать строку. Применим левосторонний вывод. Результат приводится
ниже.
        Исходная строка: paaaxbbb
        Вывод:       S → pX → paXb → paaXbb → paaaXbbb → paaaxbbb
        При выводе начальные терминалы в сентенциальной форме сверяются
с символами в исходной строке. Там, где допускается замена самых левых
терминалов в сентенциальной форме с помощью более чем одного
порождающего         правила,   всегда    можно        выбрать    соответствующее
порождающее правило, исследовав следующий символ во входной строке.
Это связано с тем, что, поскольку мы имеем дело с s-грамматикой, правые
части альтернативных порождающих правил будут начинаться с различных
терминалов. Таким образом, всегда можно написать детерминированный
анализатор, осуществляющий разбор сверху вниз, для языка, генерируемого
s-грамматикой.
        LL(1)-грамматика является обобщением s-грамматики, и принцип ее
обобщения все еще позволяет строить нисходящие детерминированные
анализаторы. Две буквы L в LL(1) означают, что строки разбираются слева
направо (Left) и используются самые левые выводы (Left), а цифра 1 – что
варианты     порождающих        правил    выбираются       с     помощью         одного
предварительно просмотренного символа. Кстати, если речь идет, например,
о LL(2)-грамматике, это значит, что строки разбираются слева направо и
используются самые левые выводы, а варианты порождающих правил
выбираются с помощью двух предварительно просмотренных символов.
Аналогично,      термин     LR(1)-грамматика      подразумевает,         что     строки