Проектирование трансляторов

-вычисление компонент допвектора;

-вычисление адреса хранения массива;

-вычисление адреса хранения допвектора;

-занесение этих адресов в соответствующие ячейки.


Для массивов с постоянными границами компоненты допвектора

вычисляются в ходе трансляции и помещаются среди констант. Чтобы

отличить переменные граничные пары от постоянных нужно ввести до-

полнительный анализ операндов ADEC, являющихся граничными парами.

Допвектора могут располагаться вслед за парой ячеек, выделенной

последнему массиву или среди констант(для массива с постоянными

границами.


ЛЕКЦИЯ 12


СТРУКТУРЫ ДАННЫХ И ОРГАНИЗАЦИЯ ПАМЯТИ


Некоторые применяемые языки требуют динамического распреде-

ления памяти; блоки оперативной памяти при этом выделяются произ-

вольно, а затем освобождаются. Область данных - это блок ОП, вы-

деленный для данных.

Области данных могут принадлежать также к статическому клас-

су. Статическая область данных имеет постоянное число ячеек, а

динамическая область данных не всегда присутствует во время счета.

Если вызов процедуры происходит рекурсивно, то существует

несколько областей данных в ОП, каждая для отдельного вызова про-

цедуры.

Если компилятор знает все характеристики переменных во вре-

мени, то он может сгенерировать полностью команды обращеиня к пе-

ременным, основываясь на этих характеристиках.

Память выделяется компилятором не только для переменных, но

и для описателей, содержащих атрибуты, определяемые во время сче-

та. Этот описатель заполняется и изменяется во время счета. Типы

данных исходной программы должны быть отображены на типы данных

машины. Целые переменные содержатся обычно в одном слове.


Информационные таблицы


При анализе программы из описаний, заголовков процедур, цик-

лов и т.д. извлекается информация и сохраняется для последующего

использования. Эта информация обнаруживается в отдельных точках

программы и организуется так, чтобы к ней можно было обратиться

из любой части компилятора. В каждом компиляторе в той или иной

форме используется таблица символов. Это таблица идентификаторов,

встречающихся в программе, вместе с их атрибутами.

При разборке компилятора невозможно определить вид и содер-

жание информации, которую следует собирать, до тех пор, пока не

будут достаточно обстоятельно продуманы команды обьектной прог-

раммы для каждой инструкции исходной программы и сама синтезирую-

щая часть компилятора.

При проверке правильности семантики и генерации кода тре-

буются знания характеристики идентификатора. Эти характеристики

выясняются из описания и накапливаются в таблице символов. Наип-

ростейшая таблица символов для каждого элемента имеет поле аргу-

мента и значения. Аргументами таблицы являются символы или иден-

тификаторы, а значениями - их характеристики. Так как число ли-

тер в идентификаторе непостоянно, в аргументе часто помещают сим-

волы вместо самого идентификатора. Это позволяет сохранить фикси-

рованный размер аргумента. Идентификаторы хранятся в специальном

списке строк.

При проходе исходной программы через компилятор при встрече

конструкции описания происходит запись идентификатора исходной

программы в таблицу символов вместе с его атрибутами. В результа-

те дальнейшего чтения исходной программы, в компиляторе при на-

хождении любого идентификатора программа обращается к таблице

символов и ищет в ней данный идентификатор. Если идентификатор не

обнаружен, то выдается сообщение, что данный идентификатор не оп-

ределен. Если же он обнаружен, то производится сравнение данного

идентификатора с записанным в таблице символов и производятся

необходимые преобразования.

При работе с таблицей символов нужно разработать правила ор-

ганизации и обращения к таблице символов. Таблицы символов могут

быть как упорядоченными, так и неупорядоченными.


При упорядоченном списке элементов наиболее результативным

является бинарный или логарифмический поиск. Иногда один и тот же

идентификатор может быть описан и использован много раз в различ-

ных блоках и процедурах, и каждое такое описание должно быть

единственным. Соответственно нужно разделять таблицу симводов.

При этом устанавливается правило нахождения соответствующего

идентификатора. Оно состоит в следующем: сначала просматривается

текущий блок, затем обьемлющий блок и т.д., до тех пор, пока не

будет найдено описание данного идентификатора.

При осуществлении поиска все элементы таблицы хранятся для

каждого блока в смежных ячейках и используется список блоков.

Информация об идентификаторе хранится в той части таблицы,

которую мы определили как "значение".

Таблица символов состоит из 5-ти различных списков:


- список меток;

- список арифметических констант;

- список имен общих блоков,имен подпрограмм и имен перемен-

ных;

- список общих блоков;

- список имен подпрограмм.


Элементы всех этих списков помещаются в одной и той же таб-

лице; первые два байта каждого элемента используются для ссылки

на следующий элемент в том же списке.

ЛЕКЦИЯ 13


ВНУТРЕННИЕ ФОРМЫ ИСХОДНОЙ ПРОГРАММЫ


Ввиду сложности реальных языков программирования и предъяв-

ления повышенных требований к эффективности самого процесса ком-

пиляции и к готовым программам, разработчики вынуждены проектиро-

вать многопроходные компиляторы. При этом для связи между прохо-

дами, необходимы внутренние (промежуточные) формы исходной прог-

раммы. В большинстве внутренних форм, операторы располагаются в

том порядке, в котором они должны выполняться, что означает пос-

ледующий анализ и итерацию об'ектного кода. (Эти внутренние пред-

ставления можно использовать для интерпретации).

