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

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

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

  Определение. Транслирующая грамматика,  записанная в  форме, когда  все символы действия в правых частях расположены  правее всех терминальных и  нетерминальных  символов, называется  постфиксной  транслирующей грамматикой. 
     Это определение  говорит  о  том,  что  правила  постфиксной транслирующей грамматики должны иметь вид: где  a О( VT  И  VА) *  и z О VTвых .
     Любая транслирующая грамматика может  быть  преобразована  в постфиксную  форму путем разбиения правил грамматики и добавления новых нетерминальных символов.  Например, для преобразования правила введем дополнительный нетерминал   и разобьем исходное правило на две части. В результате получаем правило в постфиксной форме:      Воспользуемся этим  приемом для преобразования к постфиксной форме транслирующей  грамматики,  которая  задает  преобразование арифметических выражений без скобок, описываемых грамматикой Г 4.3, в постфиксную форму.      Добавляем три новых нетерминала <P>,  <Q>,  <S> и,  разбивая правила грамматики, получаем грамматику в постфиксной форме.

                                      Г4.4 :      <I> ® <S><R>,
                                                          <S>  ® a{a},
                                                           <R>  ® <P><R>,
                                                           <P>  ® +a{a}{+},
                                                          <R>  ® <Q><R>,
                                                          <Q>  ® -a{a}{-},
                                                           <R>  ® $.

Напомним, что при построении восходящих распознавателей  обработка каждого правила A
<A> ® ax с номером k с символом x, занимающим самую правую позицию в правой части правила, связывалась операция  Свертка(k).  В  постфиксной транслирующей грамматике самую правую позицию могут занимать символы действия, поэтому при построении восходящего преобразователя эти символы можно объединить с операцией свертки в одну  операцию,  которую  назовем
Свертка  - Действие(k) (СД(k)). Учитывая, что все символы действия постфиксной транслирующей грамматики могут быть объединены  с  операциями свертки, приходим к заключению, что процедура построения восходящего распознавателя может быть применена для построения  восходящего преобразователя при условии, что вместо операции Cвертка (k) будет использоваться операция Свертка -  Действие(k)  для  правил построения постфиксной транслирующей грамматики,  содержащая символы действия.
В  качестве  иллюстрации  последнего  утверждения рассмотрим построение преобразователя для грамматики Г 4. 3. Выполняя последовательно шаги процедуры построения SLR(1) преобразова-
теля  для грамматики с аннулирующими правилами и заменяя операции Свертка(k) для правил 2, 4 и 6 операциями Свертка  -  Действие(k), получаем  таблицы переходов и действий искомого преобразователя в следующем виде.
 

                                                                                                            Таблица 4.1

     
   I   S   R   P   Q   +   -    a
  I0                
  S     R1   P   Q   +   -  
 R1                
 a2                
  P      R3   P   Q   +   -  
 R3                
  +                a4
 a4                
  Q      R5   P   Q   +   -  
 R5                
  -                a6
 a6                
  h0  I0   S            a2

                                     Таблица 4.2

   +    -    a   |--
  I0         D
   S   П    П     c7
   R1        c1
 c1  CD2  CD2   CD2
   P   П    П      c7
   R3         c3
   +        П  
  a4  CD4  CD4    CD4
   Q    П    П      c7
  R5         c5
   -        П  
  a6  CD6    CD6  CD6
  a4        П  

 

      В качестве демонстрации работы преобразователя построим последовательность конфигураций для входной цепочки а + а - а|--, дополнив эту последовательность указателем выполняемого действия.


       1. а + а - а|--     h0                      П            -
               2.  + а - а|--       h0 a2                 СД2                 a
                3. + а - а|--        h0 S                   П                     a
              4.  а - а|--          h0 S +              П                     a
                  5.  - а|--             h0 S + a4         СД4                aa +
                 6. - а|--              h0 S P              П                    aa +
                7.  а|--               h0 S P-            П                   aa +
                      8.   |--                h0 S P - a6      СД6              aa + a -
                      9.   |--                h0 S P Q       С7                  aa + a -
                    10.  |--                h0 S P Q R5       С5             aa + a -
                   11.  |--                h0 S PR3            С3            aa + a -
                    12.  |--                h0 S R1             С1             aa + a -
                    13.  |--                h0  I0                  Д                    aa + a -
    Приведенная последовательность конфигураций показывает,  что выходная цепочка формируется при выполнении операций СД2,  СД4  и СД6 соответственно на 2, 5 и 8 шаге.


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


Hosted by uCoz