Теория и реализация языков программирования

         

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


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

Определение. Обобщенной схемой синтаксически управляемого перевода (или трансляции, сокращенно: 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.


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