Пред.Страница   След.Страница   Раздел   Содержание

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}.
 

Пред.Страница   След.Страница   Раздел   Содержание