Определение. Cхемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка Tr = (N, T, ?, R, S), где
(1) N - конечное множество нетерминальных символов;
(2) T - конечный входной алфавит;
? - конечный выходной алфавит;
R - конечное множество правил перевода вида
где
(5) S - начальный символ, выделенный нетерминал из N.
Определим выводимую пару в схеме Tr следующим образом:
(1) (S, S) - выводимая пара, в которой символы S соответствуют друг другу;
(2) если (xAy; x'Ay') - выводимая пара, в цепочках которой вхождения A соответствуют друг другу, и A
Переводом ? (Tr), определяемым СУ-схемой Tr, назовем множество пар
Если через P обозначить множество входных правил вывода всех правил перевода, то G = (N, T, P, S) будет входной грамматикой для Tr.
СУ-схема Tr = (N, T, ?, R, S) называется простой, если для каждого правила A
Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).
Пример 5.2. Перевод арифметических выражений в ПОЛИЗ (польскую инверсную запись) можно осуществить простой СУ-схемой с правилами
E ![]() | ET+ |
E ![]() | T |
T ![]() | TF+ |
T ![]() | F |
F ![]() | id |
F ![]() | E. |
Найдем выход схемы для входа id * (id + id). Нетрудно видеть, что существует последовательность шагов вывода
переводящая эту цепочку в цепочку id id id + *.
Рассмотрим связь между переводами, определяемыми СУ- схемами и осуществляемыми МП-преобразователями [2].