yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->               7.3.2 Добавление нетерминала

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

               7.3.2 Добавление нетерминала

 

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

     Пример: Пусть в исходной грамматике G одно из  правил  имеет вид A -> abВc.  Обозначив bB через новый  нетерминал  N,  заменим это правило двумя:  A -> aNc;  N -> bB.

     Процедуру добавления нетерминала к  множеству  правил  можно применять многократно.

 

                  7.3.3  Подстановка правил

 

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

 

    В множество Р можно добавить правило  A -> х,  если   A +-> х. (если цепочка х выводима из А с применением  других  правил  множества Р).

 

             7.3.4 Изменение направления рекурсии

 

     Для построения  распознавателей  в  правилах  грамматики  не должно быть левосторонней рекурсии, т.е. правил вида A -> Ax. Пусть в исходной грамматике есть следующее правило:  A -> Ax1¦ Ax2¦...¦Axk¦y1¦y2¦....¦ys (знак ¦ означает "или", т.е. в этом правиле объединено несколько правил с  одинаковыми  левыми частями; xi,yi цепочки терминалов и нетерминалов и  yi  не  начинаются с А). Исходная грамматика не содержит нетерминала В.     Тогда возможна эквивалентная замена такого составного правила на два не содержащих левосторонней рекурсии:

 

  A -> y1¦y2¦....¦ys¦y1B¦y2B¦....¦ysB

 

  B -> x1¦x2¦....¦xk¦x1B¦x2B¦....¦xkB

 

    Пример: Пусть в исходной грамматике G имеется правило  с  левосторонней рекурсией    A -> Abc ¦ b. Устраним левостороннюю рекурсию.

     Введем обозначения: х1=bc;  y1=b. После замены получим:

              A -> b ¦ bB;

              B -> bc ¦ bcB.

 

 

40