Обобщенные схемы синтаксически управляемого перевода

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

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

1. - конечное множество символов перевода вида A_i, где и i - целое число;

2. R - конечное множество правил перевода вида A -> u, A₁ = v₁,..., A_m = v_m, удовлетворяющих следующим условиям:

1. для 1 < = j < = m,

2. каждый символ, входящий в v₁,..., v_m, либо принадлежит либо является , где B входит в u,

3. если u имеет более одного вхождения символа B, то каждый символ B_k во всех v соотнесен (верхним индексом) с конкретным вхождением B.

A -> u называют входным правилом вывода, A_i - переводом нетерминала A, A_i = v_i - элементом перевода, связанным с этим правилом перевода. Если в ОСУ-схеме нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной.

Выход ОСУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченнойA, свяжем одну цепочку для каждого A_i. Эта цепочка называется значением (или переводом) символа A_i в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода A_i = v_i, определенных в прямых потомках вершины n.

Переводом , определяемым ОСУ-схемой Tr, назовем множество {(x, y) | x имеет дерево разбора во входной грамматике для Tr и y - значение выделенного символа перевода S_k в корне этого дерева }.

Пример 5.4. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x, функцииsin и cos, а также операции * и +. Такие выражения порождает грамматика

E -> E + T | T

T -> T * F | F

F -> (E) | sin (E) | cos (E)|x|0|1

Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 - что выражение продифференцировано. Формальная производная - это E₂. Законы дифференцирования таковы:

Эти законы можно реализовать следующей ОСУ-схемой:

Рис. 5.1.

Дерево вывода для sin (cos (x)) + x приведено на рис. 5.1.