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


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

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

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

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