Внутренняя форма является более развернутым представлением

исходной программы, к которой предъявлялись требования лаконич-

ности и краткости. Более подробное представление обеспечивает

проведение глубокого анализа и оптимизации программ.

Как правило, в одном компиляторе для разных синтаксических

единиц (выражений, условных операторов, операторов присваивания и

т.д.) используются разные, наиболее подходящие с точки зрения

разработчика, внутренние формы.


1.1. Опреанды и операторы


Внутренние формы содержат операторы и операнды. В различных

видах представлений существенное отличие заключается в форме сое-

динения операторов и операндов.

Операторы: + , - , / , * , BR (branch) и т.п. Операнды : -

простые имена (переменных, процедур и т.д.);

- константы;

- временные переменные, генерируемые компилятором;

- переменные с индексами.

Каждый операнд (за исключением переменных с индексом) пред-

ставляется указателем на соответствующий элемент в таблице симво-

лов, констант или временных переменных.

В поле операнда предусматривается признак косвенной адреса-

ции, чтобы указать таким путем, что значение в таблице, на кото-

рое указывает операнд, является адресом расположения значения,

которое требуется операнду при исполнении команды.

Пременную с индексами А[i,j,...,k] можно обрабатывать сле-

дующим образом:

- сначала включить последовательность операций для вычисления

VARPART и запоминания ее во внешней ячейке Т;

- сам операнд представить двумя указателями: на элемент с име-

нем массива и на значение VARPART, т.е. А[i,j,...,k] можно

представить в виде А[T]. Такой операнд занимает две ячейки

во внутреннем представлении, но зато позволяет генерировать

более эффективную объективную программу. Простая переменная


┌───┬───┬─────────────────────────────────────┐

│ 1 │ I │ указатель на эл-т таблицы символов │ I - признак

└───┴───┴─────────────────────────────────────┘ косвенной

Константа адресации

┌───┬───┬─────────────────────────────────────┐

│ 2 │ │ указатель на эл-т таблицы констант │

└───┴───┴─────────────────────────────────────┘

Временная переменная

┌───┬───┬─────────────────────────────────────┐

│ 3 │ I │ указатель на эл-т табл. врем. перем.│

└───┴───┴─────────────────────────────────────┘

Перменная с индексами

┌───┬───┬─────────────────┬───┬───┬───────────────┐

│ 4 │ I │ ук-ль на эл-т │ х │ I │ ук-ль на эл-т │

│ │ │ с именем массива│ │ │ с индексом │

└───┴───┴─────────────────┴───┴───┴───────────────┘

┌─────────────────────────┘

│ описание индексов

х = 1 - указатель на табл. символов

2 - указатель на табл. констант

3 - указатель на табл. временных переменных


Форматы операндов

Польская запись

1.Польский логик Я.Лукашевич впервые применил запись арифмети-

ческих и логических выражений, которая без скобок указывает точ-

ный порядок выполнения операций. В ней операторы следуют непос-

редственно за операндами (постфиксная запись). Она определяется

следующими правилами:

1) операнды следуют в том же порядке, как они представлены в

префиксной записи;

2) операторы следуют в том же порядке, в каком они должны

вычисляться (слева направо);

3) опер-ры располаг-ся непосредственно за своими оп-дами.

Это можно представить следующими правилами: <операн-

д>::=<идентификатор>|<операнд><операнд><оператор>

<оператор>::= + | - | / | * | ... Для унарных оперций можно

ввести новый символ ( например @ для -) и еще одно правило

<операнд>::=<операнд>@ Пример A * ( B + C / D ) <=> ABCD / + *

A + ( -B + C * D ) <=> AB@CD * + +

(C таким же успехом можно применять префиксную запись).


Вычисление арифметических выражений


Данные правила определяют порядок обработки выражения с по-

мощью стека за один просмотр выражения слева направо, начиная с

самого левого символа входной цепочки:

1. Если сканируемый символ идентификатор, то его значение

