Определение. Символ X
О VтИ VA
называется недостижимым
в КС-грамматике Г, если X не появляется ни в одной выводимой цепочке.
Рассматривая правила грамматики, можно заметить , что если нетерминал в
левой части правила является достижимым , то и все символы правой части
являются достижимыми. Это свойство правил является основой процедуры выявления
недостижимых символов, которую можно записать так:
Образовать одноэлементный список, состоящий из начального символа
Если найдено правило, левая часть которого уже имеется в списке, то включить
в список все символы, содержащиеся в его правой части.
Если на шаге 2 новые нетерминалы в список больше не добавляются,
то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие
в список, являются недостижимыми.
Например, применяя приведенные правила к следующей грамматике:
Г2. 1 :
R = { <I> ®a<I>b,
<I> ®c, <A>
®b<I>, <A>
®a },
находим, что A является недостижимым символом.