Главная Промышленная автоматика.

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

(1) h(a)a, если а принадлежит S, но не является буквой греческого алфавита;

(2) h(a) определяется табл. 3.1, если й -греческая буква.

Например, переводом предложения алг будет цепочка

Таблица 3.1

греческая буква

Е s 24

I ь

М \1

греческая буква

alpha beta

iIIj

gamma delta

0 0 П я

epsiJon zeta

- Pp 2 о

theta

iota

kappa lambda -

Q. u)

omicron

pi rho Sigma tau

upsiion phi chi psi

omega

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

Определение. Запись обычных (или -инфиксных) арифметических выражений без использования скобок называют польской (бесскобочной) записью). Пусть 0 - множество знаков бинарных операций (например, {-\-, *}) и 2 - множество операндов. Определим рекурсивно две формы польской записи, префиксную и постфиксную:

(1) Если инфиксное выражение Е является единственным операндом а€2, то как префиксная, так и постфиксная польские записи выражения Е - это просто а.

(2) Если EfiE - инфиксное выражение, где G-знак операции, а и Е-инфиксные выражения, операнды для 9, то

(а) E[Ez - префиксная польская запись выражения ЕЕ, где Е{ и Ez - префиксные польские записи выражений £j и £о соответственно;

) Этот метод впервые описал польский математик Лукасевнч, фамилию которого произнести труднее, чед1 слово „польская".

зл. Формализмы.используемые для определения перевода

(б) EEl - постфиксная польская запись выражения EfiE, где El и El-постфиксные польские записи выражений Pj и £"з соответственно. (3) Если (£)-инфиксное выражение, то

(а). префиксная польская запись выражения (Е) - это префиксная польская запись выражения £; (б) постфиксная польская запись выражения (Е)-это постфиксная польская запись выражения Е.

Пример 3.2. Рассмотрим инфиксное выражение (a-\-b)v!C. Это выражение вида ЕЕ, где Е(а~\-Ь) н Ес: Тогда с-префиксная и постфиксная польская запись выражения Е. Префиксная запись выражения Е, т. е. выражения а + й, это -{-аЬ. Таким образом, префиксной записью выражения (а\-Ь)*с является и-{-аЬс.

Аналогично постфиксной записью выражения g + 6 будет аЬ+, а постфиксной записью выражения (g+ й) *с будет аЬ-\-С9. □

От префиксного или постфиксного выражения можно однозначно вернуться к инфиксному выражению. Это не совсем очевидно, но можно доказать, используя упр. 3.1.16 н 3.1.17.

а >

Рис. 3.1. Древовидное представление выражения (a-f6)*c.

Арифметические выражения удобно представлять с помощью деревьев. Представление выражения (а-{-Ь)*с в виде дерева показано на рис. 3.1. В этом дереве каждая внутренняя вершина помечена знаком операции из множества в, а каждый лист - операндом из 2. Префиксная польская запись-это просто левое скобочное представление дерева, из которого удалены все скобки. Аналогично постфиксная польская запись -это правое скобочное представление дерева, из которого удалены все скобки.

Два важных примера переводов-множества пар

{{х> у) 1 X-инфиксное выражение и у-префиксная (постфиксная) запись выражения х}

Эти переводы нельзя задать с помощью гомоморфизмов. Нужны более Мощные способы задания переводов, и мы займемся теперь формализмами, позволяющими удобно описывать эти и другие переводы.



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

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

Назовем устройство, которое но данной входной цепочке х вычисляет такую выходную цепочку у, что {х, у)£Т, транслятором, реализующим перевод Т. Хотелось бы, чтобы определение перевода обладало „хорошими" евойствами, в частности такими:

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

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

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

(!) эффективность трансляции -время, необходимое для обработки входной цепочки w длины п линейно зависит от

(2) небольшой объем,

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

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

Пример 3.3. Рассмотрим схему, определяющую перевод {(х, х) I х€ {О, l}*} (для каждого входа х выходом служит обращенная цепочка) по правилам, выписанным в табл. 3.2.

В переводе, определяемом этой схемой, пару вход-выход можно получить, порождая последовательность выводимых пар

цепочек (а, Р), где а - входная выводимая цепочка* ар - выходная выводимая цепочка. Начинается последовательность парой (5, 5). Затем к этой паре можно применить первое правило. Тогда первое 5 заменяется на 05 по правилу 5-05, а второе 5 заменяется на 50 в соответствии с элементом перевода

Таблица 3.2

Правило

Элемент перевода

(1) sos

(2) S -IS

(3) Se

5 - 50. Пока можно рассматривать этот элемент перевода просто как правило 5---50. Так получается выводимая пара (05, 50). Снова применяя правило (1) к символу 5 в этой новой паре, получаем (005, 500). Затем правило (2) дает (0015, 5100). Если здесь применить правило (3), то будет (001, 100). К последней паре никакого правила применить нельзя, и потому она принадлежит переводу, определяемому этой схемой. □

Схема трансляции Т определяет некоторый перевод t{T). По схеме Г можно построить транслятор, реализующий перевод т(Т), который работает так. По данной входной цепочке х с помощью правил схемы трансляции транслятор находит (если это возможно) некоторый вывод цепочки х из 5. Допустим, что S - azazaz ... =р а„ = х -такой вывод. Затем транслятор строит вывод

(«о, Po)=(ai, Pi)= . =(а„, Р„)

состоящий из выводимых пар цепочек, для которого (а, р) = (5, 5), (а, Р) = (х, (/) и каждая цепочка р,- получается из p,- i с помощью элемента перевода, соответствующего правилу, примененному в надлежащем месте при переходе от а. к а,-. Цегючка у служит выходом .для цепочки х.

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

Пример 3.4. Рассмотрим схему перевода, отображающую арифметические выражения из языка L (Сд) в соответствующие постфиксные польские запнсн. Она изображена в табл. 3.3. = fr л" Я -i- £ + Г соответствует элемент перевода Е = мь1й элемент говорит о том, что перевод, порождае-

снмволон Е, стоящим в левой части правила, получается



из перевода, порождаемого символом Я, стоящим в правой части правила, за которым идут перевод, порождаемый символом Т, и знак +.

Определим выход, соответствующий входу а + Для этого сначала по правилам схемы перевода найдем левый вывод це-

Таблица 3.3

Правило

Элемент перевода

-Е + Т

Е = ЕТ +

T = TF*

T = F

->{Я)

ПОЧКИ а-ат иэ,5. Затем вычислим соответствующую последовательность выводимых пар цепочек:

(Л, Е){Е + Т,ЕТ + ) (ТТ, TT-h) (F~{-T,FT + ) (a + r, аГ + ) z(a + TF, aTF +) z{a-{-FF,aFF-) (a + a*P, aaP* + ) = (a + aa, aaa* +)

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

Схемы перевода в примерах 3.3 и 3.4 относятся к важному классу схем, называемых схемами синтаксически управляемого перевода.

Определение. Схемой синтаксически управляемого перевода (или трансляции) (сокращенно СУ-схемой) называется пятерка Г-= (N, 2, Д, R, 5), где

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

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

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

(4) -конечное множество правил вида Л ->-а, р, где a(Nij2)*, Pe(NUA)* и вхождения нетерминалов в цепочку р образуют перестановку вхождений нетерминалов в цепочку а,

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

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

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

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

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

Если между парами (аЛр, аЛр) и (аур, аур) с учетом соответствия их нетерминалов установлена описанная выше связь, то будем писать (аЛр, аЛр)=?>г («тР, ауР)- Транзитивное замыкание, рефлексивно-транзитивное замыкание и k-ю степень отношения =>j. будем обозначать =4>7, н =7 соответственно. Когда можно, будем опускать индекс Т.

Переводом, определяемым схемой Т (обозначается т(Т)), называют множество пар

{(X, у) 1(5, 5)Цх, у), и г/€Д*}

Пример 3.5. Рассмотрим СУ-схему "Г = ({5}, {а, -{-}., {а, +}, °> 5), где R состоит из правил

S-»-а, а





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 [40] 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0031