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

         

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


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

(1) N - конечное множество нетерминальных символов;

(2) T - конечный входной алфавит;

? - конечный выходной алфавит;

R - конечное множество правил перевода вида

где

и вхождения нетерминалов в цепочку v образуют перестановку вхождений нетерминалов в цепочку u, так что каждому вхождению нетерминала B в цепочку u соответствует некоторое вхождение этого же нетерминала в цепочку v; если нетерминал B встречается более одного раза, для указания соответствия используются верхние целочисленные индексы;

(5) S - начальный символ, выделенный нетерминал из N.

Определим выводимую пару в схеме Tr следующим образом:

(1) (S, S) - выводимая пара, в которой символы S соответствуют друг другу;

(2) если (xAy; x'Ay') - выводимая пара, в цепочках которой вхождения A соответствуют друг другу, и A

u, v - правило из R, то (xuy; x'vy') - выводимая пара. Для обозначения такого вывода одной пары из другой будем пользоваться обозначением
: (xAy, x'Ay')
(xuy, x'vy'). Рефлексивно-транзитивное замыкание отношение
обозначим
*.

Переводом ? (Tr), определяемым СУ-схемой Tr, назовем множество пар

Если через P обозначить множество входных правил вывода всех правил перевода, то G = (N, T, P, S) будет входной грамматикой для Tr.

СУ-схема Tr = (N, T, ?, R, S) называется простой, если для каждого правила A

u, v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке.

Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).

Пример 5.2. Перевод арифметических выражений в ПОЛИЗ (польскую инверсную запись) можно осуществить простой СУ-схемой с правилами

E
E + T
ET+
E
T
T
T
T * F
TF+
T
F
F
F
id
id
F
(E)
E.

Найдем выход схемы для входа id * (id + id). Нетрудно видеть, что существует последовательность шагов вывода

переводящая эту цепочку в цепочку id id id + *.

Рассмотрим связь между переводами, определяемыми СУ- схемами и осуществляемыми МП-преобразователями [2].



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