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



             

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


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

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

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

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

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

A \rightarrow u, v

где

u \in (N \cup T)^*, v \in (N \cup \Pi)^*
и вхождения нетерминалов в цепочку 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, назовем множество пар

\{(x, y) \mid (S, S) \Rightarrow^* (x, y), \; x \in T^*, y \in \Pi^*}

Если через 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). Нетрудно видеть, что существует последовательность шагов вывода

\begin{align*} &(E, E) \Rightarrow (T, T) \Rightarrow (T* F, TF*) \Rightarrow \\ &\Rightarrow (F * F, FF*) \Rightarrow (id * F, id \; F*) \Rightarrow (id * (E), id \; E*) \Rightarrow \\ &\Rightarrow(id * (E + T), \; id \; E T + *) \Rightarrow (id * (T + T), id \; T T + *) \Rightarrow \\ &\Rightarrow (id * (F + T), \; id \; F T + *) \Rightarrow (id * (id + T), id \; id T + *) \Rightarrow \\ &\Rightarrow (id * (id + F), id \; id F + * ) \Rightarrow\\ &\Rightarrow (id * (id + id), id \; id \; id + * \Rightarrow;\\ \end{align*}

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

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




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