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



     Денежные переводы Крым |     

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


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

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

  1. ?- конечное множество символов перевода вида Ai, где
    A \in N
    и i - целое число;
  2. R - конечное множество правил перевода вида A
    u, A1 = v1, ... , Am = vm, удовлетворяющих следующим условиям:

    1. A_j \in \Gamma
      для 1
      j
      m,
    2. каждый символ, входящий в v1, . . . , vm, либо принадлежит ?, либо является
      B_k \in \Gamma
      , где 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 , а также операции * и +.


Содержание  Назад  Вперед