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

---

4.2.  Транслирующие грамматики

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

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

Примером Т - грамматики может служить следующая грамматика:

Г_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}

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

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

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

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

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

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

4.2.2.  Построение транслирующей грамматики по  СУ - схеме.

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

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

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

C(T) = C(Г_Т) 

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

Т = {V_твх, V_твых,V_a,Q,I}

и требуется построить Т - грамматику

                                                      Г~ = {V'_твх,V'_твых,V'_a,R,I}.

Для того чтобы получить тот же самый перевод, необходимо, чтобы

V_твх = V_твх', V_твых = V_твх', V_a = V_a'.

Рассмотрим преобразование правила из множества Q СУ - схемы   A╝a ,b , где цепочки

a = x_оA_ох₁А₁...x_nA_n  и    b = y_оA_оу₁A₁...у_nA_n,

и поставим в соответствие этому правилу правило грамматики в виде:

А ╝ x_оу_оA_ох₁у₁A₁...x_ny_nA_n.

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

Г_4.1:

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

Перевод цепочки ((x+x)+x) с применением правил построенной грамматики может быть получен с помощью следующего вывода:

<A> ==> <A><C> ==> (<B>)<C> ==> (<A><C>)<C> ==>
((<B>)<C>)<C> ==> ((<A><C>)<C>)<C> ==> ((x{x}<C>)<C> ==> ((x{x}+<A>{+}<C>)<C>)<C> ==>
((x{x}+x{x}{+}<C>)<C>)<C> ==>((x{x}+x{x}{+})<C>)<C> ==>
((x{x}+x{x}{+})+<A>{+}<C>)<C> ==>
((x{x}+x{x}{+})+x{x}{+}<C>)<C> ==>
((x{x}+x{x}{+})+x{x}{+})<C> ==> ((x{x}+x{x}{+})+x{x}{+}).

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

((x+x)+x,{x}{x}{+}{x}{+}),

которая совпадает с результатом вывода в заданной СУ - схеме.

---

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