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

    • 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 является недостижимым символом.
     

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

    •