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

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

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

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

3.18). Рис. 3.18. "Желаемая" структура дерева вывода цепочки с+~+!хгхг+Ы: Более приоритетная операция 'х' должна выполняться до того, как ее результат будет использоваться в вычислениях. Можно догадаться, что для того. чтобы дерево вывода имело желаемую структуру, в искомой грамматике группы операндов, связанные операцией 'х', должны порождаться из нетерминала Т так же, как в грамматике б~; порождается сам операнд ~. Иными 1 словами, нетерминал Тдолжен играть роль начального символа грамматики, порождающей цепочки операндов, связанных операцией 'х'.

Точно так же, как в б~, из начального символа Е порождались цепочки операндов, связан- 1 ных операцией '*', с выполнением операций слева направо, в искомой грамматике из Т должны порождаться цепочки операндов, связанных операцией 'х'. Значит, необходимо ввести дополнительный нетерминал (назовем его Г). Искомая грамматика будет иметь вид: О~~,. à — +Е+Т ~ Т Т-+ТхГ ~ Г Р' — и' В этой грамматике дерево вывода цепочки г+г+юхЫ+~хг будет иметь следующий вид (рис. 3.19). Очевидно, что простая семантика с использованием только синтезированных атрибутов дает правильные вычисления значения любого арифметического выражения в этой грамматике. Если мы добавим еще один уровень приоритета операций, а именно возведение в степень, то, конечно, нетерминал Е должен быть начальным символом грамматики, порождающей фрагменты арифметического выражения, состоящие из операндов и знаков возведения в степень.

Пусть этот знак '1'. Глава 3 Рис. ЗЛ9. Дерево вывода цепочки в искомой грамматике Грамматика: Š— +Р ~Р ~ РР— и из начального символа Г порождает цепочки вида РР~1г, причем вычисление значения выра>кения при естественном определении семантики будет левоассоциативным — выполняться слева направо, т. е. 21314 будет пониматься как (2 ) или же 2 " . Но в некоторых языках программирования операция возведения в степень считается правоассоциативной, т. е. вычисление цепочки 213Т4 желательно понимать как (2 ) .

Чтобы достичь этого при естествен- з~ ном определении семантики, нужно просто немного изменить грамматику в этой части: à — эРТГ~ РР— эк Возможность использования скобок в арифметическом выражении можно учесть следующим образом. Любое арифметическое выра>кение, взятое в скобки, должно рассматриваться как операнд на следующих этапах вычислений вверх по дереву вывода. Поэтому полную грамматику арифметических вычислений можно представить следующим образом: б~,.

Š— эЕ+Т~ Š— Т~ Т ТэТХУГ ~ У7У ~ à à — +РТЕ~ Р Р-и ~(Е) Определим атрибутную грамматику для вычисления значения выражения (табл. 3.12). Структура и значение Таблица 3.12. Атрибутная грамматика арифметических выражений Введенные дополнительные нетерминалы имеют 'традиционные названия: Т вЂ” <терм>, à — <фактор>, Р— <первичное> или <рпп1агу>. Именно так традиционно представляется грамматика арифметических выражений и семантика ее продукций в современных языках программирования.

Отметим, что грамматика б'~, имеет следующие свойства: Г3 она задает язык арифметических выражений, т. е. порождает все правиль- ные выражения и ни одного неправильного; О она является недвусмысленной, т. е. каждой цепочке языка сопоставляет только одно дерево вывода; З она позволяет определить естественную простую атрибутную семантику с использованием только синтезированных атрибутов, определяющую стандартный порядок вычисления значения выражения с учетом приоритетов операций и вычисления операций с одинаковым приоритетом слева направо, а операций возведения в степень — справа палево; П при необходимости порядок вычисления в выражении можно регулиро- вать, используя скобки.

Следует отметить, однако, что этот "стандартный" порядок вычислений используется не всегда. В языке АПЛ-ЗбО, который в ~ХС82~ авторы называют "мощным средством, способствующим более четкой организации мышления", принят другой порядок вычислений арифметических выражений— а именно все операции выполняются в АПЛ-360 справа налево без учета при- Глава 3 оритетов. Такое отступление от общепринятой схемы авторы языка объясняют тем, что этот язык имеет много операторов, которые используются в выражениях, и введение приоритетов могло бы внести путаницу в понимание порядка вычисления значений.

