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

Проблема задания бесконечного перевода конечными средствами аналогична проблеме задания бесконечного языка. Известно несколько возможных подходов к определению переводов. Аналогично порождению языка с помощью грамматики можно использовать систему, порождающую пары цепочек, принадлежащие переводу. Можно также воспользоваться распознавателем с двумя лентами, распознающим пары, принадлежащие переводу, или же определить автомат, который принимает в качестве входа цепочку и выдает (недетерминированно, если нужно) все цепочки , являющиеся переводами цепочки . Этот список не исчерпывает всех возможностей, ко охватывает наиболее распространенные модели.

Назовем устройство, которое по данной входной цепочке вычисляет такую выходную цепочку , что , транслятором, реализующим перевод . Хотелось бы, чтобы определение перевода о6ладало «хорошими» свойствами, в частности такими:

1. в нем легко разобраться, т.е. легко установить, какие пары цепочек принадлежат переводу;

2. прямо по определению перевода можно механически построить эффективный транслятор, реализующий этот перевод.

Желательные качества трансляторов таковы:

1. эффективность трансляции — время, необходимое для обработки входной цепочки длины линейно зависит от ,

2. небольшой объем.

3. корректность — желательно иметь небольшой конечный тест, такой, что если транслятор прошел через него, то правильность работы транслятора гарантирована на всех входных цепочках.

Одним из формализмов, используемых для определения переводов, является схема синтаксически управляемого перевода (трансляции). Интуитивно такая схема представляет собой просто грамматику, в которой к каждому правилу присоединяется элемент перевода. Всякий раз, когда правило участвует в выводе входной цепочки, с помощью элемента перевода вычисляется часть выходной цепочки, соответствующая части входной це­почки, порожденной этим правилом.

Пример:

Рассмотрим схему, определяющую перевод (для каждого входа выходом служит обращенная цепочка) по правилам, приведенным в таблице.

Номер	Грамматика	Элемент перевода
1.
2.
3.

Решение:

В переводе, определяемом этой схемой, пару вход – выход можно получить, порождая последовательность выводимых пар цепочек , где – входная выводимая цепочка, а – выходная выводимая цепочка. Начинается последовательность парой . Затем к этой паре можно применить первое правило. Тогда первое заменяется на по правилу , а второе заменяется на в соответствии с элементом перевода . Пока можно рассматривать этот элемент перевода просто как правило . Так получается выводимая пара . Снова применяя правило (1) к символу в этой новой паре, получаем . Затем правило (2) дает . Если здесь применить правило (3), то будет . К последней паре никакого правила применить нельзя, и потому она принадлежит переводу, определяемому этой схемой.

Схема трансляции определяет некоторый перевод . По схеме можно построить транслятор, реализующий перевод , который работает так. По данной входной цепочке с помощью правил схемы трансляции транслятор находит (если это возможно) некоторый вывод цепочки из . Допустим, что – такой вывод. Затем транслятор строит вывод

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

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

Домашнее задание: Написать таблицу для префиксной и постфиксной формы записи для грамматики вида

.

Пример:

Построить последовательность перевода для цепочки .

Решение:

ч.

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

,

где

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

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

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

- конечное множество правил вида , где , , и вхождения нетерминалов в цепочку образуют перестановку вхождений нетерминалов в цепочку ;

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

Пусть - правило. Каждому вхождению нетерминала в цепочку соответствует некоторое вхождение того же нетерминала в цепочку . Если нетерминал входит в цепочку только один раз, то соответствие очевидно. Если входит более одного раза; то для указания соответствия мы будем пользоваться верхними целочисленными индексами. Это соответствие является (если оно явно не указано, то подразумеваемой) частью правила. Например, в правиле 1-й. 2-й и 3-й позиция цепочки соответствуют 2-я, 3-я и 1-я позиции цепочки .

Определим выводимую пару цепочек схемы:

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

2. если - выводимая пара, в которой два выделенных вхождения нетерминала соответствуют друг другу, и правило из , то - выводимая пара. Вхождения нетерминалов в и соответствуют друг другу точно так же, как они соответствовали в правиле. Вхождения нетерминалов в и соответствуют вхождениям нетерминалов в и в новой выводимой паре точно так же, как они соответствовали в старой выводимой паре. Когда надо, это соответствие будет указываться верхними индексами; оно составляет существенную часть выводимой пары.

Если между парами и с учетом соответствия их нетерминалов установлена описанная выше связь, то будем писать . Транзитивное замыкание, рефлексивно-транзитивное замыкание и -ю степень отношения будем обозначать и соответственно. Когда можно, будем опускать индекс .

Определение: Переводом, определяемым схемой (обозначается ) будем называть множество пар

.

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

Определение: СУ-схема называется простой, если для каждого правила соответствующие друг другу вхождения нетерминалов встречаются в и в одном и том же порядке.

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

Дата добавления: 2014-01-07