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

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

         Ph с Vh {:} Ah ( {;} Ah )* {.}

        ( гиперальтернативы  в гиперправилах отделяются точкой с

          запятой, в конце гиперправила ставится точка ).

     Правила в  метаграмматике ( гиперправила ) также называются

формами или схемами.

    Pm - конечное множество правил метапорождений:

         Pm с Vm {::} Vh ( {;} Vh )* {.}

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

         M с Vm

    L ( Gm ) - ( в общем случае бесконечное )  множество  терми-

нальных метапорождений метапонятия M: L ( Gm ) с Vs*

    Пусть метапонятие MM имеет одно или более  вхождений  в  ги-

перправило h. Согласованной заменой метапонятия MM в гиперправи-

ле h назовем замену всех его вхождений одним и тем же терминаль-

ным порождением Tm с L ( Gm ).

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

ванной замены всех входящих в него метапонятий.

    Понятием называется непустое ( протопонятие ), если для него

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

раз является бесконечным множеством нетерминалов Vn грамматики.

    Gst = < Vt, Vn, P,  S >

    Vt - конечное множество терминалов;

    Vn - множество нетерминалов;

    P  - множество правил;

    S -  начальный символ грамматики

    Множество правил порождения P определяется тем, что

        P с Vn {:} A ( {;} A )* {.},

    где  Vn с Vs+ - множество понятий,

        A с F ( {,} F )* - множество альтернатив,

        F = 0 U Vt u Vn U B

        0 - пустое множество;

        B - множество тупиковых протопонятий.

    Для тупикового протопонятия никакое  правило  порождения  не

может быть выведено.  Возможности тупиков используются в системе

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

    Предикат - это протопонятие имеющее одну из форм:  where а (

если верно что а ) или unless а ( если неверно что а ).

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

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

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

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

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

ния.

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

оператора присваивания PASCAL-подобного языка  и  контролирующую

следующие  контекстные условия (3-го рода по классификации Брат-

чикова)

   1. Арифметическое выражение может состоять из выражений  при-

надлежащих лишь арифметическим типам

   2. Логическое выражение может состоять из выражений лишь  ло-

гических типов

   3. Не допускается смешивать в арифметических  выражения  раз-

личные типы

   4. Переменной можно присваивать значение того же либо  струк-

турно эквивалентного типа

                     Грамматика 1-го уровня

             Нетерминальные символы метаграмматики

   TYPE   тип

   ATYPE  арифметический тип

   PTYPE  указательный тип ( указатель на нечто)

                     Правила метапорождения

TYPE ::= ATYPE | PTYPE | bool

PTYPE ::= pointer TYPE

ATYPE ::= int | float

                     Грамматика 2-го уровня

     Реализация контексных  условий  основана  на  том что имена

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

сут в себе информацию о типе соответствующих объектов

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

ass оператор присваивания

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

e TYPE правая часть оператора присваивания (lvalue типа TYPE)

e<n> TYPE выражения различных уровней приоритета

t TYPE терм (константа, переменная или выражение в скобках)

mulop операция *,/

addop +,-

compop <,>,>=,<=

boolop AND,OR

ass := le TYPE, ':=', e TYPE

le TYPE := id TYPE ; '^',le pointer TYPE

e1 ATYPE := e1 ATYPE, mulop, t ATYPE;t ATYPE

e2 ATYPE := e2 ATYPE, addop, e1 ATYPE; e1 ATYPE

t ATYPE := symbol id ATYPE; symbol const ATYPE; '(', e2 ATYPE, ')'

e3 bool := e3 ATYPE,compop ,e2 ATYPE ; symbol id bool ;symbol const bool

e4 bool := e4 bool ,boolop, e3; e3

e TYPE := e2 TYPE ; e4 TYPE

mulop := '*';'/'

addop := '+';'-'

compop := '<' ;'>';'<=';'>=';'='

boolop := 'AND' ;'OR'

      Задача построения  (конечной) контекстно-свободной грамма-

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

конечных  множеств терминальных и нетерминальных символов исход-

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

дет соответствовать терминалу либо нетеминалу строящейся грамма-

тики.  Каждому классу соответствует цепочка символов метаграмма-

тики, из которой он выводится.

                   Нетерминалы КС-грамматики

ASS соответствует ass

LE ->le TYPE

E -> e

EN -> enTYPE

T -> t TYPE

MULOP ->mulop

ADDOP ->addop

COMPOP ->compop

BOOLOP ->boolop

      Выполнив указанные выше замены в продукциях 2-го уровня (и

отбросив продукции грамматики 1-го уровня), получим

ASS := LE ':='E TYPE

LE := id | ^ LE

E1 := E1 MULOP T | T

E2 := E2 ADDOP E1 | E1

T  :=id | const | (E2)

E3 :=E3 COMPOP E2 | id | const

E4 :=E4 BOOLOP E3 | E3

E := E2 | E4

MULOP := '*' | '/'

ADDOP := '+' |'-'

