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

4. Способы описания перевода и преобразователи

4.1. Описание перевода или трансляции .

В общем случае перевод или трансляцию можно представить как соответствие между словами алфавита Р и алфавита W. Если цепочка a Î P* , цепочка b Î W* , они называются соответственно входной и выходной цепочками.

 

Определение. Если заданы входной алфавит P и выходной алфавит 
                      W, то переводом с языка Lвх, состоящего из цепочек 
                      множества P*, на язык Lвых, состоящий из цепочек 
                      множества W*, называется множество C пар цепочек 
                      (a ,b ) таких, что a Î Lвх и b Î Lвых. 

                                     C={(a ,b ) | a Î Lвх и b Î Lвых}.  
 

 

 
Если входной и выходной алфавиты заданы в виде: P = {a,b,c,d} и W = {00,01,10,11}, и если входной и выходной языки содержат цепочки длиной l < 3, то соответствие между
входными и выходными цепочками может быть описано, например, в виде перевода.
 

С = {(a,00),(b,01),(c,10),(d,11),(ab,0001),(ac,0010),

         (cd,0011),(bc,0110),(bd,0111),(cd,1011) }.

 

Конечные переводы с небольшим числом элементов можно задавать в виде перечислений. Однако, для задания больших конечных переводов и бесконечных переводов нужны такие
же средства задания как и для формальных языков. Рассмотрим случай , когда множество входных цепочек  (входной язык перевода С) можно задать с помощью грамматики Г и множества выходных цепочек (выходной язык перевода С) - с помощью грамматики Г'.
Примером такого задания может служить перевод, определяющий для каждой входной цепочки a ее зеркальное отображение a ". Если входной и выходной алфавиты состоят из двух символов - {0,1}, то правила построения такого перевода имеют вид:

        входные цепочки                      выходные цепочеки

1)          <I> ╝ 0<I>,                                 <I> ╝ <I>0
2)          <I> ╝ 1<I>,                                 <I> ╝ <I>1
3)          <I> ╝ $,                                       <I> ╝ $

 
Применяя одновременно соответствующие правила  построения к входной и выходной цепочкам, получаем:

(<I>,<I>) ==> (0<I>,<I>0) ==> (00<I>,<I>00) ==>  (001<I>,<I>100) ==> (001,100)

При таком построении существенное значение имеет заданное соответствие между правилами построения входных и выходных цепочек.

4.1.1.  Синтаксически  управляемые  схемы.

Обобщением рассматриваемого способа задания перевода  с помощью двух грамматик является понятие СУ - схемы, которое может быть определено следующим образом. 
 

Определение. Схемой синтаксически управляемого перевода (СУ-схемой)   называется совокупность пяти  объектов: 
 

                T = {Va,Vтвх,Vтвых,Q,<I>}, 

где Va - множество  нетерминальных символов, 
      Vтвх- множество терминальных символов,  используемых для построения 
                входных цепочек, 
       Vтвых- множество терминальных символов,  используемых для построения 
                   выходных цепочек, 
       <I>-начальный символ, <I> Î Va, 
         Q - множество правил вида   <A> ╝ a ,b, 
                 где <A> принадлежит Va, a Î(Va U Vтвх)*,  b Î (Va U Vтвых)* и 
                 нетерминалы,  входящие в цепочку b образуют перестановку 
                 нетерминалов цепочки a . 

Из приведенного определения следует, что каждое правило СУ- схемы должно включать цепочку, построенную из символов входного алфавита и нетерминальных символов, и цепочку, построенную из символов выходного алфавита и нетерминальных символов, и что в эти цепочки должны входить одни и те же нетерминалы. То обстоятельство, что основой СУ - схемы являются две грамматики, устанавливается следующим определением:

