гл. 3- ТЕОРИЯ ПЕРЕВОДА

И рассмотрим вывод

т(Г) = {(х, a(+a))h"0 и х~префнкспая польская запись выражения а{-[-аУ с некоторым заданным порядком выполнения операций +}. □

Определение. Если r--(N. S, Д, 5)-СУ-схема, то т(Г) называется синтаксически управляемым переводом (СУ-перево-дом). Грамматика G.-=(N, S, Р, S), где Р{Л-а Л сс, р принадлежит R}, называется входной грамматикой СУ-схемы Т. Грамматика G = (N, Д, Р\ 5), где Р= {Л -»-р Л -а, р принадлежит R\, называется выходной грамматикой схемы Т).

Синтаксически управляемый перевод можно трактовать еще по-другому, считая его методом преобразования деревьев выводов входной грамматики в деревья выводов выходной грамматики G, Перевод дайной входной цепочки х можно получить, построив ее дерево вывода, затем преобразовав это дерево в дерево вывода в выходной грамматике и, наконец, взяв крону выходного дерева в качестве перевода цепочки х.

Алгоритм ЗЛ. Преобразование деревьев посредством СУ-схемы.

Вход. СУ-схема r(N, S, Д, R, S) с входной грамматикой G,- -(N. S, Pi, S) к выходной грамматикой G(N, Д, Р, S) и дерево вывода О в Gj- с кроной, принадлежащей 2*.

Выход. Некоторое дерево вывода D в G, такое, что если х и у-кроны деревьев D и D соответственно, то {х, у)£{Т).

Метод.

(1) Применять шаг (2)-рекурсивно, начиная с корня дерева D.

(2) Пусть этот шаг применяется к вершине п, внутренней в дереве D, и пусть п,, . .ее прямые потомки.

(а) Устранить из множества вершин п, ...,n листья (т. е. вершины, помеченные терминалами или е).

(б) Пусть Л-а-правило грамматики G,., соответствующее вершине п и ее прямым потомкам, т. е. Л-метка вершины п и а образуется конкатенацией меток вершин

..., п. Выбрать из R некоторое правило вида Л-на, р-).

) Здесь нижние индексы i и о - первые бзквы слов input (вход) и output (йы.ход).- Прим. ред.

) Заметим, что может определяться по 4 и а не единственным образом. Если подходящих правил несколько, то выбор произволен.

3.1. ФОРМАЛИЗМЫ. ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПСРЕВОДЛ

Переставить оставшихся Прямых потомков вершины п (если они есть) согласно соответствию между вхождениями нетерминалов в а и (Поддеревья, корнями которых служат эти потомки, переставляются вместе с ними.)

(в) Добавить в качестве прямых потомков вершины п листья с метками так, чтобы метки всех ее прямых потомков образовали цепочку р.

(г) Применить шаг (2) к прямым потомкам вершины я, не являющимся листьями, в порядке слева направо.

3) Результирующим деревом будет D. □

. Пример 3.6. Рассмотрим СУ-схему T = {{S, А}, {а, Ъ),

R, S), где R состоит нз правил

SOAS, SAa Л05Л, ASa Sl. Ь Л-1, b

На рис. 3.2,0 показано дерево вывода во входной грамматике. Применение к корню этого дерева шага (2) алгоритма 3.1

А S

/\\\

Q S А i

\\ \\

1 О S А

Рис, 3.2. Применение алгоритма 3.1.

устраняет левый лист, помеченный 0. Далее, так ка. корню соответствует правило 5"->0Л5 и у этого правила только один элемент перевода SAa, нужно поменять местами оставшихся прямых потомков корня. Затем надо добавить в самой правой позиции третьего прямого потомка, помеченного а. Результатом будет дерево, показанное на рис. 3.2,6.

Снова Применим шаг (2) уже к первым двум потомкам корня. Применение шага (2) ко второму из них приводит еще к двукратному повторению шага (2). Окончательный результат показан на рис. 3.2,6. Заметим, что (00111, bbbaa)x(T). □

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

Теорема 3.1. (1) ЕЬли х и у-соответственно кроны деревьев D и D из алгоритма 3.1, то (х, у)т:(Т).