заносим в стек и переходим к следующему символу (правило <оп-

реанд>::= идентификатор)

2. Если сканируемый символ - бинарный оператор, он приме-

няется к двум верхним операндам в стеке и замещает их на получен-

ный результат, что эквивалентно правилу <операнд>::= <операнд><о-

перанд><оператор>.

3. Если сканируемый символ - унарный оператор, то он приме-

няется к верхнему символу стека и затем замещает его результатом

(правило <операнд>::= <операнд><оператор> [ Д/З - стр.282 ]


Включение в польскую запись других операторов


1) Присваивание <пер.>::= <выр.> ( <=><пер.><выр.>:= )

прим.: А := В * С + D <=> АВС * D + :=

- После выполнения оператора := из стека исключаются <пер.> и

<выр.>, т.к. этот оператор не имеет результирующего значения в

отличие от бинарных арифметических операторов.

- Кроме того, в стеке находится не значение <пер.> (оно нам

не нужно), а ее адрес, т.к. в рез-те присвоения по нему заносит-

ся значение <выр.>

2) Оператор GOTO А <=> A BRL,

где метка А представлена адресом соответствующего ей эл-та

таблицы символов. Оператор BRL (Branch to label)

3) Условные переходы

<операнд1><операнд2> BP, где первый операнд является значе-

нием арифметического выражения, второй указывает номер (место)

символа в цепочке польской записи. Если операнд1 положителен

(positive), то в качестве следующего берется символ, на который

указывает операнд2, иначе работа продолжается как обычно.

BP - переход по положительному значению, ВМ - по минусу, BZ

- по нулю, BPZ - по неотрицательному значению, и т.д.

4) Условная инструкция

IF<выр>THEN<инстр.1>ELSE<инстр.2><=><выр><С1>BZ<инср.1><С2>BR<инстр.2>

С1 - номер имвола, с которого начинается <инстр.2>.

С2 - номер символа,следующего за <инстр.2>.

Операторы BZ и BR не порождают результирующего значения.

Часть их работы состоит в исключении из стека двух верхних эле-

ментов (значения <выр> и <С1>) для BZ и соответственно одного

<С2> для BR. Оператор безусловного перехода <С2>BR - использует-

ся метка <С2> для внутренних генерируемых переходов. В то время

как оператор <метка> BRL в качестве значения <метка> использует

адрес эл-та таблицы символов.

5) Описание массива. ARRAY A[Li:Ui,...,Ln:Un]

можно представить в виде:

LiUi...LnUn A ADEC, где ADEC - оператор, имеющий переменное

число операндов, зависящее от числа индексов. Операнд А - оче-

видно, адрес элемента таблицы символов для А -> При вычислении

ADEC, следовательно, из этого элемента таблицы извлекается ин-

формация о размерности массива А (т.е. и о числе операндов ADEC)

- с этой целью изменен порядок записи операндов.

6) Переменная с индексами A[<выр.i>,...,<выр.n>] преставляется

в виде <выр.1>...<выр.2> A SUBS

Оператор SUBS используя элемент А таблицы символов и ин-

дексные выражения, вычисляет адрес элемента массива. Затем опе-

ранды исключаются из стека и на их место заносится новый опе-

ранд, определяемый адресом элемента массива и его типом.

Использование для индексирования специального оператора

SUBS - более удобный способ для польской записи.

Пример: BEGIN INTEGER K; ARRAY[1:I-j]; K:=0;

L:IF I>j THEN K:=K+A[I-j]*6 ELSE

BEGIN I:=I+1;I:=I+1;COTOL END

END

(1) BLOCK 1 IJ - A ADEC K0 := Польская запись

(11) IJ - 29 BMZ

(16) K KIJ - A SUBS 6*+:= 41 BR Для каждого символа отво-

(29) II1 + := II1 + := L BRL дится одна строка (место)

(41) BLCEND

Как видно, описание INTEGER K (не требующее генерации ко-

манд) отсутствует во внутреннем представлении. Оно нужно для

формирования элемента таблицы символов для К.

Введены два оператора без операндов BLOCK (начало блока) и

BLCKEND (конец блока).


N содерж. N содерж. таблица

слова слова символ слова слова символ символов

┌────┬────┬────┬───────┬────┬────┬────┬────────┬───┬─────┐

│ 1 │ 11 │ │ BLOCK │ 36 │ 6 │ │ SUBS │ 1 │ I │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 2 │ 1 │ 1 │ 1 │ 37 │ 1 │ 6 │ 6 │ 2 │ Y │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 4 │ 2 │ 1 │ I │ 39 │ 15 │ │ * │ 3 │ A │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤

│ 6 │ 2 │ 2 │ Y │ 40 │ 14

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: