yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->            8.4 Построение МП-распознавателей для q-грамматик

Дискретная математика

            8.4 Построение МП-распознавателей для q-грамматик

 

     КС-грамматика (грамматика второго типа) называется q-граммаикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми  левыми  частями множества  "ВЫБОР" попарно не пересекаются.

     Правила имеют вид Х -> y&, где y - терминал; & -  любая  це-почка терминалов и нетерминалов,  возможно  пустая  (q-грамматика может содержать эпсилон-правил т.е. правила вида Х -> @).

     Замечание: q-грамматика отличается  от  S-грамматики  только наличием в множестве Р эпсилон-правил; этот факт существенно  осложняет построение МП-распознавателя.

     Дадим определение ряду унарных отношений, которые можно построить на множестве  {VT, -+}.

     Отношение "СЛЕД Y" (следующий за Y) - подмножество множества

входных символов МП-распознавателя, которые  могут  следовать  за нетерминалом Y в любых сентенциальных формах, получаемых из  множества Р правил грамматики.

     Отношение "ВЫБОР Y" - подмножество множества входных  символов МП-распознавателя, c которых могут начинаться цепочки,  выводимые из нетерминала Y в любых сентенциальных формах,  получаемых из множества Р правил грамматики.

     Отношение "ВЫБОР Y" для конкретной грамматики  строится  как объединение таких отношений, построенных для всех правил,  содержащих в левых частях Y.

     Для правил вида Y -> x& (1) и Y -> z (2) множество "ВЫБОР Y" всегда равно первому терминалу правой части правила:

       для правила 1 "ВЫБОР Y1" ={x}

       для правила 2 "ВЫБОР Y2" ={z}

     Если в множестве Р правил грамматики нет больше  правил  для нетерминала Y, то отношение "ВЫБОР Y" = "ВЫБОР Y1" U "ВЫБОР Y2"

                   "ВЫБОР Y" = {x,z}.

     Для правил вида Y -> @ (3) отношение "ВЫБОР Y3" = "СЛЕД Y" и определять его нужно, анализируя все правила грамматики.

     Для q-грамматики попарное пересечение множеств  "ВЫБОР"  для правил с одинаковыми левыми частями должно быть пусто.  Это условие гарантирует однозначность работы  МП-распознавателя  (правило грамматики применяется всякий раз, когда  магазинный  символ  является его левой частью, а входной символ  принадлежит  множеству

"ВЫБОР" этого правила).

 

     Рассмотрим на примере процедуру  проверки  КС-грамматики  на предмет ее принадлежности к классу q-грамматик.

     Пусть задана грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

     Доказать, что заданная грамматика относится к классу q-грамматик.

                      Решение

     Для каждого из двух нетерминалов в множестве правил Р имеется больше одного правила (предполагается, что процедуры  исключения непродуктивных и недостижимых нетерминалов уже выполнены).

  1. Для нетерминала S:

     "ВЫБОР S1" = {a}; "ВЫБОР S2" = {b}.

     "ВЫБОР S1" П "ВЫБОР S2" = { } (пересечение пусто).

  2. Для нетерминала A:

     "ВЫБОР A3" = {c}; "ВЫБОР A4" = "СЛЕД A"

После нетерминала A могут следовать -+ (правило 1) и a в выводе

     1     3       1   (номера правил)

   S -> aA -> acSa -> acaAa ->... символ a,

   отсюда  "СЛЕД A" = { -+, a}.

 

 "ВЫБОР A3" П "ВЫБОР A4" = {c} П {-+,a}={ }(пересечение пусто).

     Вывод: заданная грамматика  G[S] является q-грамматикой.

     Построим для этой грамматики МП-распознаватель.

     Для q-грамматики существует формальная процедура  построения МП-распознавателя с одним состоянием   по следующему алгоритму:

  1.Входной алфавит МП-распознавателя  V = {VT,-+}.

  2.Множество магазинных символов {  VN,  VT1,  \/},  где  VT1  часть терминальных символов грамматики, которые встречаются в цепочках & множества правил.

  3.Начальная конфигурация - в магазине находится начальный  символ грамматики (например для грамматики G[S] -  S \/).

   Замечание: условимся запись содержимого  магазина  вести  так,                           чтобы верхний символ (тот, с которым работает МП-автомат) занимал самую левую позицию.

  4.Управляющая таблица строится так: столбцы таблицы  -  символы входного алфавита (последний символ -+);строки таблицы - магазинные символы. Заполнение управляющей таблицы:

   а) для правил грамматики вида Х -> y& (& не пустая цепочка)

           .... ¦   y    ¦

               ............

           -----+--------+----------

                ¦\Зам.& /¦

            X   ¦ \    / ¦  ....

                ¦  \  / П¦

           -----+---\/---+----------

               ............

           .... ¦ .....  ¦  ....

 

   б) для правил грамматики вида  Х -> y (&  пустая цепочка)

           .... ¦   y    ¦

              ..............

           -----+--------+----------

                ¦\Выт.Х /¦

            X   ¦ \    / ¦  ....

                ¦  \  / П¦

           -----+---\/---+----------

               ............

           .... ¦ .....  ¦  ....

   В соответствии с п.п. а) и б) обрабатывается все  множество  Р правил грамматики (кроме эпсилон правил).

   в) клетки таблицы на пересечении терминал-магазинный символ  и тот же терминал-входной алфавит:

 

           ....  ¦   y    ¦

                .............

           ------+--------+----------

                 ¦\Выт.y /¦

            y    ¦ \    / ¦  ....

                 ¦  \  / П¦

           ------+---\/---+----------

                .............

           ....  ¦ .....  ¦  ....

   г) каждая клетка таблицы на пересечении нетерминала Z и  входных символов МП-распознавателя из множества "СЛЕД Z" ={y,...-+}:

           ....  ¦   y    ¦      ....  ¦  --+   ¦

                 ¦        ¦  ....      ¦        ¦

                .............         .............

           ------+--------+--- ... ----+--------+

                 ¦\Выт.Z /¦            ¦\Выт.Z /¦

            Z    ¦ \    / ¦            ¦ \    / ¦

                 ¦  \  / Д¦            ¦  \  / Д¦

           ------+---\/---+----... ----+---\/---+

                .............         .............

           ....  ¦ .....  ¦  ........  ¦ .....  ¦

 

 

  г) все оставшиеся клетки последнего столбца таблицы (-+) заполняются "отв."кроме клетки на пересечении со строкой \/, в которой ставится "доп.";

   д) оставшиеся незаполненными клетки управляющей таблицы заполняются буквой Е-"состояние ошибки".

 

     Построим МП-распознаватель  для  языка,  порождаемого  G[S]