COMPOP := '<' ;'>';'<=';'>=';'='

BOOLOP := 'AND' ;'OR'

     В заключение хотелось бы отметить различия в синтаксисе за-

писи правил КСграмматики и грамматики ван Вейнгардена.  В первой

разделителями символов и метасимволов являются пробелы, раздели-

телями альтернатив являются знаки '|'.  Терминальные символы за-

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

лы-большими.  При записи грамматик ван Вейнгардена разделителями

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

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

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

ся с терминала symbol.

                            ЛЕКЦИЯ 19

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

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

вания вида ( например , преобразование типов в языке СИ) :

   Пусть int  i,j;

         char c,ch;

т.е. описываем  переменные i и j как целые,а c и ch как символь-

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

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

другого вида ,  в языке СИ необходимо в правой части перед соот-

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

быть приведена переменная из правой части.  Разумеется, этот тип

-  тип переменной в левой части выражения .  Если же имеет место

присвоение типа (2) ,т.е.  типы переменных правой и левой частей

совпадают,то тип в правой части не указывается.

  (1) c= (char) i;

  (2) ch=c;

  (3) ch= (char) j+c;

  (4) i=(int) ch;

  (5) c= (char) 20;

   Для данных  выражений типы правых частей не везде совпадают с

типами соответствующих им левых  частей.  Необходимо  произвести

преобразование  типа  левой части к типу идентификатора в правой

