Главная » Просмотр файлов » Карпов - Основы построения трансляторов (2005)

Карпов - Основы построения трансляторов (2005) (943926), страница 19

Файл №943926 Карпов - Основы построения трансляторов (2005) (Карпов - Основы построения трансляторов (2005)) 19 страницаКарпов - Основы построения трансляторов (2005) (943926) страница 192013-09-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

3.16. Таблица 3.16. Вычисление входной цепочки дас-'гЮКе/~~ Ие:= Стек Остаток входной Выполняемая Примечание цепочки операция символ >йОКе~ — д Ие:= 3 д, а, с - - в стек Три однотипных шага д, а, с а'ОКет — д Ие:= 3 Выполнение х~ .'=а> с; х1 — в стек сравнения; х~ я (ТМИНЕ, ГАЗАКЕ~ ~ ОКе~ — а Ие:= 3 3дх, Ы вЂ” в стек Здх~д ОК х. тх~ОК4 х~ — В стек е/ — а Ие:= 3 Выполнение операции; х. е ~ТК~ЮЕ ГА$8Е е,~ — в стек Два однотипных шага --а Ие:= 3 а Йе:=3 х- те —,~ ) ,У Ф х, — в стек 3дх..л; а — в стек 3 дх2 хз ч Ие Х4 .'= ПЕ(Х2, Х, Д); х4 — в стек По адресу д записы- вается значение х4 Д +-Л4 Стек пуст; результат записан по адресу д 10 Вычисления закончены Итак, по арифметическому выражению ~и даже фрагменту программного ко- да), приведенному в форму ПОЛИЗ, выполнение вычислений с помощью стека очень просто. Однако, как перевести арифметическое выражение в ПОЛ ИЗ? Существуют различные алгоритмы такого преобразования.

Мы рассмотрим алгоритм, основанный на синтаксически-ориентированной трансляции. Действительно, исходное множество объектов для такого алгоритма — множество цепочек, результаты — тоже цепочки символов. Поэтому можно считать Очередной входной Выполнение операции Запись в стек й1е~х„хз, су) = если х..

истинно, то х;, в противном случае искомый алгоритм транслятором„который осуществляет преобразование выражения в ПОЛИЗ на основе структуры входных цепочек. Для построения транслятора, переводящего арифметические выражения в ПОЛИЗ. построим атрибутную грамматику арифметических выражений. Синтаксические правила грамматики построены — это грамматика Ь'|,. Для просторны будем рассматривать выражения только с операциями двух типов — операцией типа сложения оп~с и более приоритетной операцией типа умножения оп~у. С~"~,-.

'Š— ~Ео~псТ~ Т Т вЂ” ~ТотуР ~ РР— и'~ (Е) Как построить семантические правила? Нашей целью является формирование постфиксной формы выражения. Обозначим р постфиксную форь~у выражения, т. е. пусть р — семантический атрибут, приписанный нетерминалам Е, Ти Р. Если структура некоторого фрагмента выражения Ео есть Е~оисТ, например, то его постфиксная форма Ео р может быть построена как конкатенация пары постфиксных форм, составляющих этот фрагмен~ подвыражений, за которым следует знак операции. т.

е. Ео.р=Е1.р Т.р о~ос. Эти простые соображения приводят к следующей атрибутной грамматике арифметических выражений, целью которой является трансляция выражений в ПОЛИЗ (табл. 3. 1 7). Рассмотрим преобразование в 1 ОЛИЗ выражения а+Ьх(с — д)+~е — ф Будем считать, что дерево вывода этой цепочки построено синтаксическим анализатором, и стоит задача вычисления ПОЛИЗ этого выражения по дереву его вывода в атрибутной грамматике табл. 3.17. Такое аннотированное дерево представлено на рис.

