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

    Основное использование распознавательных средств задания языков состоит в
построении алгоритмов грамматического разбора. Поэтому необходимо для произвольной
КС-грамматики уметь строить эквивалентный МП-автомат.
    МП-автомат представляет интерес как средство разбора в КС-грамматиках
произвольного вида. Этот факт сформулирован в следующей теореме.
    Теорема. Языки, порождаемые КС-грамматиками, совпадают с языками,
распознаваемыми МП-автоматами.
    Доказательство. Существуют две стратегии разбора: восходящий и нисходящий разбор.
Рассмотрим обе стратегии разбора.

      5.4.1. Восходящий разбор в МП-автомате
    При восходящей стратегии необходимо найти основу и редуцировать ее к какому-нибудь
нетерминалу в соответствии с правилами данной грамматики. Это можно сделать в том
случае, если реализовать следующий алгоритм функционирования МП-автомата:
    1) любой входной символ записывается в магазин;
    2) если в верхушке магазина сформирована основа, совпадающая с правой частью
правила, то она заменяется на нетерминал в левой части этого правила;
    3) разбор заканчивается, если в магазине остается аксиома, а входная цепочка
рассмотрена полностью.
    В соответствии с этим алгоритмом для КС-грамматики G = (VT, VN, P, S) построим МП-
автомат:
     M = (К, VT, Г, δ, p0, F, B0), где Г = VT ∪ VN ∪ {B0},
    K = {p0, F}, F = {f}.
    Функция переходов δ будет содержать следующие команды:
    а) p0, a, ε → p0, a - для любых a ∈ VT;
    б) p0, ε, ϕ’ → p0, A - для всех правил A → ϕ ∈ P, где ϕ’ - зеркальное отображение ϕ;
    в) p0, ε, SB0 → f, B0.

    В общем случае команда выглядит так:
    pi, σ, γ → pj, λ , где pi ∈ K – состояние автомата до выполнения команды, σ∈Vt – символ
на входной ленте, γ∈Γ - символ верхушки магазина, pj ∈ K – состояние автомата после
выполнения команды, λ∈Γ - символ, который записывается в магазин.
    Таким образом, любому выводу в грамматике G взаимно однозначно соответствует
последовательность команд построенного МП-автомата. Обратное построение КС-
грамматики по произвольному МП-автомату также возможно, но не представляет
практического интереса.
    Рассмотрим пример восходящей стратегии разбора.
    Пусть дана грамматика G:
              S → S+A | S/A | A
              A → a | (S);
    VN={S, A}, VT={a, (, ), +, /}.
    Для заданной КС-грамматики G необходимо построить МП-автомат.
    Эквивалентный МП-автомат должен содержать следующие команды:
    1. Команды переноса терминальных символов в магазин:
                                           p0, a, ε → p0, a ;
                                           p0, +, ε → p0, + ;
                                           p0, /, ε → p0, / ;
                                           p0, (, ε → p0, (;
                                           p0, ), ε → p0, ).