Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 30 стр.

      Таблица 5.1 – Распознавание МП-автоматом строки (а)

   Номер           Текущее
                                  Входная строка         Содержимое магазина
конфигурации      состояние
     1                q                  (a)                        S
     2                q                  (a)                        A
     3                q                  (a)                       (S)
     4                q                   a)                       S)
     5                q                   a)                       A)
     6                q                   a)                       a)
     7                q                    )                        )
     8                q                  ε                          ε

              Алгоритм 5.3. Построение расширенного МП-автомата
                               по КС-грамматике

      Построим МП-автомат, выполняющий правосторонний разбор. Данный
автомат имеет единственное текущее состояние и одно заключительное состоя-
ние, в котором стек пуст. Стек содержит левую часть текущей сентенции. Пер-
воначально в стек помещается специальный магазинный символ, маркер пусто-
го стека #. На каждом шаге автомат по правилу грамматики замещает нетерми-
налом строку верхних символов стека или дописывает в вершину входной сим-
вол.
     Вход: КС-грамматика G = (VT , V N , P, S ) .
     Выход: расширенный МП-автомат M = (Q, T , N , F , q0 , N 0 , Z ) такой, что
L(M) = L(G).
      Шаг 1. Положить Q = {q, r}, q0 = q, Z = {r}, N = VT ∪ VN ∪ {#}, T = VT,
N0 = #.
      Шаг 2. Для каждого правила вида ( A → β ) ∈ P , где β ∈ V * , сформировать
магазинную функцию вида F (q, ε , β ) = (q, A) , предписывающую заменять пра-
вую часть правила в вершине стека нетерминалом из левой части, независимо
от текущего символа входной строки.
      Шаг 3. Для каждого терминала t ∈ T сформировать магазинную функцию
вида F (q, t , ε ) = (q, t ) , которая помещает символ входной строки в вершину
стека, если там нет правой части правила, и перемещает читающую головку.
      Шаг 4. Предусмотреть магазинную функцию для перевода автомата в за-
ключительное состояние F (q, ε , # S ) = (r , ε ) .

    Пример 5.2. Для грамматики из примера 5.1 построить расширенный
МП-автомат. Последовательность построения МП-автомата будет иметь вид.
    1) Q = {q, r}, q0 = q, T = {+, (, ), a}, N = {+, (, ), a, S, A}, N0 = #, Z = r.


30