yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->         7.3  Эквивалентные преобразования КС-грамматик

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

         7.3  Эквивалентные преобразования КС-грамматик

 

     Для построения распознавателей грамматик, других целей очень часто необходимо преобразовать правила исходной грамматики к соответствующему виду. При этих преобразованиях язык, порождаемый исодной и полученными после преобразования грамматиками не  должен меняться.

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

     Рассмотрим ряд процедур, которые всегда приводят  к  эквивалентным преобразованиям.

 

  7.3.1 Удаление или добавление бесполезных (непродуктивных и  не-

                 достижимых) нетерминалов

 

     В множестве Р правил грамматики  G  непродуктивным  называют нетерминал из которого нельзя получить  цепочку  терминалов.  Для поиска в множестве правил непродуктивных нетерминалов используется следующее свойство:

     Свойство А: Если все символы правой части правила продуктивны, то продуктивен и символ, стоящий в его левой части.

 

     Процедура поиска  непродуктивных  нетерминалов  в  множестве правил P грамматики G:

     - составить список нетерминалов для которых найдется хотя бы одно правило, правая часть которого состоит только из терминалов;

     - если найдется такое правило, что все нетерминалы,  стоящие в его правой части уже занесены в список, то  добавить  в  список нетерминал стоящий в его левой части;

     - если на предыдущем шаге список не пополняется, то уже  получен исчерпывающий список всех продуктивных нетерминалов.

     Hетерминалы грамматики не попавшие в список, построенный  приведенному выше алгоритму, являются непродуктивными и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

     В множестве правил недостижимым называют нетерминал, который не может быть получен в процессе вывода.  Для поиска недостижимых нетерминалов используется следующее свойство:

     Свойство Б: Если нетерминал в левой части  правила  является достижимым, то достижимы все нетерминалы, стоящие в правой  части этого правила.

 

     Процедура поиска недостижимых нетерминалов в множестве  правил P грамматики G:

     - образовать одноэлементный список из начального  нетерминала;

     - если найдено правило, левая часть которого уже  в  списке,

то включить в список все нетерминалы из его правой части;

     - если на предыдущем шаге список не пополняется, то уже  получен исчерпывающий список всех достижимых нетерминалов.

     Hетерминалы грамматики не попавшие в список, построенный  по приведенному выше алгоритму, являются недостижимыми и, не нарушая эквивалентности, из множества правил Р можно удалить все правила, содержащие такие нетерминалы.

     Hе нарушая эквивалентности,можно также исключить правила такого вида:   A -> A

             A -> B, B -> C, C -> A (циклический блок правил).

 

     Пример : Задана грамматика G

 

       P = { S -> aS,  (1)

             S -> aA,  (2)        VN = { S, A, B, C, D };

             A -> bB,  (3)        VT = { a, b, c, d };

             A -> bC,  (4)

             B -> d,   (5)        Начальный символ - S.

             D -> c    (6) };

    Упростить исходную грамматику G.

                  Решение

    1. Поиск непродуктивных нетерминалов :

     Используя правила (5) и (6), заносим в  список  продуктивных нетерминалы B, D.  Затем по правилу (3) - A, затем по правилу (2)

- S, далее список не пополняется.  Получен полный список  продуктивных нетерминалов - { B, D,  A,  S}.  Hепродуктивный  символ  С (правило (4) можно исключить).

    2. Поиск недостижимых нетерминалов :

     Первым в список вносим начальный символ грамматики S,  затемна основании правила (2) дополняем список нетерминалом A; правило(3) дает основания  внести  в  список  нетерминал  В.  Дальнейшие действия в соответствии с алгоритмом список нетерминалов  не  пополняют. Полученный список выглядит так {S,A,B}.

     Hедостижимый нетерминал D.  Правило (6) из множества  правил грамматики S можно исключить.

     В  результате  этих  преобразований  получаем  эквивалентную грамматику S1: VN = {S, A, B}; VT = {a, b, d};  начальный  символ S; P = { S -> aS     (1)

         S -> aA     (2)

         A -> bB     (3)

         B -> d  }.  (4)

 

 

39