грамматикой из предыдущего примера.

 

    Пусть задана q-грамматика G[S]=(VT={a,b,c}; VN={S,A}; S; P);

P={S -> aA(1); S -> b(2); A -> cSa(3); A -> @ (4)}.

 

                       Решение

 

  1.Проверка нетерминалов на достижимость и продуктивность

 

 S достижим (начальный символ); A достижим (правило 1);

 

 S продуктивен (правило 2); A продуктивен (правило 1).

 

  2.Построение МП-распознаватель(ранее доказано, что это  q-грамматика):

    - входной алфавит V={a,b,c,-+};

 

    - множество магазинных символов {S,A,a,\/};

 

    - начальное содержимое магазина  S,\/;

 

    - управляющая таблица имеет вид:

              г======T========T========T========T========¬

              ¦      ¦    a   ¦    b   ¦    c   ¦  -+    ¦

              ¦------+--------+--------+--------+--------¦

              ¦  \/  ¦   E    ¦    E   ¦    E   ¦ доп.   ¦

              ¦      ¦        ¦        ¦        ¦        ¦

              ¦------+--------+--------+--------+--------¦

              ¦      ¦\ Зам. /¦\ Выт. /¦        ¦        ¦

              ¦  S   ¦ \ А  / ¦ \ S  / ¦   Е    ¦ отв.   ¦

              ¦      ¦  \  / П¦  \  / П¦        ¦        ¦

              ¦------+---\/---+---\/---+--------+--------¦

              ¦      ¦\ Выт. /¦        ¦\ Зам. /¦\ Выт. /¦

              ¦  A   ¦ \ А  / ¦   Е    ¦ \ Sa / ¦ \ А  / ¦

              ¦      ¦  \  / Д¦        ¦  \  / П¦  \  / Д¦

              ¦------+---\/---+--------+---\/---+---\/---¦

              ¦      ¦\ Выт. /¦        ¦        ¦        ¦

              ¦  a   ¦ \ а  / ¦   Е    ¦   Е    ¦ отв.   ¦

              ¦      ¦  \  / П¦        ¦        ¦        ¦

              L======¦===\/===¦========¦========¦========-

     Примечание: поле для состояний осталось незаполненным,  т.к. заполнять его нет смысла (состояние только одно).

  3.Проверка работы МП-распознавателя.

    Получим цепочку на основании правил грамматики:

     1      3       1        3          1           4

   S -> aA  -> acSa -> acaAa -> acacSaa -> acacaAaa -> acacaaa

    Работу МП-распознавателя по разбору цепочки acacaaa  представим в виде таблицы:

-----------T-----------T---------T----------T---------T---------¬

¦Необработ.¦ Обраб. вх.¦Верх.симв¦Содержимое¦Действие ¦Действие ¦¦цепочка   ¦ символ    ¦магазина ¦магазина  ¦с магаз. ¦с вх.симв¦

+--------T-+-----------+---------+----------+---------+---------+

¦acacaaa-+ ¦     a     ¦     S   ¦   S \/   ¦  Зам. A ¦    П    ¦

¦ cacaaa-+ ¦     c     ¦     A   ¦   A\/    ¦  Зам. Sa¦    П    ¦

¦  acaaa-+ ¦     a     ¦     S   ¦   Sa\/   ¦  Зам. A ¦    П    ¦

¦   caaa-+ ¦     c     ¦     A   ¦   Aa\/   ¦  Зам. Sa¦    П    ¦

¦    aaa-+ ¦     a     ¦     S   ¦   Saa\/  ¦  Зам. A ¦    П    ¦

¦     aa-+ ¦     a     ¦     A   ¦   Aaa\/  ¦  Выт. А ¦    Д    ¦

¦     аa-+ ¦     a     ¦     а   ¦   aa\/   ¦  Выт. а ¦    П    ¦

¦      а-+ ¦     а     ¦     а   ¦   а\/    ¦  Выт. а ¦    П    ¦

¦       -+ ¦     -+    ¦    \/   ¦    \/    ¦допустить¦    -    ¦

L----------+-----------+---------+----------+---------+----------

     Контрольная цепочка распознается построенным  МП-распознавателем.

 

 

 

43