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


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


   Покажем теперь, как по заданной СУ - схеме можно построить детерминированный преобразователь. В начале по заданной СУ - схеме построим транслирующую грамматику Г. Это всегда можно   сделать, поскольку заданная СУ - схема должна быть простой. Если входная грамматика заданной СУ - схемы относится к классу 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)*, строим коман-
         ды: