2.2 Определение непроизводящих символов.

Определение.Символ <X> VAназываетсянепроизводящим, если из него не может быть выведена конечная терминальная цепочка.

     Рассматривая правила грамматики,  можно сделать  вывод,  что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:     1. Составить список нетерминалов,  для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.     2. Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.     3. Если на шаге 2 список больше не пополняется,  то  получен  список всех производящих нетерминалов грамматики,  а все нетерминалы не попавшие в него являются непроизводящими. Анализируя в соответствии с приведенными правилами следующую грамматику :                                 Г_{2. 0}:          R = {<I>a<I>a,

<I>b<A>d,<I>c,<A>c<B>d,<A>a<A>d,<B>d<A>f  },находим, что здесь непроизводящими являются символы <А> и <В>. После удаления правил, содержащих непроизводящии символы, получаем:R' = {<I> a<I>a, <I> c}.

• 2.3 Определения недостижимых символов.

  Определение. Символ XVт VAназываетсянедостижимымв КС-грамматике Г, если X не появляется ни в одной выводимой цепочке.

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

1. Образовать одноэлементный список, состоящий из начального символа

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

3.  Если на шаге 2 новые нетерминалы в список больше  не  добавляются,  то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.

Например, применяя приведенные правила к следующей грамматике:  

Г_{2. 1} :      R = {   <I> a<I>b,

        <I> c,        <A> b<I>,        <A> a   },

• находим, что A является недостижимым символом.2.4  Определения бесполезных символов.

Бесполезныйсимвол грамматики можно определить следующим образом:

 

Определение.Символ X, который принадлежит VтU Vaназываетсябесполезнымв  КС-грамматике Г, если он является недостижимым или непроизводящим.

 

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

 Г_{2. 2} : R = {<I>ac

<I> b<A>, <A> c<B><C>, <B> a<I><A>, <C> bc, <C> d  }.

Вначале находим, что <А> и <В> являются непроизводящими символами и, исключая правила с непроизводящими символами , получаем:  

R' = {<I>ac          <C> bc,          <C> d  }.

В полученной схеме символ <C>  является недостижимым символом. Исключая правила, содержащие этот символ, получаем:  

R" = {<I>ac  }.

 

Определение.КС-грамматика называетсяприведенной, если она  не содержит бесполезных символов.

 

В дальнейшем изложении рассматриваются только приведенные КС-грамматики. Другие виды преобразований грамматик, описываемые ниже, предназначены для  исключения правил определенного вида из схемы грамматики.