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

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

  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 шаге.

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


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








---