Формальные языки


Распознавателя


    Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя .
    Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид:
    <A>  ® a a , где a

    - цепочка символов полного словаря и a принадлежит
    терминальному словарю, нужно поставить в соответствие команду

       

          (*)    f 0( s0 , e , <A> ) = ( s0

          , a

          ' a) ,

       

    которая задает такт работы без сдвига входной головки и в которой

    a ' представляет собой зеркальное отображение цепочки a

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

    символа грамматики команды:
     

               (**)    

        f ( s0 , a , a ) = ( s0 , $ )

       

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

    a, и после нее всегда должна выполняться команда (**).
    Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A>  ® a a

    поставим в соответствие команду
     

             f ( s0 , a , <A>) = ( s0 , a

            ') ,

       

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

        f ( s0 , b , b ) = ( s0




        - Начало -  - Назад -  - Вперед -