Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 50
Текст из файла (страница 50)
З.З. =Ет+, ° ПРавилу Е Е-)- Т соответствует элемент перевода Е = мый сима + Этот элемент говорит о том, что перевод, порождаесиыволом Е, стоящим в левой части правила, получается 247 ивлочск (а, р), где а — входная выводимая цепочка, а р — выходная выводимая цепочка.
Начинается последовательность парой (Я 5), Затем к этой паре можно применять первое правило. тогда первое Я заменяется на 05 по правилу Я 05, а второе 5 заменяется на 50 в соответствии с элементом перевода Гл. А. ТеОРия пеРеВОДА Таблица Л.Э Элемент оерееоде Полонно Е=ЕТ+ Е.=Т т=ТЕ Те Е Т=Е Я=а Š— е Е+Т Е вЂ” «Т Т вЂ” «Тор Т вЂ” РŠ— «(Е) Е а 248 из перевода, порождаемого символом Е, стоящим в правой части правила, за которым идут перевод, порождаемый символом Т, и знак +, Определим выход, соответствующий входу а+ а «а.
Для этого сначала по правилам схемы перевода найдем левый вывод це- почки а+а«а из 5. Затем вычислим соответствующую последовательность выводимых пар цепочек: (В, В) =Р(В+Т, ВТ+) =Р(Т+Т, ТТ+) =2 (Р+Т, РТ+) ~(а+Т, аТ+) =ь (а + Т «Р, аТР о + ) =ь(а+Р«Р, аРР«+) ~(а+а«Р, ааР «+) =ь (а + а «а, ааа «+ ) Каждая выходная цепочка этой последовательности получается нз предыдущей выходной цепочки заменой подходящего нетерминала правой частью элемента перевода, присоединенного к правилу, примененному при выводе соответствующей входной цепочки.
Схемы перевода в примерах 3.3 и 3.4 относятся к важному классу схем, называемых схемами синтаксически управляемого перевода. Определение. Схемой синтаксически управляемого перевода (или трансляции) (сокращенно СУ-схемой) называется пятерка Т = =(Х, Х, О, П, 5), где (1) г( — конечное множество нетерминальных символов, (2) Х вЂ” конечный входной алфавит, (3) Ь вЂ” конечный выходной алфавит, А «ФОРМАЛИЗМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА (4)  — конечное множество правил вида А — а, )), где аЕ(МОХ)', () ч(1А)() й)о и вхождениЯ нетеРмнналов в цепочкУ Р Образуют перестановку вхождений нетерминалов в цепочку а, (б) 5 — начальный символ, выделенный нетерминал из «н. Пусть А — а, () — правило.
Каждому вхождению нетерминала в цепочку а соответствует некоторое вхождение того же нетерминала в цепочку р. Если нетерминал В входит в цепочку а только один раз, то соответствие очевидно. Если В входит более одного раза, то для указания соответствия мы будем пользоваться верхними целочисленными индексами.
Это соответствие является (если оио явно не указано, то подразумеваемой) частью праввла. Например, в правиле А — В<««СВ'е«, В"'В"'С 1-й, 2-й и 3-й позиции цепочки Вел СВИВ соответствуют 2-я, 3-я и 1-я позиции цепочки В"'Во'С. Определим выводимую пару цепочек схемы Т: (1) (5, 5) — выводимая пара, в которой символы 5 соответствуют друг другу. (2) если (аАр, а'Ар') †выводим пара, в которой два выделенных вхождения иетерминала А соответствуют друг другу, и А — у, у' †прави из й«, то (ау)1, а'у'()') †выводим парэ. Вхождения нетерминалов в у и у' соответствуют друг другу точно так же, как они соответствовали в правиле.
Вхождения нетерминалов в а и р соответствуют вхождениям нетерминалов в а' и ))' в новой выводимой паре точно так же, как они соответствовали в старой выводимой паре. Когда надо, это соответствие будет указываться верхними индексами; оно спставляет существенную часть выводимой пары. Если между парами (аАр, а'Ар') и (ау(), а«у««1«) с учетом ответствия их нетерминалов установлена описанная выше связь, то будем писать (аАр, а'А(1')~г(ау(1, а'у'р'). Транзнтивное замыкание, рефлексивно-транзитивное замыкание и и-ю степень отношения =От будем обозначать Ог, — ->г и Х«ьг соответственно. Когда можно, будем опускать индекс Т. Переводом, определяемым схемой Т (обозначается т(Т)), называют множество пар ((х, у) ~(5, 5)=э'(х, у), хЕХ' и у~йе) ПРимер 3,3. Рассмотрим СУ-схему Т=((5), (а, -1-), (а, «-), Й, 5), где В состоит из правил 1 5«О5«м 5«1«1 5«е« 5- а, а гл.
3. теория пеРенодА з.!. ФОРМАЛИЗМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПСРЕНОДА и рассмотрим вывод (5 5) зал ( 1 5о)5!з! 5!з! ) 5зз!) ~(1 1 5зз!5зз)5уз! Уз! 1.5!з! ) 5зз!) =>(++а5!з!5!з! а-1-5"'+5!") =о(+ +аа5, а+а+5) ~(++ааа, а+а+а) т(Т) =((х, а(+а) )(1) 0 и х — -префимспая польская запись выражения а(+а)1 с некоторым заданным порядком выполнения операций +). П Определение. Если Т=--(Х, Х, Л, )с, 5) — СУ-схема, то т(Т) называется синтаксически управляемым переводом (СУ-переводом). Грамматика б, =(зч, Х, Р, 5), где Р=(А — а~ А — а, р принадлежит )с), называется входной гралзматикой СУ-схемы Т.
Грамматика 6.=(зч, Л, Р', 5), где Р'=(А- р)А- сс, б принадлежит зс), называется выходной граммитикой схемы Т'). Синтаксически управляемый перевод можно трактовать еще по-другому, считая его методом преобразования деревьев выводов входной грамматики 6; в деревья выводов выходной грамматики б,. Перевод данной входной цепочки х можно полчить, построив ее дерево вывода, затем преобразовав это дерево в дерево вывода в выходной грамматике и, наконец, взяв крону выходного дерева в качестве перевода цепочки х. Алгоритм 3.1. Преобразование деревьев посредством СУ-сх емы. Вход.
СУ-схема Т=(Х, Х, Л, 1(, 5) с входной грамматикой бз=(Ь), Х, Р„5) и выходной грамматииой 6,=(!(, Л, Р„5) и дерево вывода 0 в 6, с кроной, принадлежащей Х'. Выход. Некоторое дерево вывода В' в б„такое, что если х и у — кроны деревьев В и В' соответственно, то (х, у) Ет(Т).
Метод. (1) Применять шаг (2) рекурсивно, начиная с корня дерева 12. (2) Пусть этот шаг применяется к вершине и, внутренней в дереве (л, и пусть п„..., и„— ее прямые потомки. (а) Устранить из множества вершин п„...,пз листья (т. е. вершины, помеченные термнналамн или е). (б) Пусть А — сс — правило грамматики бз, соответствующее вершине и и ее прямым потомкам, т. е. А — метка вершины и и сс образуется конкатенацией меток вершин и„..., и„. Выбрать нз )с некоторое правило вида Л вЂ” сс, рз). з)зес н ) .д ь нжкке нндекеы ! н о — перные буквы слов 1лри1 (аход) н ои1- ри( (йылод).— Прим.
ред. з и. з) Заметны, ято б может определяться по А н а не едннетненны,об о . Есин подходящнх правил несколько, то ныбор пронзнолен. м, ра- 250 Переставить оставшихся прямых потомков вершины и (если они есть) согласно соответствию между вхождениями нетерминалов в а и (). (Поддеревья, корнями которых служат эти потомки, переставляются вместе с ними.) (в) Добавить в качестве прямых потомков верцшны и листья с метками так, чтобы метки всех ее прямых потомков образовали цепочку р. (г) Применить шаг (2) к прямым потомкам вершины и, не являющимся листьями, в порядке слева направо.
3) Результирующим деревом будет О'. Г) Пример 3.6. Рассмотрим СУ-схему Т =((5, Л), ()Р,' Ц, (а, Ь), 1(, 5), где )лз состоит нз правил / 5 — ОА5, 5Аа А — 05А„А5а 5- 1, Ь А 1„Ь На рис. 3.2, а показано дерево вывода во входной грамматике. Применение к корню этого дерева' шага (2) алгоритма 3,1 Ь Ь а б !з Рнс. 3.2. Прнменеане алгоритма 3.1. устраняет левый лист, помеченный О. Далее, там ка: корню соответствует правило 5-- ОА5 и у этого правила только один элемент перевода 5Ла, нужно поменять местами оставшихся "рямых потомков корня.
Затем индо добавить в салюй правой позиции третьего прямого потомка, помеченного а. Резуль~атом будет дерево, показанное на рис. 3.2„б. Снова применим шаг (2) уже к первым двум потомкам корня. Рименение шага (2) ко второму из них приводит еще к двуИРатному повторению и!ага (2). Окончательный результат показан на рис. 3.2,в. Заметим, что (00111, ЬЬЬаа) Ет(Т). П Чтобы установить связь между процессом перевода, осуществляемым алгоритмом 3.1, и Су-схемой, ко!оран служит входом этого того алгоритма, докажем следующую теорему.
25! ГЛ. 3. ТЕОРИИ пеРЕВОДА В ), ФОРМАЛИЗМЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕВОДА Теорема 3.1. (1) Если х и у — соответственно крона деревьев 0 и 0' из алгоритма 3.1, то (х, у) Е т(Т). (2) Если (х, у) Ет(Т), то существуют дерево вывода 0 с кроной х и такая последовательность выборов при обращении к шагу (2б), что в результате получается дерево В' с кроной у. Д о и а з а т е л ь с т в о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
