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


Построение восходящих преобразователей


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



  4.3.7  Построение восходящих преобразователей.

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

  Определение. Транслирующая грамматика,  записанная в  форме,   когда все 
                           символы действия в правых частях распо  ложены правее всех 
                           терминальных и  нетерминальных   символов, называется 
                           постфиксной  транслирующей грамматикой. 
 

     Это определение  говорит  о  том,  что  правила  постфиксной транслирующей грамматики должны иметь вид:

                 <A> ®

            a{ z },

где  a О( VT  И  VА) *  и z О VTвых

.
     Любая транслирующая грамматика может  быть  преобразована  в постфиксную  форму путем разбиения правил грамматики и добавления новых нетерминальных символов.  Например, для преобразования правила

               <A>  ® a{ z }<B>{ w },

введем дополнительный нетерминал   и разобьем исходное правило на две части. В результате получаем правило в постфиксной форме: