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

       

Построение преобразователя


   Покажем теперь, как по заданной СУ - схеме можно построить детерминированный преобразователь. В начале по заданной СУ - схеме построим транслирующую грамматику Г. Это всегда можно   сделать, поскольку заданная СУ - схема должна быть простой. Если входная грамматика заданной СУ - схемы относится к классу LL(1) -грамматик, то и входная грамматика транслирующей грамматики также должна относиться к этому классу, поскольку при построении Т - грамматики входные правила изменениям не подвергались. Учитывая, что искомый преобразователь должен в процессе формирования выхода осуществлять и распознавание входной цепочки, будем его строить по правилам транслирующей грамматики, используя правила построения распознавателя.


   Такой преобразователь должен воспроизводить левый вывод входной цепочки в магазине и удалять терминальные символы, на ходящиеся в вершине, при совпадении их с очередным символом на входной ленте. Однако при этом в магазин будут записываться выходные символы, содержащиеся в правилах Т - грамматики, и возникнут неопределенные ситуации при появлении выходного символа в вершине магазина. Чтобы исключить такие ситуации, дополним этот правила построения преобразователя следующим правилом: при появлении выходного символа в вершине магазина он должен передаваться на выход независимо от того, какой символ находится под входной головкой.


     Построение функции переходов МП

     (1) Для  всех правил вида <A>

--> ba,  где b О

Vтвх и a О(Vтвх

U Vтвых U Va)*, строим ко-
         манды:

               j( s0, b,  A)=( s0, a', $ ),

             где a' - зеркальное отображение цепочки a.
         (2) Для всех правил вида <A>

    --> <B>a, где B ОVa и a О(Vтвх

    U Vтвых U Va)*, строим коман-
             ды:




                 j*( s0, u, A ) = ( s0, aB , $ ),


               где u О  ВЫБОР(<A> --> <B>aвх) и  aвх -  цепочка,  полученная  из a путем удаления из
               нее всех выходных символов.
      .      (3) Для всех правил вида <A>

      --> $
      строим команды:


                   j*( s0, u, A ) = ( s0, $, $ ),


               где u О

        ВЫБОР(<A> --> $).
             (4) Для всех символов b, принадлежащих, Vтвх , стоящих на  первом месте  в  правой части правил
                  транслирующей  грамматики, т.е. символов,заносимых в магазин, строим  правило:


                     j( s0, b, b ) = ( s0, $, $ ).


               (5) Для всех выходных символов {u}, таких что  u О Vтвых U {$}, строим команды:


                       j*( s0, z, {u} ) = ( s0, $, {u} ),


                     где z О

            Vтвх.
                     Точнее команды строятся для сочетаний {u}z, таких что z может следовать за {u} в цепочках,
                    выводимых в за  данной грамматике.
                 (6) Заключительное правило строим так:


                         j( s0, $, h0 ) = ( s0, $, $ ).


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



              Содержание раздела