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

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

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

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

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

ВХОДНОЙ ЯЗЫК В качестве входной цепочки наш компилятор принимает поток лексем после лексического анализатора Милана: именно лексемы являются терминальными символами грамматики, которая описывается синтаксическими диаграммами входного языка. В семантических вычислениях, однако, кроме типа лексем используется и номер внутри этого типа, характеризующий конкретного представителя типа. Например, при компиляции программы на Милане нам необходимо генерировать выходную программу, и конкретная команда должна генерироваться с учетом индекса лексемы. Например, операторы '+' и ' — ' представляются лексемой 0Ь; с индексом. Если ~' = О, то необходимо сгенерировать команду сложения, а если ~ =- 1, то нужно генерировать команду вычитания.

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

Аналогично, любой идентификатор представляется лексемой Ы; с индексом ~', показывающим номер идентификатора в таблице имен. Итак, будем считать, что сканер Милана передает распознавателю поток лексем, две таблицы — таблицу констант и таблицу имен, — а также целую переменную Мс, хранящую общее число констант в программе. Нисходящие методы синтаксического анализа 5.7.2. Выходной язык Рис. 5.2?.

Структура стековой машины Стековая машина ~рис. 5.27) — это абстрактный вычислитель, имеющий адресуемую линейную память программ, адресуемую линейную память данных, стек и АЛУ ~арифметико-логическое устройство), выполняющее все команды стековой машины. Ьудем считать, что в каждом слове памяти программ может быть помещена одна команда, в каждом слове памяти данных и стека — одно данное целого типа. В процессе работы машины счетчик команд 'рс' указывает очередную выполняемую команду. Для трансляции языка Милан необходимо в этой машине иметь следующие команды (табл. 5.б — 5.8). Таблица 5.6. Команды управления Н1 Т Выполнение программы прекращается, управление возвращается операци- 3МР гг ача управления команде с адресом ггг ается команде с адресом ггг, если в верхушке стека О элемент выталкивается из стека 3МРО Управление передается команде с адресом ггг, если в верхушке стека не О (ТРОЕ).

Верхний элемент выталкивается из стека ЗМР! ггг В качестве выходного языка компиляторов алгоритмических языков обычно выбирается ассемблер некоторой ЗВМ или какой-либо другой промежуточный язык. Мы в качестве такого языка вьюерем р-код, т. е. набор команд условной стековой машины, которую мы рассматривали в примере компиляции арифметических выражений в гриве 3.

Подобный код часто применяется в качестве промежуточного языка при трансляции языков программирования. Глава 5 188 Таблица 5.7. Команды ввода-вывода Очередное целое из входного потока загружается в верхушку стека в двоич- ном коде Содержимое верхушки стека выгружается в выходной поток как целое число Таблица 5.8. Команды арифметико-логические Содержимое слова а памяти данных загружается в стек Содержимое верхушки стека выталкивается из стека и записывается в слово а памяти данных КТи АВВ Безадресная операция: два операнда выбираются из стека, их сумма записы- вается в стек о же для вычитания МШ.

Т ИЧ о же для умножения о же для деления Два операнда выталкивается из стека и сравниваются, и результат — 0 или 1 — записывается в стек; ~ — тип сравнения: ~ = О для '=', ~ = 1 для '~', ~ = 2 для '<', ~ = 3 для '>', ~ = 4 для '<', ~ = 5 для '>' Как и в арифметических операциях, в операции сравнения первый операнд находится в стеке глубже, чем второй. Выполняемая операция сравнения зависит от ~. Кодировка операций совпадает с кодировкой их в лексеме ге1.

При положительном результате сравнения в стек записывается 1, иначе туда записывается О. Команды условного перехода используют эти логические значения. Так, команда <1МРО ~л> читает верхушку стека и передает управление на п~, если прочитанное значение О. Это значение из стека убирается. 5.7.3. Компилятор Результатом компиляции программ на Милане должна быть программа стековой машины. Генерацию команд при компиляции такого простого языка, как Милан, можно совместить с этапом синтаксического анализа, выполняя генерацию с помощью семантических функций, включенных в алгоритм распознавания структуры входной программы. Сами же алгоритмы распознавания для Милана строятся в методе рекурсивного спуска по синтаксическим диаграммам языка так, как было показано выше.

