2015-04-06
2173
Основой построения СУ -схем перевода является использование двух грамматик, с помощью которых осуществляется синхронный вывод входной и выходной цепочек. Построение транслирующих грамматик предполагает применение другого подхода, который предусматривает использование одной грамматики и разрешает включение как входных, так и выходных символов в каждое правило такой грамматики.
Транслирующей грамматикой (Т -грамматикой) называется КС-грамматика, множество терминальных символов которой разбито на множество входных символов и множество выходных символов, которые называются также символами действия.
Примером Т - грамматики может служить следующая грамматика:
Г4.1: Vтвх = {a,b,c}, Vтвых = {x,y,z}, Va = { 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}
Каждый символ или цепочка символов, заключенные в фигурные скобки, должны рассматриваться как единый символ, называемый символом действия. В общем случае цепочки символов, заключенные в фигурные скобки, можно интерпретировать как имена процедур, выполнение которых производит требуемый эффект на выходе. При описании перевода обычно предусматривают, что каждый символ действия представляет собой процедуру, осуществляющую передачу символа, заключенного в фигурные скобки, на выход. Когда нужно подчеркнуть, что используется такая интерпретация символов действия, то Т - грамматику называют грамматикой цепочного перевода.
Множество пар цепочек, выводимых с помощью правил заданной Т - грамматики, образуют перевод, определяемый этой грамматикой.
Последнее определение позволяет нам сделать вывод, что один и тот же перевод может быть задан как с помощью СУ - схемы, так и с помощью Т - грамматики. Эти два способа задания являются равноправными и, более того, они допускают преобразование друг в друга.
Возможность одного из таких преобразований устанавливается следующим утверждением.
Утверждение. Для каждой простой СУ-схемы Т можно построить транслирующую грамматику ГТ такую, что переводы, порождаемые СУ - схемой и Т - грамматикой, совпадают.
|
|
|
C(T) = C(ГТ)
Синтаксически-управляемые схемы и транслирующие грамматики позволяют задавать соответствия между цепочками входного и выходного языков, называемые переводом. Такие соответствия отражают структурные или синтаксические свойства входных и выходных цепочек, но возникают значительные трудности при попытках их использования для описания контекстно-зависимых условий или смысла конструкций - семантики языков программирования.
Для задания семантики применяются различные приемы: W -грамматики, венский метаязык, аксиоматический и денотационный методы, а также атрибутные транслирующие грамматики (АТ-грамматики).
Рассматриваемые в настоящем разделе АТ-грамматики отличаются от транслирующих грамматик тем, что символам грамматики приписываются атрибуты, отражающие семантическую информацию, а правилам грамматики сопоставляются правила вычисления значений атрибутов. Чтобы пояснить назначение атрибутов, приведем несколько примеров. Если входной язык предусматривает использование констант C, то в качестве атрибута константы можно взять ее значение. Условимся записывать значение константы за ее обозначением с разделителем в виде косой черты, например, C/5. Если в Т-грамматике используются операционные символы {сложить}, то в качестве атрибутов таких символов можно взять значения операндов и результата. Обозначая атрибуты символами x, y, z, операционный символ с атрибутами запишем в виде {сложить}/x/y/z.
В АТ-грамматиках используются атрибуты двух видов: наследуемые и синтезируемые. Значения наследуемых атрибутов определяются при выполнении очередного шага вывода по значениям атрибутов цепочки, содержащихся в левой части правила грамматики. Вычисление значений синтезируемых атрибутов может откладываться и определяться при выполнении последующих шагов вывода. В общем виде свойства АТ-грамматик могут быть сформулированы следующим образом.
Транслирующую грамматику называют атрибутной грамматикой или АТ-грамматикой если:
1. Символам грамматики приписаны один или несколько атрибутов и для каждого атрибута определено множество допустимых значений.
2. Атрибуты могут быть наследуемыми и синтезируемыми.
3. Для каждого правила грамматики должны быть заданы правила вычисления атрибутов в виде оператора присваивания с функцией в правой части, определяющей значение атрибута, расположенного слева. Такие функции для вычисления атрибутов могут зависеть от атрибутов правой или левой частей рассматриваемого правила.
4. Для наследуемых атрибутов начального символа должны быть заданы начальные значения.
5. Функции, вычисляющие значения синтезируемых атрибутов символов действия, должны зависеть от других атрибутов этого символа.
