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

       

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


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


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

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

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

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

           <A> ®

      a{ z },

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

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

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



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


               <D> ® a{ z }, 

               <A>  ® <D><B>{w}.


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


            Г 4. 2 : <I> ® a{a}<R>,

                       <R> ® +a{a}{+}<R>,

                       <R>®-a{a}{-}<R>,

                       <R>® $.


               Добавляем три новых нетерминала <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 шаге.

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


          Содержание раздела