Поэтому наша задача — определить, какие семантические действия в какое место синтаксических диаграмм языка Милан должны быть включены для выполнения компиляции. Нисходящие методы синтаксического анализа Генерируемую программу будем располагать с начальной ячейки памяти программ, для чего счетчик генерируемых команд С очистим. Этот счетчик будет доступен всем семантическим программам компилятора. Память данных стековой машины распределим так: первые Мс слов будут занимать константы объектной программы, а за ними по порядку, определяемому их местом в таблице имен, будут идти переменные (напомним, что Хс — это число констант во входной программе; это число получается на этапе лексического анализатора и доступно на последующих этапах трансляции). Синтаксические диаграммы языка Милан с включенными туда семантическими функциями приведены на рис. 5.28. Поскольку при распознавании будут выполняться семантические вычисления, в лексемах, являющихся представителями нескольких конкретных объектов, указан явно индекс — номер того объекта, который представляет этот тип лексем.

Это относится к лексемам Ы, соиМ, о1я, ойп и ге1. Рис. 5.28. Компилятор языка Милан (синтаксические диаграммы с включенными семантическими процедурами) Глава 5 190 Семантические процедуры используют г1роцедуру ОЕАР, генерирующую команду стековой машины, с указанием того адреса, куда помещается эта команда, например: бЕМ(С, <команда>). Счетчик команд С затем может увеличиваться на единицу: С++. В табл.

5.9 приведены семантические процедуры с пояснениями. Таблица 5.9. Семантические процедуры с пояснениями ЕХ(С, <Н 1.Т>) Программа кончается командой останова ЕМ(С, <Щ Хс+~ >); С++ ~ СЕЯ(С, <П), ~>).; та с номером ~ помещается в стек ЕМ(С, сИЧХ>); С з входного потока записывается в стек ~ = О йеп СЕМ(С е СЕЙ(С, <ИЧ> ется команда сложения либо вычита- анды уже помещены в стек ется команда сравнения; операнды щены в стек Х(С, сРКХ>); С++ из верхушки стека записывается в вы- оток ЕМ(С, <ЯТ, Хс+~>); С++ ~з верхушки стека записывается в сло- и данных := С++ Е~х(С <3МР М>) С++ Е~(М, <3МРО, С>) Организуется выполнение цикла Рассмотрим поочередно эти семантические процедуры.

Самая простая, по- видимому, это процедура уО. Она генерирует команду останова после того, как вся программа построена и известен адрес слова в памяти программ, сле- дующего после последней команды. Этот адрес находится в счетчике С. / = О йеп СЕЯ(С, <АВВ ье СЕЙ(С, <ЯЗВ>); С++ ЕХ(С, <СМР, ~>); С++ Значение (-й переменной помещается в стек (переменные располагаются после констант в памяти данных) уется команда умножения либо деле- висимости от значения индекса у лекс; операнды уже помещены в стек Запоминается адрес начала фрагмента вычис- ления условия цикла Запоминается адрес слова, куда должна быть помещена команда условного перехода для организации цикла. Счетчик команд увеличивается, чтобы зарезервировать поле для этой команды Нисходящие методы синтаксического анализа Генерирование команд для реализации любой конструкции алгоритмического языка должно подчиняться некоторой идее.

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

При распределении памяти переменным выделен участок памяти данных после всех констант в порядке номеров их имен, и именно этот номер является индексом лексемы Ы,. Поэтому семантическая процедура у1 имеет вид ~бЕМ(С, <1.Р, Мс+~>); С++~, Счетчик С указывает адрес очередной команды, операция С++ устанавливает счетчик команд на адрес следующей команды.

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

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

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

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