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



Построение преобразователя - часть 2


             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) Заключительное правило строим так: