Описание перевода или трансляции. Синтаксически – управляемые (СУ) – схемы. Перевод, определяемый СУ – схемой. Построение простой СУ – схемы

В общем случае перевод или трансляцию можно представить как соответствие между словами алфавита Р и алфавита 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)

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

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

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

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 ').

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

Переводом С(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)

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

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

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

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

состоящие только из нетерминалов, оказываются одинаковыми во входной и выходной грамматиках.

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

Г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'+').

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