Кроме того, по мнению авторов языка АПЛ-360, такой порядок удобен для "размышления одновременно с записью". Например, если вы хотите вычислить годовой доход при заработке, составляющем в месяц 2000 рублей за вычетом подоходного налога (13%) и спецналога (1%), то можно написать: 3+ — 12х2000х1 — %13+1.

Это можно прочитать как: зарплата будепг начисляться 12 месяцев, каждый месяц по 2000 рублей, за вычетом ~в процени~ах) 13 как подоходного налога и 1 — как спецналога". Вычисление этого выражения должно проводиться справа налево без учета приоритетов. В языке АПЛ-360 это выражение записывается без скобок. Очевидно, что в языке Паскаль, например, для правильного вычисления значения это выражение должно содержать, по меньшей мере, три пары скобок: 12х(2000х(1 — 0.01х(13+1))). Конечно, в языке АПЛ-360 для явного определения порядка вычислений можно использовать и скобки.

Определим атрибутную грамматику арифметических выражений в языке АПЛ-360 (табл. 3.13). Таблица 3.13. Атрибутная грамматика арифметических выражений в языке АПЛ-360 Здесь простейшая грамматика и естественная семантика продукций определяют порядок выполнения операций справа налево без учета приоритетов для арифметических выражений, однако с помощью скобок можно определить любой желаемый порядок вычислений.

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

Другое название этой формы — постфиксная запись, отражающая структуру выражения, при которой знак операции непосредственно следует за своими операндами. В действительности, можно различить три формы записи выражения: инфиксную, при которой знак бинарной операции стоит между операндами (это наша обычная форма, 'а+О'), префиксную — знак операции перед своими операндами '+аЬ', и постфиксную — знак операции после операндов 'аЬ+'. Г1рефиксную форму можно понимать как обычную функциональную запись Яа, о), в которой опущены скобки и знак функции (например.

'+') стоит непосредственно перед операндами, разделенными каким-то разделителем. Аналогично: постфиксная форма — это стилизованная функциональная запись (а, Ь)1. Удобство как префиксной, так и постфиксной форм записи арифметических выражений состоит в том, что они, в отличие от привычной нам инфиксной формы записи, не требуют скобок для определения любого порядка выполнения операций. Очевидно, что операции (функции), используемые здесь, не обязательно бинарные (просто по их виду должна быть ясна арность операции) и, более того, нс обязательно арифметические. Примеры этих форм записи приведены в табл. 3.14 (в этой таблице трехместная функция фйеи-йс(а, о, с), выдающая в качестве результата Ь, если а истинно, а в противном случае выдающая с, обозначена как 'Йе').

Таблица 3.14, Три формы записи выражения 120 Глава 3 Т а б л и ц а 3. 1 4 ~окончание) Префиксная форма была введена в 1925 г. польским логиком Яном Лукасевичем, поэтому ее вариант — постфиксная запись — традиционно называется Польской инверсной записью, или ПОЛИЗ. ПОЛИЗ значительно более удобная форма, чем префиксная запись: простой алгоритм с использованием стека позволяет вычислить значение выражения. А именно, в стек записываются операнды по мере поступления, слева направо, а как только встретится знак операции, из стека выбираются операнды этой операции, операция выполняется, и ее результат снова записывается в стек. В частности, рассмотрим примеры 4 и 5 табл. 3.15.

Значение выражения в этой записи можно вычислить так, как в табл. 3.15. Таблица 3.15. Вычисление значения выражения в записи абсид — х+~е — + Очередной входной Остаток входной Стек Выполняемая операция Примечание символ цепочки ~ Стек пуст. Первый ' символ входной Ьсд — ~+ф — -'3 а -- в стек цепочки — операнд Ь, с, И вЂ” в стек 6, с, И Три однотипных шага — х+/е — + 3 л,:=с — И; х, — в стек Выполнение операции ' — ' х -'~е — +3 Выполнение операции 'х' 3 аЬх~ х~ .'= Ьхх~', х. — в стек ~ Выполнение операции '+' ~е — +3 хз .'= а+х.; хз-- в стек ~ е — в стек Два однотипных шага х4 .'=~ — е; х4 — в стек Выполнение операции '-' Выполнение операции '+' х5 хз х4~ х~ — в стек Результат— в верхушке стека Вычисления закончены Структура и значение Другой пример: входная цепочка вычисляется так, как показано в табл.

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

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

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

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