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

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

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

1. ?- конечное множество символов перевода вида Ai, где
   
   и i - целое число;
2. R - конечное множество правил перевода вида A
   
   u, A1 = v1, ... , Am = vm, удовлетворяющих следующим условиям:
   1. 
      для 1
      
      j
      
      m,
   2. каждый символ, входящий в v1, . . . , vm, либо принадлежит ?, либо является
      
      , где B входит в u,
   3. если u имеет более одного вхождения символа B, то каждый символ Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B.

A

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

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

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

Пример 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 - что выражение продифференцировано. Формальная производная - это E2. Законы дифференцирования таковы:

d(f(x) + g(x)) = df(x) + dg(x) d(f(x) * g(x)) = f(x) * dg(x) + g(x) * df(x) d sin (f(x)) = cos (f(x)) * df(x) d cos (f(x)) = -sin (f(x))df(x) dx = 1 d0 = 0 d1 = 0

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

E E + T E1 = E1 + T1 E2 = E2 + T2 E T E1 = T1 E2 = T2 T T * F T1 = T1 * F1 T2 = T1 * F2 + T2 * F1 T F T1 = F1 T2 = F2 F (E) F1 = (E1) F2 = (E2) F sin (E) F1 = sin (E1) F2 = cos (E1) * (E2) F cos (E) F1 = cos (E1) F2 = - sin (E1) * (E2)


Рис. 5.1. 

F x F1 = x F2 = 1 F 0 F1 = 0 F2 = 0 F 1 F1 = 1 F2 = 0

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


Содержание раздела

---

---