Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 43 стр.

    Эти команды обеспечивают занесение терминального символа из входной ленты в
магазин.
    2. Команды редукции по правилам грамматики:
                                   p0, ε, A+S → p0, S ;
                                   p0, ε, A/S → p0, S ;
                                   p0, ε, A → p0, S ;
                                   p0, ε, )S( → p0, A ;
                                   p0, ε, a → p0, A.
         Эти команды заменяют зеркальное отображение правила, полученного в верхушке

  магазина, на нетерминал в левой части данного правила грамматики.

    3. Команды проверки на завершение разбора:
                                     p0, ε, SB0 → f, B0.
    Разбор завершается, если в магазине остались аксиома и маркер дна магазина, а входная
цепочка полностью рассмотрена.
    Подадим на вход автомата цепочку      a/(a+a)   и выполним разбор. Процесс разбора
представлен в таблице 1.

      5.4.2. Нисходящий разбор в МП-автомате
         На любом шаге нисходящего разбора должно применяться какое-либо правило. В

  начальный момент таким нетерминалом является аксиома. МП-автомат, выполняющий

  нисходящий разбор, работает по следующему алгоритму:

    1) в начальный момент времени в магазин заносится аксиома: p0, ε, ε → p1, S;
    2) для каждого правила A→ϕ∈P нетерминал в верхушке магазина заменяется на правую
часть правила с помощью команды: p1, ε, A → p1, ϕ;
    3) для каждого терминала a∈VT выполняется сравнение символа на входной ленте с
символом в верхушке магазина и его поглощение: p1, a, a →p1, ε
    4) разбор заканчивается по команде: p1,ε,B0 → f, B0.
          Для грамматики, рассмотренной в предыдущем примере, разбор той же входной

  цепочки по нисходящей стратегии         будет выполняться посредством следующего

  множества команд:

   1) команда занесения аксиомы в магазин:

                                         p0, ε, ε → p0, S;
   2) команды замены нетерминала правой частью правила:
                             p1, ε, S → p1, S+A
                             p1, ε, S → p1, S/A
                             p1, ε, S → p1, A
                             p1, ε, A → p1, a
                             p1, ε, A → p1, (S);