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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.Р, Мс+~>); С++~, Счетчик С указывает адрес очередной команды, операция С++ устанавливает счетчик команд на адрес следующей команды.

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

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