Смекни!
smekni.com

Проектирование трансляторов (стр. 25 из 31)

ченными действиями:

CONDITIONAL -> if B <A1> then C <A2> else D <A3> fi

Действия А1, А2 и А3 означают (next - значение номера

следующей метки, присваиваемое компилятором):

А1. Проверить тип В, применяя любые необходимые преобра-

зования (приведения) типа для получения логического значения.

Выдать код для перехода к L<next>, если В есть "ложь":

JUMPF L<next>,<address of B>

Поместить в стек значение next ( обычно для этого служит

стек знаков операций ). Увеличить next на 1. (Угловые скобки

(<,>), в которые заключаются "next" и "address of B", исполь-

зуются для обозначения значений этих величин, и их не следует

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

ющих правилах грамматики.)

А2. Генерировать код для перехода через ветвь else (

т.е. перехода к концу условной зависимости )

GOTO L<next>

Удалить из стека номер метки ( помещенный в стек дейс-

твием А1 ), назвать i, генерировать код для размещения метки

SETLEBEL L<i>

Поместить в стек значение next. Увеличить next на 1.

А3. Удалить из стека номер метки (j). Генерировать код

для размещения метки

SETLABEL L<j>

Если условная зависимость сама является выражением ( а

не оператором ), компилятор должен знать, где хранить его

значение, независимо от того, какая часть вычисляется - then

или else. Это можно сделать, специфицируя адрес, который ука-

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

частью then либо частью else, по указанному адресу.

Аналогично можно обращаться с вложенными условными выра-

жениями или операторами.

III. Описания идентификаторов

Допустим, что типы всех идентификаторов полностью выяс-

нены в предыдущем проходе и помещены в таблицу символов. Ад-

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

Рассмотрим описание

somemode x

еречислим действия, выполняемые во время компиляции:

1. В таблице символов производится поиск записи, соот-

ветствующей x.

2. Текущее значение указателя стека идентификаторов дает

адрес, который нужно выделить для x. Этот адрес

(idstack, current block number, idstack pointer)

включается в таблицу символов, а указатель стека идентифика-

торов увеличивается на статический размер значения, соответс-

твующего х. (В Алголе 68, если вид х начинается с ref, обьем

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

х, а не для самого х; это обозначается с помощью адреса дру-

гого типа. )

3. Если х имеет динамическую часть, например в случае

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

мяти во время прогона.

IV. Вход и выход из блока

При входе в блок ( последовательное предложение с описа-

ниями в Алгол 68 ) предположим, что во время предыдущего про-

хода получена определенная информация. Она состоит из таблиц

видов и символов, дающих типы или виды всех идентификаторов и

т.п. Тогда при входе в блок нужно выполнить следующие основ-

ные действия:

1. Прочитать в таблице символов информацию, касающуюся

блока, и связать ее с информацией включающих блоков таким об-

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

щих реализаций идентификаторов и т.д.

2. Поместить в стек (idstack pointer). Поместить в стек

(wostack pointer). Поместить в стек (block number). Все эти

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

вновь после того, как будет покинуть блок, в который только

что осуществлен вход:

idstack pointer := 0

wostack pointer := 0

3. Генерировать код для исправления DISPLAY

BLOCK ENTRY block number

4. Увеличить номер уровня блока на 1. Увеличить наиболь-

ший использованный до сих пор номер блока на 1 и присвоить

это значение номеру блока.

5. Прочитать информацию о виде и добавить ее в таблицу

видов ( если в языке имеются такие "сложные" виды, как в Ал-

голе 68 ).

При выходе из блока требуется:

1. Обновить таблицу блоков, задав размер стека идентифи-

каторов и т.п. для покинутого блока.

2. Исключить информацию в виде таблицы символов для по-

кинутого блока.

3. Генерировать код для изменения дисплея

BLOCK EXIT block number

4. Удалить из стека (block number). Удалить из стека

(wostack pointer). Удалить из стека (idstack pointer). Умень-

шить номер уровня на 1.

5. Поместить результат (при необходимости) в рамку стека

вызывающего блока.

ЛЕКЦИЯ 16

КОНТЕКСТНЫЕ УСЛОВИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

КОНТЕКСТНЫЕ УСЛОВИЯ 1-ОГО И 2-ОГО ТИПА

1. Условия, связанные с описанием правил идентификаторов

В каждом блоке без внутренних блоков идентификатор нельзя

описывать более одного раза.

Для процедур и функций ни один идентификатор не должен вхо-

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

ности спецификаций.

2. Правила соответствия между определяющими и использующими

вхождениями идентификаторов.

.

Правила поиска часто называют алгоритмами идентификации.

Проверим одно контекстное условие:

1. Рассмотрим min блок.

2. Ищем определяющее вхождение идентификатора в рассмотрен-

ном блоке. Если оно найдено, то процедура идентификации законче-

на.

Иначе - шаг 3.

3. Ищем min блок, который мы рассмотрели в шаге 2. Если та-

кой блок найден, рассмотрим его и переходим к шагу 2. Иначе,

процедура закончена.

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

Однако, задача идентификации сложнее, т.к. обычно рассмат-

ривается группа контекстных условий.

1. Каждый идентификатор, входящий в совокупность специфика-

ций, должен также входить в список формальных параметров.

2. Каждый идентификатор, входящий в список значений, должен

входить в совокупность спецификаций.

3. Идентификаторы, входящие в тело процедуры, могут быть

описаны в блоке, вне этого блока или могут быть включены в

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

Список спецификаций - заголовок (имя) функции, описание ти-

па функции.

Список значений - те параметры, кот. меняются при изменении

функции, т.е. результат.

КОНТЕКСТНЫЕ УСЛОВИЯ ТРЕТЬЕГО ТИПА

Они регламентируют:

1) Соответствие видов величин, входящих в синтаксические

конструкции программ.

2) Задание допустимых соотношений между формальными парамет-

рами в процессах и формальными описаниями соответствующих проце-

дур.

3) Сравнение индексов переменных в использующем и определяю-

щем вхождениях идентификаторов.

4) Сравнение размерности массива в используемом и определяю-

щем вхождении идентификатора.

КОНТЕКСТНЫЕ УСЛОВИЯ ЧЕТВЕРТОГО ТИПА

Некоторые логические ограничения, которые относятся к реа-

лизации той или иной версии транслятора.

Массив может быть с неограниченным размером.

ЛЕКЦИЯ 17

ПРОГРАММНЫЕ ГРАММАТИКИ

Правила вывода этих грамматик имеют тот же вид, что и у

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

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

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

дущих шагах.

Gp = { Vт, Vn, P, I, S }

G - конечное множество целых положительных чисел

(множество меток)

** **

r) Ф -> psi │ W1 │ W2 │, W1, W2 - некоторое подмножество меток

│ * * *

метка,соотв. Ф,psi ( Vт U Vn )

выводу

* - соответствующий класс грамматическим правилам

** - обозначается некоторое подмножество

В терм. порожденной грамматике сформируем использование

данного грамматического файла.

w - промежуточная цепочка.

Если w содержит вхождения по цепочке Ф, то левое вхождение

Ф в цепочке заменяем на psi.

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

помеченное метками из множества W1.

Если w не содержит вхождения строки Ф, то строка w не моди-

фицируется, и к ней применяется некоторое правило, полученное

меткой из множества W2.

Язык, порожденный этой грамматикой, содержит только терми-

нальные символы.

В зависимости от ограничений на классическую часть различа-

ют:

1) контекстно-свободные,

2) контекстно-зависимые,

3) укорачивающие грамматики.

Имеют место теории, которые доказывают, что программные кон-

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

стные-свободные грамматики, в то время как зависимые контек-

стно-свободные грамматики совпадают с программно контекстно-сво-

бодными грамматиками.

Когда применяются программные грамматики процесс трансляций

выполняется в 2 этапа:

1) Порождается промежуточная форма программы.

Имеет место некоторый промежуточный язык, в котором некото-

рые синтаксические конструкции отсутствуют (например, внутр.

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

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

раммы.

2) Промежуточная форма программы проверяется на предмет

соотношения контекстных условий и выполняется замена симво-

лов-двойников на терминальные символы программы.

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

ваться в различных модификациях.

После первого этапа выполняется проверка контекстных усло-

вий (2 этап).

Каждая проверка заключается в следующем:

- сначала выделяются конструкции, участвующие в проверке;

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

торых эта конструкция состоит (присвоение индекса);

- далее производится сравнение выделенных конструкций;

способ зависит от конкретного контекстного условия (сравнение

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

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

торых построенных конструкций.

На выходе все двойники заменяются на терминальные символы

(соответствующие).

КОНТЕКСТНЫЕ УСЛОВИЯ ДЛЯ ПРОГРАММНЫХ ГРАММАТИК

1. В каждом блоке без внутренних блоков каждый идентифика-

тор должен быть описан не более одного раза (это условие приме-