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

______________________________________________________________

4.8. Построение  преобразователей

  Покажем теперь, как по заданной СУ - схеме можно построить детерминированный преобразователь. В начале по заданной СУ - схеме построим транслирующую грамматику Г. Это всегда можно   сделать, поскольку заданная СУ - схема должна быть простой. Если входная грамматика заданной СУ - схемы относится к классу LL(1) -грамматик, то и входная грамматика транслирующей грамматики также должна относиться к этому классу, поскольку при построении Т - грамматики входные правила изменениям не подвергались. Учитывая, что искомый преобразователь должен в процессе формирования выхода осуществлять и распознавание входной цепочки, будем его строить по правилам транслирующей грамматики, используя правила построения распознавателя.
   Такой преобразователь должен воспроизводить левый вывод входной цепочки в магазине и удалять терминальные символы, на ходящиеся в вершине, при совпадении их с очередным символом на входной ленте. Однако при этом в магазин будут записываться выходные символы, содержащиеся в правилах Т - грамматики, и возникнут неопределенные ситуации при появлении выходного символа в вершине магазина. Чтобы исключить такие ситуации, дополним этот правила построения преобразователя следующим правилом: при появлении выходного символа в вершине магазина он должен передаваться на выход независимо от того, какой символ находится под входной головкой.
     Построение функции переходов МП

     (1) Для  всех правил вида <A> --> ba,  где b Î V_твх и a Î(V_твх U V_твых U V_a)*, строим ко-
         манды:

j( s₀, b,  A)=( s₀, a', $ ),

         где a' - зеркальное отображение цепочки a.
     (2) Для всех правил вида <A> --> <B>a, где B ÎVa и a Î(V_твх U V_твых U V_a)*, строим коман-
         ды:

j*( s₀, u, A ) = ( s₀, aB , $ ),

         где u Π ВЫБОР(<A> --> <B>a_вх) и  a_вх -  цепочка,  полученная  из a путем удаления из
         нее всех выходных символов.
.      (3) Для всех правил вида <A> --> $ строим команды:

j*( s₀, u, A ) = ( s₀, $, $ ),

где u Î ВЫБОР(<A> --> $).
(4) Для всех символов b, принадлежащих, V_твх , стоящих на  первом месте  в  правой части правил
          транслирующей  грамматики, т.е. символов,заносимых в магазин, строим  правило:

j( s₀, b, b ) = ( s₀, $, $ ).

     (5) Для всех выходных символов {u}, таких что  u Î V_твых U {$}, строим команды:

j*( s₀, z, {u} ) = ( s₀, $, {u} ),

         где z Î Vтвх.
         Точнее команды строятся для сочетаний {u}z, таких что z может следовать за {u} в цепочках,
        выводимых в за  данной грамматике.
     (6) Заключительное правило строим так:

j( s₀, $, h0 ) = ( s₀, $, $ ).

4.8.1. Пример построения  преобразователя.

   Применение правил построения команд преобразователя рассмотрим на примере транслирующей грамматики Г, которая описывает перевод инфиксных выражений, состоящих из идентификаторов и знаков + и *, в постфиксные польские выражения. Эта грамматика имеет следующую схему:

Г _{4. 2} :    R = {<E> ®+<E><E>{+},
                       <E> ®x<E><E>{x},
                       <E> ®a{a}}

  Используя правило построения команд преобразователя (1) для правил грамматики, начинающихся входным терминальным символом, получаем команды преобразователя Мп1:

q(s₀, +, <E>) = (s₀, {+}<E><E>, $),
q(s₀, *, <E>) = (s₀, {*}<E><E>, $),
q(s₀, a, <E>) = (s₀, {a}, $)

Правила построения команд вида (2),(3),(4) к заданной грамматике неприменимы, поэтому с помощью правил вида (5) построим команды, обеспечивающие передачу выходных символов на выход. Эти команды имеют вид:

q*(s₀, +, {+}) = (s₀, $, +), q*(s₀, *, {+}) = (s₀, $, +),
q*(s₀, a, {+}) = (s₀, $, +), q*(s₀, $', {+}) = (s₀, $, +),
q*(s₀, *, {*}) = (s₀, $, *), q*(s₀, +, {*}) = (s₀, $, *),
q*(s₀, *,{a}) = (s₀, $, *), q*(s₀, $',{*}) = (s₀, $, *),
q*(s₀, a,{a}) = (s₀, $, a), q*(s₀, +{a}) = (s₀, $, a),
q*(s₀, *,{a}) = (s₀, $, a), q*(s₀, $', {a}) = (s₀, $, a)

Для перехода в заключительное состояние s₁ в соответствии с правилом (6) построим команду:

q(s₀, $', h₀) = (s₁, $, $)

   Чтобы посмотреть как работает построенный преобразователь, рассмотрим построение выходной цепочки для входа +a*aa. Последовательность конфигураций, получаемых с помощью команд преобразователя имеет вид:

(s₀, +a*aa, h₀E, $) |-- (s₀, a*aah₀{+}EE, $) |--
(s₀, *aa, h₀{+}T{a}, $) |--
(s₀, *aa, h₀{+}E, a) |--
(s₀, aa, h₀{+}{*}T{a}, a) |--
(s₀, a, h₀{+}{*}E, aa) |--
(s₀, $, h₀{+}{*}{a}, aa) |--
(s₀, $, h₀{+}{*}, aaa) |--
(s₀, $, h₀{+}, aaa*)|--
(s₀, $, h₀, aaa*+) |--
(s₀, $, $, aaa*+).

   Результатом работы преобразователяявляется выходная цепочка aaa*+, представляющая постфиксную запись заданной входной цепочки.

4.8.2. Порядок построения детерминированного магазинного преобразователя.

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

1. Построить грамматику, описывающую цепочки входного языка.
2. Проверить принадлежность этой грамматики классу LL(1)- грамматик. Если условия LL(1) - грамматики не выполняются, то попытаться выполнить преобразование или вернуться к п.1 и построить другую грамматику.
3. Построить простую СУ-схему, используя построенную грамматику в качестве входной грамматики СУ - схемы.
4. Построить транслирующую грамматику для полученной СУ -схемы.
5. Используя правила построения, найти команды преобразования для разных групп правил транслирующей грамматики.
6. Убедиться, что построенный преобразователь реализует заданный перевод, выполняя несколько примеров построения выходных цепочек с помощью команд преобразователя.

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

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

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

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

     <A> ®a{ z },

где  a Î( V_T È  V_А) *  и z Î V_Tвых .
     Любая транслирующая грамматика может  быть  преобразована  в постфиксную  форму путем разбиения правил грамматики и добавления новых нетерминальных символов.  Например, для преобразования правила

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

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

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

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

Г _4.3 : <I> ® a{a}<R>,
           <R> ® +a{a}{+}<R>,
           <R>®-a{a}{-}<R>,
           <R>® $.

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

---

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