части.

   assign   : е TYPE l,'=', e TYPE mod.        /*Задание

                              конструкций присваивания*/

   e TYPE l : id./*В левой  части конструкции может быть

                                  только идентификатор*/

             /*Правая часть конструции может быть предс-

               тавлена:                               */

   e TYPE mod: e TYPE r ;    /* выражением  типа  правой

                                             части-(1)*/

               TYPE nomber; /*числовым типом*/

              '(',TYPE,')',e TYPE1 r;/*конструкцией вида

               (тип)выражение_типа_отличного_от_типа_ле-

               вой_части -(4)*/

               '(',TYPE,')',TYPE1 nomber. /*конструкцией

               вида ( тип) номер,имеющий тип,отличный от

               типа левой части конструкции -(5)      */

   e TYPE r : e TYPE l,operation, e TYPE1 l;/* выражение

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

              типом, аналогичным типу  левой части  (2),

              операцией - (3),выражением типа ,отличного

              от типа левой части.                    */

      TYPE  : int symbol;/* в данном  примере  могут ис-

                            пользоваться   данные  цело-

                            численного  или  символьного

              сhar symbol.  типов                     */

       Где :

            е- expression -выражение,

            TYPE- тип,

            l- left -левый,

            r- right - правый,

            mod- modern -новый(англ.),тогда

  e TYPE l -выражение, тип которого  может встретиться в

            левой части выражения,

  e TYPE r -обозначает  выражение , тип  которого  может

            встретиться  в  правой  части  ( простое ) ,

 e TYRE mod-обозначает  выражение , тип  которго  может

            встретиться в правой части  ( составное  или

            простое, т.е.,  может  быть  состоять только

            из выражения типа правой части или из приве-

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

            нужному  типу и типа левой части переменных.

            РАСПРЕДЕЛЕНИЕ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ

                           1. ДИСПЛЕЙ

               1.1 Взаимодействие Дисплея и стека

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

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

тить соответствующие адреса, где это необходимо, в таблицу симво-

лов. Фаза распределения памяти почти не зависит от языка и  маши-

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

имеющих блочную структуру и реализуемых на многих  типичных  ЭВМ.

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

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

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

структурой, а машина имеет линейное запоминающее  устройство,  то

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

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

типа.

     Ниже мы рассмотрим классическую структуру стека времени про-

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

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

называемой "кучей".

     В каждом компиляторе предусмотрена схема распределения памя-

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

В Фортране память, выделенная для значений  идентификаторов,  ни-

когда не освобождается, так что здесь подходящей  структурой  для

нее является одномерный массив. Если считается, что массив  имеет

левую и правую стороны, память можно выделять слево направо.  При

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

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

     INTEGER A,B,X,Y

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

     ┌───┬───┬───┬───┬───────────────

     │ A │ B │ X │ Y │

     └───┴───┴───┴───┴───────────────

                       ^

                       │

     Рис. 20.1 Схема выделения памяти в Фортране

     Такая схема не учитывает тот факт, что рабочая  память  (па-

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

весьма неэффективна (в смысле использования  объема  памяти)  для

языка с блочной структурой.

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

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

оптимальным решением было бы разрешить указателю в  вышеприведен-

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

Такой механизм распределения эквивалентен стеку  времени  прогона

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

няющимся снизу вверх.

     │   │      │   │      │   │     (1) begin real x,y

     │   │      │   │      │   │                .

     │   │      ├───┤      ├───┤                .

     │   │      │ d │      │ q │                .

     │   │      ├───┤      ├───┤     (2)     begin int c,d

     │   │      │ c │      │ p │                   .

     ├───┤      ├───┤      ├───┤                   .

     │   │      │   │      │   │             end;

     │   │      │   │      │   │     (3)     begin int p,q

     │ Y │      │ Y │      │ Y │

     ├───┤      ├───┤      ├───┤                   .

     │   │      │   │      │   │                   .

     │   │      │   │      │   │             end;

     │ X │      │ X │      │ X │                .

     └───┘      └───┘      └───┘                .

                                         end.

      (1)        (2)        (3)

     Рис. 20.2 Схема распределения памяти под переменные  в  раз-

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

     На рис. 20.2 показаны "моментальные снимки" стека  фрагмента

программы во время прогона.

     Часть стека, соответствующую определенному  блоку,  называют

РАМКОЙ стека. Считается, что указатель стека  показывает  на  его

первый свободный элемент.

     Кроме указателя стека, требуется также указатель на дно  те-

кущей рамки (УКАЗАТЕЛЬ РАМКИ). При входе в  блок  этот  указатель

устанавливается равным текущему значению указателя стека. При вы-

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

чению, соответствующему включающему блоку.

     Указатель рамки включающего блока может храниться  в  нижней

части текущей рамки стека, образуя  часть  статической  цепи  или

(как мы будем считать) массива, который называется ДИСПЛЕЕМ.

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

телей на начало рамок стека, соответствующих всем текущим  блокам

(рис. 20.3).

                    │   │

                    │   │

                    │   │

     │  │           ├───┤

     │  │           │ q │

     │  │           ├───┤

     │  │           │ p │

     │  │     /───> ├───┤

     │  │    /      │   │

     ├──┤   /       │ Y │

     │  │──/        ├───┤

     ├──┤           │   │

     │  │─────────> │ X │

     └──┘           └───┘

   Дисплей           Стек

     Рис. 20.3 Схема связи Дисплея и стека  во  время  выполнения

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

     Это несколько упрощает перенастройку указателя рамки при вы-

ходе из блока.

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

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

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

     Рассмотрим следующий отрезок программы на языке Алгол-60:

     ...

     begin int n; read(n);

          [1:n] int numbers;

          real p;

          begin real x,y;

     ...

     Место для numbers должно выделяться в первой рамке стека,  а

для x и y - в рамке над ней. Но во время  компиляции  неизвестно,

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

чисел.

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

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

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

Однако этого обычно не делают, возможно, из-за тех проблем, кото-

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

ся и уменьшающегося стека во время прогона.

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

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

при прогоне - динамическую память над статической в каждой рамке.

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

где начинаются рамки (кроме первой), но можем распределять стати-

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

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

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

но установить так, чтобы он указывал на начало новой рамки  (рис.

20.4).

                                          │ Рамка 2

                      │       │           │

                      │       │           │

                      │       │          /

                      ├───────┤          \

                      │   y   │ Динами-   │

                      ├───────┤           │

                      │   x   │ ческая    │

                /───> ├───────┤           │

     │     │   /      │ Числа │ память     > Рамка 1

     │     │  /       │       │           │

     ├─────┤ /        ├───────┤ - - - -   │

     │     │/         │   p   │ Стати-    │

     ├─────┤          ├───────┤ ческая    │

     │     │──\       │   n   │ память    │

     └─────┘   \────> └───────┘          /

     Дисплей            Стек

     Рис. 20.4 Схема связи Дисплея и стека во время выполнения  с

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

     На этом рисунке массив занимает только динамическую  память.

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

компиляции, например, его размерность (а следовательно,  и  число

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

элемента массива она может потребоваться. Во многих  языках  сами

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

ка мы знаем их число, и для значений этих границ  можно  выделить

статическую память. Тогда мы вправе считать, что  массив  состоит

из статической и динамической частей. Статическая  часть  массива

может размещаться в статической части рамки, а динамическая  -  в

динамической. Кроме информации о границах,  в  статической  части

может храниться указатель на сами элементы массива.  Модифицируем

рис. 20.4 в рис. 20.5 с учетом этих особенностей.

                                                │ Рамка 2

                           │        │           │

                           │        │           │

                           │        │          /

                           ├────────┤          \

                           │   y    │ Динами-   │

                           ├────────┤           │

                           │   x    │ ческая    │

                     /───> ├────────┤           │

          │     │   /      │Элемен- │ часть      > Рамка 1

          │     │  /       │ты чисел│           │

          ├─────┤ /    ┌─> ├────────┤ - - - -   │

          │     │/     │   │   p    │ Стати-    │

          │     │      │   ├────────┤           │

          │     │      │   │ Стат.  │           │

          │     │      └───│ часть  │ ческая    │

          │     │          │ чисел  │           │

          ├─────┤          ├────────┤           │

          │     │──\       │   n    │ часть     │

          └─────┘   \────> └────────┘          /

          Дисплей            Стек

     Рис. 20.5 Схема связи Дисплея и стека во время выполнения  с

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

частей

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

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

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