Определение. Если T = {Va,Vтвх,Vтвых,Q,I} СУ-схема,  то грамматика 
                                         Г = {Va,Vтвх,R, I}, 
                        где R = {<A> ╝ a |<A> ╝ a ,b принадлежит Q}, 
                        называется входной грамматикой  СУ-схемы Т, а грамматика 
                                          Г'={Va,Vтвых,R',I}, 
                        где R' = {<A> ╝ b | <A> ╝ a ,b принадлежит Q} 
                        называется выходной грамматикой СУ-схемы Т. 

С помощью СУ - схемы можно строить пары соответствующих цепочек. Такое построение называется выводом СУ -схемы, а получаемые пары цепочек - выводимыми парами.

Определение. Парой, выводимой с помощью заданной  СУ-схемы, называют любую  пару, которая может быть построена с применением  следующих правил: 
    1) (<I>,<I>) - выводимая пара, 
    2) если (a <A>b ,a '<A>b ') - выводимая пара и  выделенные нетерминалы соответствуют друг другу и в Q существует правило <A>╝g ,g ', то 
        (ag b , a 'g 'b ') является выводимой парой.

        Это записывается так:

                    (a <A>b ,a '<A>b ') ==> (ag b ,a 'g 'b ').

Последовательность выводимых пар обозначим как прежде:

                        (a <A>b ,a '<A>b ') ==>*  (wm p ,w 'm 'p ').

4.1.2.  Перевод, определяемый СУ-схемой.

С помощью понятия выводимая пара можно определить перевод, задаваемый СУ - схемой.

 
Определение. 
Переводом С(T), определяемым СУ-схемой  Т назовем множество пар, состоящих из входной   и выходной цепочек, выводимых из пары,   включающей два начальных символа. 

 С(T) = {(a ,b ) | (<I>,<I>) ==>* (a ,b ) и  a Î Vтвх*, b Î Vтвых*} 
 

В качестве примера рассмотрим СУ-схему, заданную следующим образом:

 T4.1:   Va = {<I>,<A>}, Vтвх = {0,1},Vтвых = {a,b}

              Q = {  <I> ╝ 0<A><I>,   <I><A>a;
                         <A> ╝ 0<I><A>,  <A><I>a;
                         <I> ╝ 1,   b;
                         <A> ╝ 1,  b
                     }.

Эта схема определяет перевод, входные слова которого состоят из нулей и единиц, а выходные из букв а,b. Нулям входной цепочки должны соответствовать буквы a, а единицам - буквы b выходной цепочки, причем расположение символов в выходной цепочке должно быть
зеркальным по отношению к соответствующим символам входной цепочки. Вывод в рассматриваемой СУ - схеме может, например, иметь вид:
 

(<I>,<I>) ==> (0<A><I>,<I><A>a) ==> (0<A>0<A><I>,<I><A>a<A>a) ==>

==>(0<A>00<I><A><I>,<I><A><I>aa<A>a)==>*==>*(0100111,bbbaaba)

4.1.3.  Простая СУ - схема.

Приведенное определение СУ - схемы не накладывает никаких ограничений на правила, кроме необходимости совпадения нетерминалов во входной и выходной частях правила. Для построения детерминированных устройств, осуществляющих перевод цепочек, используются СУ - схемы с дополнительными ограничениями на вид правил, которые определяются так.
 

 
Определение. 
СУ-схема Т = {Va,Vтвх,Vтвых,Q,I} называется  простой, если для  каждого правила  <A>╝a ,b из Q соответствующих друг 
 другу вхождения нетерминалов встречаются в  a и b в одном и том же  порядке. 


 

Определение. 
Перевод называется простым СУ-переводом,  если он определяется 
простой СУ-схемой. 

В качестве примера простой СУ - схемы, приведем СУ - схему Т4.2, которая задает перевод в виде множества постфиксных и соответствующих им инфиксных выражений.
 

T4.2: Va = {E,T,F}, Vтвх = {+,*,a}, Vтвых = {+,*,a,(,)}

         Q = {  E ╝ ET+ , E+T;     E╝T , T;
                    T╝TF* , T*F;    T╝F , F;

                                                   F╝E , (E);  F╝a , a; }.
 

Вывод в этой СУ - схеме, выполняемый путем применения правил к самым левым нетерминалам промежуточных цепочек, имеет вид:
 

(E,E) ==> (T,T) ==> (TF*,T*F) ==> (FF*,F*F) ==>(aF*,a*F) ==> (aE*,a*(E)) ==>

(aET+*,a*(E+T))==> ==> (aTT+*,a*(T+T)) ==> (aFT+*,a*(F+T)) ==>

==> (aaT+*,a*(a+T)) ==> (aaF+*,a*(a+F)) ==> ==>  (aaa+*,a*(a+a))

Другим примером простой СУ - схемы может служить СУ - схема Т4.3, которая задает перевод инфиксных выражений в постфиксные польские выражения.
 

T4.3: Va = {E,T,F}, Vтвх = {a,+,*,(,)}, Vтвых = {a,+,*}.

Q =  {   E╝E+T, ET+; E╝T,T;
             T╝T*F, TF*; T╝F,F;
              F╝(E), E; F╝a,a  }.

Вывод в приведенной СУ - схеме может иметь вид:
 

(E,E) ==> (E+T,ET+) ==> (T+T,TT+) ==> (F+T,FT+)==>  (a+T,aT+) ==> (a+T*F, aTF*+) ==>

(a+F*F,aFF*+) ==>  (a+a*F,aaF*+) ==> (a+a*a,aaa*+)
 

4.1.4.  Построение  простой СУ - схемы.

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

Г4. 1:    Vт = {x,+,(.)} Va = {A,B.C}

        R = {<A> ╝ x,
                 <A> ╝ (<B>),
                 <B> ╝ <A><C>,
                 <C> ╝ +<A><C>,
                 <C> ╝ $
               }

Учитывая, что выходные выражения не должны содержать скобок, находим, что   Vтвых = {x',+'}.
Первое правило грамматики содержит один входной терминал, поэтому правило СУ - схемы можем записать в виде:
 

       <A> ╝ x , x' .

Третье правило грамматики не содержит терминалов, поэтому получаем:
 

<B> ╝ <A><C>,<A><C> .

Пятое правило является аннулирующим, поэтому оно должно сохраниться в выходной грамматике

   <C> ╝ $ , $ .

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

   <A> ╝ (<B>),<B> .

При построении правила СУ - схемы по четвертому правилу грамматики следует учесть, что знак сложения в постфиксной записи должен следовать за вторым опреандом, который вводится в выражение нетерминалом А, следовательно получаем правило СУ - схемы в виде:
 

  <A> ╝ +<A><C>, <A>+'<C> .

Объединяя построенные правила, находим множество правил искомой СУ - схемы:
 

Т4.4: Q   =  {<A> ╝ x,x',
                     <A> ╝ (<B>),<B>,
                     <B> ╝ <A><C>, <A><C>,
                     <C> ╝ +<A><C>, <A>+'<C>,
                     <C> ╝ $, $}.

Чтобы в первом приближении убедиться в правильности построения СУ - схемы, выполним вывод входной цепочки ((x+x)+x) и соответствующей ей выходной цепочки, используя
построенные правила.

(<A>,<A>) ==> ((<B>),<B>) ==> ((<A><C>),<A><C>) ==> (((<B>)<C>,<B><C>) ==>

(((<A><C>)<C>),<A><C><C>) ==>(((x<C>)<C>),x<C><C>) ==> (((x+<A><C>),x'x'+'<C><C>) ==>

(((x+x+<C>)<C>), x'x'+'<C><C>) ==> (((x+x)<C>),x'x'+'<C>)  ==> (((x+x)+<A><C>),x'x'+'<A>+'<C>)

==> (((x+x)+x<C>),x'x'+'x'+'<C>) ==> (((x+x)+x),x'x'+'x'+').

Полученный результат показывает, что постфиксная запись для рассматриваемой входной цепочки построена правильно.
 

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