3.20. Таблица 3.17. Атрибутная грамматика для трансляции арифметических выражений в ПОЛИЗ Структура и значение Рис. 3.20. Построение ПОЛИЗ арифметического выражения по дереву вывода Заметим, что определение и вычисление семантических атрибутов никак не связано с предположениями о том, в каком порядке строится дерево вывода: предполагается, что дерево вывода уже построено, и уже имея полное построенное синтаксическое дерево, мы можем начать вычисление семантических атрибутов.

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

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

3.18). Глава 3 Таблица 3.18. Перевод арифметического выражения в ПОЛИЗ Рассмотрим преобразование в ПОЛИЗ выражения а+Ах(с — д). На дереве вывода этой цепочки впишем определенные в таблице семантические действия — вывод операндов и операций для 1, 3 и 6 правил грамматики, соответственно. Выполнение этих действий в порядке, определенном порядком построения дерева вывода снизу вверх (т. е.

при обходе дерева в следующем порядке: потомки слева направо, затем узел дерева), даст на выходе программы трансляции искомую цепочку абсид-х+ (рис. 3.21). Рис. 3.21. Генерация ПОЛИЗ арифметического выражения по дереву вывода 3.5.3. Интерпретация арифметических выражений Построение транслятора, интерпретирующего арифметические выражения, также удобно осуществить на основе атрибутной грамматики. Целью интерпретатора является формирование по любому арифметическому выражению Глава 3 Рис. 3.22.

Интерпретация арифметического выражения по его дереву вывода ление может иметь различные формы; часто для этого используют постфиксную нотацию, трехадресный код либо так называемый р-код ~читается "пикод"). Два последних представления можно понимать как коды ассемблера для нскоторых виртуальных машин, предоставленных в распоряжение программиста. С этих кодов может легко быть проведена трансляция в ассемблер любой машины. Мы рассмотрим здесь компиляцию арифметических выражений в р-код для стековой машины.

Выполнение программы, представленной в р-коде, обычно основано на интерпретации этого кода. Будем считать, что соответствующая виртуальная стековая машина имеет обычную память данных, память для программы и стек. Для наших целей достаточны следующие команды стековой машины ~табл.

3.20). Таблица 3.20. Команды стековой машины Структура и значение 127 Таблица 3.20 (окончание) М0Ь То же для деления Атрибутная грамматика арифметических выражений, транслирующая выра- жения в р-код, чрезвычайно проста (табл. 3.21). В этой таблице отсо обозна- чает+, а оис1 обозначает —, ои~уо обозначает х, а оиу1 обозначаеет /. Арифметическое выражение а+ох(с — И)+е будет оттранслировано так, как показано на рис. 3.23. При построении дерева вывода снизу вверх последовательное выполнение семантических правил, связанных с каждым синтаксическим правилом в дереве вывода, изменяет глобальный атрибут — генерируемую программу— так, что в результате трансляции на выходе будет сгенерирована искомая программа. Для цепочки а+Ох(с — с/)+е последовательность выполнения семантических правил, определяемая построением дерева снизу вверх, даст следующую программу: ЬВ а 1.0 Ь 10 с 1.В И ЯЗВ МШ АВВ Безадресная операция: два операнда выбираются из стека, их произведение записывается в стек Т а бл и ц а 3.

21. Атрибутная грамматика для трансляции арифметических выражений в р-код Глава 3 128 1.0 е АИЭ Здесь предполагается, что адреса операндов в памяти мнемонически совпа- дают с их именами. Рис. 3.23. Генерация р-кода по дереву вывода 3.5.5. Символьное дифференцирование Символьное дифференцирование, или задача построения производной заданной функции, является классической проблемой математического анализа.

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

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

Пусть грамматика арифметических выражений имеет вид: 6~,. Š— ~Е+Т~ Т Т вЂ” +ТхР ~ РР— +Ял(Е) ~ Соя(Е) ~ х ~ С ~ (Е) Построение производной функции производится на основе правил„которые определены в математическом анализе: лроизводпая суя.цы есин сулжа протводных, производная коиспнти~ы есть ноль, и т. д.

Характеристики

Тип файла
DJVU-файл
Размер
7,58 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6508
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее