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

"+" из  стека знаков операций,  генерировать код для сложения

целого и вещественного значений, поместить статические харак-

теристики результата в нижний стек;  тип результата - вещест-

венный.

     Действия А1,  А2,  А3 и вышеприведенную грамматику легко

расширить, что позволит использовать

     а) большее число уровней приоритета для знаков операций;

     б) унарные знаки операций.

     Другие случаи употребления нижнего стека рассматриваются

в следующем разделе.

     Нижний стек  обеспечивает  передачу  информации вверх по

синтаксическому дереву.  Для передачи же информации  вниз  по

дереву применяется  так  называемый верхний стек.  Значение в

него помещается всякий раз,  когда во  время  генерации  кода

происходит вход  в  такую  конструкцию,  как присваивание или

описание идентификатора.  При выходе из этой конструкции зна-

чение из стека удаляется. Следовательно, генератор кода может

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

справа от знака присваивания; эта информация способствует оп-

тимизации.

     Еще одной структурой данных,  которая требуется во время

генерации кода, является таблица блоков.

╔══════════╦═══════════╦═══════════════════╦═════════════════╗

║   Блок   ║  Уровень  ║   Размер стека    ║ Размер рабочего ║

║          ║   блока   ║  идентификаторов  ║                 ║

╠══════════╬═══════════╬═══════════════════╬═════════════════╣

║    1     ║     1     ║        14         ║       16        ║

║    2     ║     2     ║        12         ║       11        ║

║    3     ║     2     ║        21         ║       13        ║

║    4     ║     3     ║         4         ║        9        ║

║    5     ║     2     ║         6         ║       12        ║

╚══════════╩═══════════╩═══════════════════╩═════════════════╝

     В этой  таблице есть запись для каждого блока программы,

и эту запись можно рассматривать как структуру,  имеющуюю по-

ля, которые соответствуют номеру уровня блока, размеру стати-

ческого стека идентификаторов,  размеру статического рабочего

стека и т.д.  Такую таблицу можно заполнять во время прохода,

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

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

рамке стека.

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

дующие основные структуры данных:  нижний стек, верхний стек,

стек знаков операций,  таблица блоков и,  кроме того, таблица

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

                        Генерация команд

     По существу,  на этом этапе происходит перевод  внутреннего

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

язык.

     Возможны три формы об'ектного кода: абсолютные команды, по-

мещенные в фиксированные ячейки; программа на автокоде; програма

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

вторичную память.

     Рассмотрим выражение (A + B) + (X + Y)

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

таков:

     1. загрузить А в сумматор;

     2. прибавить B к сумматору;

     3. записать результат A+B во временную рабочую  ячейку;

     4.  загрузить X в сумматор; 5. прибавить Y к сумматору;

     6. прибавить временный результат A+B к X+Y в сумматоре.

     Каждому из  трех  сложений предшествует своя последователь-

ность команд загрузки и записи.

     Чтобы построить код генератор хранит некоторую информацию о

том,  что будет происходить в период исполнения генерируемого им

кода.

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

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

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

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

     ----------------------

     ! Программа          !

     ----------------------

     ! Константы          !

     ----------------------

     ! Подпрограммный     !

     ! стек               !

     ----------------------

     ! Промежуточные      !

     ! результаты         !

     ----------------------

     ! Хранимые результаты!

     ----------------------

     ! Переменные         !

     ----------------------

     Область ПРОГРАММА  содержит  команды  об'ектной  программы.

ПОДПРОГРАММНЫЙ СТЕК используется для хранения  адресов  возврата

подпрограмм. Область ХРАНИМЫЕ РЕЗУЛЬТАТЫ используется для хране-

ния результатов атома  ХРАНЕНИЕ  в  FOR-операторах.  В  областях

КОНСТАНТЫ и ПЕРЕМЕННЫЕ хранятся соответственно значения констант

и переменных.

     Область ВРЕМЕННЫЕ РЕЗУЛЬТАТЫ используется для хранения про-

межуточных результатов.

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

информации о параметрах атомов.  Каждый табдичный элемент  имеет

поле ВИД,  указывающее вид об'екта, описываемого этим элементом,

а также одно или два других поля. Поле ВИД содержит одно из сле-

дующих пяти значений:  КОНСТАНТА,  ПЕРЕМЕННАЯ, ПРОМЕЖУТОЧНЫЙ РЕ-

ЗУЛЬТАТ, ХРАНИМЫЙ РЕЗУЛЬТАТ или МЕТКА.

     Мы предполагаем, что генератор кода содержит процедуру, на-

зываемую ГЕН, которая строит двоичное представление генерируемой

команды.  ГЕН  вызывается с двумя параметрами:  кодом операции и

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

нерируемой команды. Процедура ГЕН выполняет следующие действия:

     1. Формируется  двоичный  код,  соответствующий первому

        параметру процедуры ГЕН.

     2. Формируется  двоичный  код,  соответствующий второму

        параметру процедуры ГЕН.

     3. Двоичный  код,  образующий  сгенерированную команду,

        помещается в ячейку,  соответствующую  текущему зна-

        чению СЧЕТКОМ.

     4. СЧЕТКОМ увеличивается и сравнивается с ГРАНКОМ.

     Здесь СЧЕТКОМ и ГРАНКОМ - переменные периода компиляции.

      Генерация кода для некоторых типичных конструктов

     Покажем, как генерируеися код для некоторых конструктов,

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

     I. Присваивания

     В соответствии с терминологией  Алгола  68  присвамвание

имеет вид

                    destination := source

     Смысл его состоит в том,  что значение,  соответствующее

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

( или именем ), заданным получателем. Например, в

                         p := x + y

значение "х+у" присваивается  р.

     Допустим, что статические характеристики источника и по-

лучателя уже находятся в вершине нижнего стека.  Опишем дейс-

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

ваивания. Прежде всего из нижнего стека удаляются два верхних

элемента, после чего происходит следующее:

     1. Проверяется  непртиворечивость типов получателя и ис-

точника. Так как получатель представляет собой адрес,  источ-

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

му адресу.  В  зависимости   от   реализуемого   языка   типы

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

выполнения присваивания. Например, если тип источника - целое

число, то  его можно сначала преобразовать в вещественное,  а

затем присвоить адрес, имеющему тип вещественного числа.

     2. Там,  где это необходимо, проверяются правила области

действия. В Алголе 68 источник не может иметь меньшую область

действия, чем получатель. Например, в

                     begin ref real xx;

                        begin real x;

                           xx := x

                        end

присваивание недопустимо, и это может быть обнаружено во вре-

мя компиляции,  если  в  таблице  символов или в нижнем стеке

имеется информация об области  действия.  Однако  в  процессе

компиляции нельзя  обнаружить  все  нарушения  правил области

действия, и в некоторых случаях  для  проверки  этой  области

приходится создавть код во время прогона.

     3. Генерируется код для присваивания, имеющий форму

                       ASSIGN type,S,D

где S - адрес источника, а D - адрес получателя.

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

присвоение имеет значение ), статические характеристики этого

значения помещаются в нижний стек.

     II. Условные зависимости

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

тор, аналогичный следующему:

                    if B then C else D fi

     При генерации кода для  такой  условной  зависимости  во

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

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

     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. В  каждом блоке без внутренних блоков каждый идентифика-

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

няется и для меток).

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

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

должно быть описание этого идентификатора.

     3. Все  переменные  в  левых частях при присваивании должны

быть одного типа.

     4. Количество индексов у переменных с индексами должно сов-

падать с числом пар граничащих массивов.

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

процедур должны совпадать с количеством и типом  форм.  парамет-

ров, приведенных в описаниях процедур.

     6. Фактический параметр,  который соответствует формальному

параметру,  вызываемому по наименованию и встреч. в левой части,

обязан быть переменной (а не выражением).

     7. Идентификаторы,входящие  в выражение для границ в описа-

ниях массивов, должны быть описаны в одном из объемлющих блоков.

                            ЛЕКЦИЯ 18

                   ГРАММАТИКИ ВАН ВЕЙНГААРДЕНА

    ОПРЕДЕЛЕНИЕ: Грамматика ван Вейгаардена - это две  связанные

грамматики,  которые  называются метаграмматикой или грамматикой

метаязыка и строгой грамматикой ( грамматикой ) языка:

              Gv = < Gm, Gst >.

             Gm  = < Vs, Vm, Pm, M >

    Vs - конечное множество  малых  синтаксических  знаков  (  в

русском  издании "Пересмотренного сообщения об Алголе" множество

маленьких букв русского алфавита ).

    Vl -  конечное  множество  больших синтаксических знаков ( в

русском издании "Пересмотренного сообщения об Алголе"  множество

больших букв русского алфавита ).

    Vm - конечное множество метапонятий:

         Vm с Vl+;

    Vh - конечное множество гиперпонятий:

         Vh с ( Vm U Vs )*;

    Ah - конечное множество гиперальтернатив:

         Ah с Vh ( {,} Vh )*

        ( гиперпонятия в гиперальтернативах отделяются запятыми ).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16