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

Расширим определение СУ-схемы, с тем чтобы выполнять

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

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

, , R, S), где все символы имеют тот же смысл, что и для СУ-схемы, за исключением того, что

• 
  - конечное множество символов перевода вида Ai, где A
  
  N и i - целое число;
• R - конечное множество правил перевода вида

  A

  
  u, A1 = v1, ..., Am = vm,

  удовлетворяющих следующим условиям:

• Aj
  
  
  для 1
  
  j
  
  m,
• каждый символ, входящий в v1, ..., vm, либо принадлежит
  
  , либо является Bk
  
  
  , где B входит в u,
• если 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)
F x	F1 = x
	F2 = 1
F 0	F1 = 0
	F2 = 0
F 1	F1 = 1
	F2 = 0

 

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

Рис. 5.1:

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

---