13. Описание перевода. Т-грамматики.

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

Определение. Если заданы входной алфавит P и выходной алфавит W, то переводом с языка Lвх, состоящего из цепочек множества P*, на язык Lвых, состоящий из цепочек множества W*, называется множество C пар цепочек ( , ) таких, что   Lвх и   Lвых. C={( , ) |   Lвх и   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) }. Конечные переводы с небольшим числом элементов можно задавать в виде перечислений. Однако, для задания больших конечных переводов и бесконечных переводов нужны такие же средства задания как и для формальных языков. Рассмотрим случай , когда множество входных цепочек (входной язык перевода С) можно задать с помощью грамматики Г и множества выходных цепочек (выходной язык перевода С) - с помощью грамматики Г'. Примером такого задания может служить перевод, определяющий для каждой входной цепочки  ее зеркальное отображение  ". Если входной и выходной алфавиты состоят из двух символов - {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: V_твх = {a,b,c}, V_твых = {x,y,z}, V_a = { I,A} R = {<I> ╝a<I>x<A>, <I> ╝z, <A> ╝<A><C>, <A> ╝by }.

Чтобы не возникало путаницы в случае использования одинаковых символов во входном и выходном алфавитах, условимся выделять выходные символы фигурными скобками. С использованием таких обозначений правила грамматики Г_Т4.1 имеют вид: R = {<I>╝a<I>{x}<A>, <I>╝{z}, <A>╝<A>c, <A>╝b{y} }.

Вывод в транслирующих грамматиках выполняется по тем же правилам, что и в обычных КС - грамматиках. Например, в рассматриваемой грамматике из начального символа может быть выведена следующая цепочка: <I> ==> a<I>{x}<A> ==> a{z}{x}<A> ==> a{z}{x]b{y}

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

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

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

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

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

Определение. Если из цепочки символов  , полученной путем вывода в заданной Т -грамматике , исключим все выходные символы, то получим цепочку 1, которую назовем входной цепочкой. Если же из цепочки  исключим все символы входного алфавита, то в результате получим цепочку 2, которую назовем выходной цепочкой, порождаемой Т - грамматикой . Цепочки 1 и 2 образуют пару, выводимую в заданной Т - грамматике.