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

Определение. 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].

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