s83

Пред.Страница

След.Страница

Раздел

Содержание

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

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

(1) Для всех правил вида <A> --> ba, где b О V_твхи a О(V_твх U V_твых U V_a)*, строим ко-
манды:

j( s₀, b, A)=( s₀, a', $ )

         где a' - зеркальное отображение цепочки a.
     (2) Для всех правил вида <A> --> <B>a, где B ОVa и a О(V_твх U V_твых U V_a)*, строим коман-
         ды:

j*( s₀, u, A ) = ( s₀, aB , $ ),

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

j*( s₀, u, A ) = ( s₀, $, $ ),

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

j( s₀, b, b ) = ( s₀, $, $ ).

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

j*( s₀, z, {u} ) = ( s₀, $, {u} ),

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

j( s₀, $, h0 ) = ( s₀, $, $ ).

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