(2) Если (х, у) С т (7"), то существуют дерево вывода D с кроной X и такая последовательность выборов при обращении к шагу (26) что в результате получается дерево D с кроной у.

Доказательство. (1) Индукцией по числу внутренних вершин дерева Е докажем, что

(3.1.1) если Е-дерево вывода в С,- с кроной х и корнем, помеченным Л, и применение к £ шага (2) дает дерево Е с кроной у, то (Л, Л)=*(х, f/).

Базис (дерево, содержащее одну внутреннюю вершину) - тривиален. Все прямые потомки являются листьями, н в /? должно быть правило Л-х, у.

Для доказательства шага индукции допустим, что утверждение (3.1.1) верно для деревьев с меньшим числом внутренних вершин и корень дерева Е имеет прямых потомков с метками Xj, ...,Xj. Тогда x==x,...X/j, где Ху=>с.лу для 1 /А. Пусть

прямые потомки кормя дерева Е помечены Kj, K. Тогда у = у...у, где Yj*Qyj для 1 , Кроме того, в R есть правило ЛA"i... Ki...K/.

Если Xj - нетерминал, то ему соответствует некоторый символ Ур =Xj. По предположению индукции (Xj, Хр j Ху,Ур у

Так как шаг (26) приводит к перестановке вершин, то

(Л, Л)=Ф (Х,.,.Х,, Kj...K,)-=Ф*(хЛ...Х„ aS>...aii>)

=4>*(л1-.-й. ...af)

(/у, если KyGN и соответствует одному из Xj, Yj в противном случае.

Таким образом, утверждение (3.1.1) справедливо. Часть (2) теоремы-это частный случай следующего утверждения:

(ЗЛ.2) если (Л, А)=(х, у), то существуют дерево вывода D ъ G; с корнем, помеченным Л> и кроной X н такая последовательность выборов при обращении к шагу (26), что применение шага (2) к дереву D дает дерево с кроной у.

(1) Е-

(2) Е-

(3) Е-

(4) Г-

(5) Т.

(6) Т-

(7) Л.

(8) Л-

~Е + Е, -Л

Л »л,

-(£+£),

Е + Е Т

А%А а

(Е + Е) Т

Например, для выражения ((a-f (а*а))*а) эта СУ-схема дает "еревод (а + а*а)»а). □

) Заметим, что входная грамматика неоднозначна, но каждой «ходиоЙ Цепочке соответствует точно одна выходная.

Доказательство этого утверждения индукцией по / оставляем в качестве упражнения. □

Заметим, что порядок применений шага (2) алгоритма 3.1 к вершинам дерева не важен. Можно было бы выбрать любой порядок, при котором каждая внутренняя вершина рассматривается точно один раз. Проверку этого утверждения тоже оставляем в качестве упражнения.

Определение. СУ-схема 7 = (N, 2, Д, R, S) называется про-.стой, если для каждого правила Л->а, р из R соответствующие друг другу вхождения нетерминалов встречаются в а и р в одном и том же порядке. Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).

Все СУ-схемы в примерах 3.3-3.5 простые, а в примере 3.6-нет.

Соответствие нетерминалов в выводимой паре простой СУ-схемы самое простое, оно определяется порядком, в каком эти нетерминалы Появляются в цепочках.

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

Пример 3.7. Следующая простая СУ-схема отображает арифметические выражения из языка L(Gq) в арифметические выражения, не содержащие избыточных скобок:

3.1.3. Конечные преобразователи

Введем наш простейший транслятор - конечный преобразователь. Преобразователь - это просто распознаватель, выдающий на каждом такте выходную цепочку (она может быть и пустой). Конечный преобразователь получится, если конечному автомату (распознавателю) позволить выдавать на каждом такте цепочку выходных символов (рис. 3.3). В рзд. 3.3 мы будем пользо-

! 7да8лйющее память/о

Рнс. 3.3. Конечный преобразователь.

ваться конечным преобразователем как моделью лексического анализатора.

Для большей общности рассмотрим в качестве основы, конечного преобразователя недетерминированный конечный автомат, способный делать е-такты.

Определение. Конечным преобразователем называется шестерка M-(Q, 2, Д, б, q„ F), где

(1) Q - конечное множество состояний,

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

(3) Д-конечный выходной алфавит,

(4) б-отображение множества Qx(ll\j{e}) в множество конечных подмножеств множества QxA*,

(5) i7o С Q - начальное состояние,

(6) FQ-множество заключительных состояний.

Определим конфигурацию преобразователя М как тройку (q, X, у), где

(1) qQ - текущее состояние управляющего устройства,

(2) х ё S*-оставшаяся непрочитанной »мсть входной цепочки, причем самый левый символ цепочки х расположен под входной головкой,

(3) уё* - часть выходной цепочки, выданная вплоть до текущего момента.

Определим бинарное отношение (илн \-, когда ясно,

о каком М идет речь) на конфигурациях, соответствующее одному такту работы преобразователя М: для всех q£Q,a£2[j {е\, хЕ* и таких, что &{д, а) содержит (г, г), будем писать

(д, ах, у) Ь- (г, X, yz)

Обычным образом далее определяются 1-, и ]-+.

Цепочку- у назовем выходом для цепочки х, если / (д- с, у) для некоторого q£F. Переводом, определяемым

преобразователем М (обозначается т(Л1)), назовем множество {(л:, У) too. ) Ь-*(. у) для некоторого qF). Перевод, определяемый конечным преобразователем, будем называть регулярным переводом или конечным преобразованием.

Заметим, что для того, чтобы выходную цепочку у можно было считать переводом входной цепочки х, цепочка х должна перевести преобразователь М из начального состояния в заключительное.

Пример 3.8. Построим конечный преобразователь, который распознает арифметические выражения, порождаемые правилами

5-а + 5а -5 + 5~5а

и устраняет из этих выражений избыточные унарные операции.

Например, выражение - а-\--а--j--а он переведет в

- а-аа. Во входном языке символ а представляет идентификатор и перед идентификатором допускается произвольная последовательность знаков унарных операций + и -. Заметим, что входной язык является регулярным множеством. Пусть M = (q, 2, Д, б, q„ f), где

(1) Q = {?o, Яи Я2, Яз, Яа\, (2)2(а, +,-},

(3) Д=-Л,

(4) б определяется диаграммой, изображенной на рис. 3.4; метка х/у на дуге, ведущей из вершины, помеченной q, в вершину, помеченную о,-, указывает, что б (о-, х) содержит {q, у),

(5) f = {<?,}.

Преобразователь М начинает работу в состоянии q и, чередуя состояния и q на входном символе -, определяет, четное или нечетное число знаков - предшествует первому символу а. Когда появляется а, преобразователь М переходит в состоя-Я1 допуская вход, и выдает а или -а в зависимости от того, четно или нечетно число появившихся минусов. Для следующих символов а он подсчитывает, четно или нечетно число предшествующих минусов, с помощью состояний q и q. Един-