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

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

символа в цепочке польской  записи.  Если  операнд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 │    │   +    │ 4 │  K  │

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

│ 8  │ 16 │    │   -   │ 41 │ 7  │    │   :=   │ 5 │ L25 │

├────┼────┼────┼───────┼────┼────┼────┼────────┼───┴─────┘

│ 9  │ 2  │ 3  │   A   │ 42 │ 1  │ 64 │   64   │

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

│ 11 │ 13 │    │ ADEC  │ 44 │ 9  │    │   BR   │

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

│ 12 │ 2  │ 4  │   K   │ 45 │ 2  │ 1  │   I    │

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

│ 14 │ 1  │ 0  │   0   │ 47 │ 2  │ 1  │   I    │

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

│ 16 │ 7  │    │  :=   │ 49 │ 1  │ 1  │   1    │

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

│ 17 │ 2  │ 1  │   I   │ 51 │ 14 │    │   +    │

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

│ 19 │ 2  │ 2  │   Y   │ 52 │ 7  │    │   :=   │

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

│ 21 │ 16 │    │   -   │ 53 │ 2  │ 1  │   I    │

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

│ 22 │ 1  │ 45 │   45  │ 55 │ 2  │ 1  │   I    │

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

│ 24 │ 8  │    │  BMZ  │ 57 │ 1  │ 1  │   1    │

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

│ 25 │ 2  │ 4  │   K   │ 59 │ 14 │    │   +    │

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

│ 27 │ 2  │ 4  │   K   │ 60 │ 7  │    │   :=   │

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

│ 29 │ 2  │ 1  │   I   │ 61 │ 1  │ 5  │   5    │

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

│ 31 │ 2  │ 2  │   7   │ 63 │ 10 │    │  BRL   │

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

│ 33 │ 16 │    │   -   │ 64 │ 12 │    │ BLCEND │

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

│ 34 │ 2  │ 3  │   A   │    │    │    │        │

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

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

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

    6 = SUBS,  7 = :=, 8 = BMZ, 9 = BR, 10 = BRL, 11 = BLOCK,

    12 = BLCKEND, 13 = ADEC, 14 = +, 15 = *, 16 = -.

     Константа занимает два слова:  первое 1,  второе - значение

ее.  Для идентификатора аналогично: первое слово 2, второе - ад-

рес (индекс) элемента таблицы символов идентификатора.

     Метки, генерируемые  для  внутренних  переходов равны соот-

ветств. номерам ячеек.

                            ТЕТРАДЫ.

     1) Арифметические выражения:

        (<оператор>,<операнд1>,<операнд2>,<результат>)

     т.о. 1. А * В => *,А,В,Т, где Т некоторая переменная, кото-

             рой присваивает результат вычисления А * В.

          2. А * В + С * D => *, A, B, T1   ┐  тетрады располагаются в

                              *, C, D, T2   ├  том порядке, в котором

                              +, T1, T2, T3 ┘  они должны вычисляться

      Для унарных  операторов  (-А)  <операнд2>  остается пустым

     (-,А, ,Т) 2)

     2) Тетрады для других операторов.

  1] BR i                  - переход на i-ю тетраду

  2] BZ i,P                - переход по "0" (BP - по "+", BM - по "-")

  3] BG i, P1, P2          - переход, если значение в P1 > чем в P2

                                         ( BL - < , BE - = )

  4] BRL P                 - переход на тетраду, номер которой в Р-м

                             элементе таблицы символов

  5] +[*,/,-] P1, P2, P3

  6] := P1,   ,P3

  7] CVRI P1,  ,P3         - преобразование значения, описанного в Р1,

                             из REAL в INT и запоминание в Р3

  8] BLOCK

  9] BLCKEND

 10] BOUNDS P1, P2         - Р1 и Р2 описывают граничную пару массива

 11] ADEC P1               - массив описан в Р1. Если он имеет размер-

                             ность n, то этой тетраде предшествует опе-

                             ратор BOUNDS, задающий n граничных пар.

                         ИНДЕКСИРОВАНИЕ

     Пример С := А [i, B[j]], если d1

            описывает диапазон изменения          *,  ,d1,T1

            второго индекса массива А, то         +,T1,B[j],T2

            получим следующее представление      :=,A[T2], ,C

     (1) BLOCK                    (10) + K,T4,T5

     (2) -I,j,T1                  (11) := T5, , K

     (3) BOUNDSI,T1               (12) BR18

     (4) ADEC A                   (13) +I,1,T6

     (5) := 0, ,K                 (14) := T6, ,I

     (6) -I,j,T2                  (15) +I,1,T7

     (7) BMZ13,T2                 (16) := T7, ,I

     (8) -I,j,T3                  (17) BRL L

     (9) *A[T3],6,T4              (18) BLCKEND

                             ТРИАДЫ

                 <оператор><операнд1><операнд2>

     В ней нет поля результата. За счет этого сокращается  запись

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

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

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

жается после его использования.

     (1) BLOCK                    (10) + K,(9)

     (2) -I,j                     (11) := (10), K

     (3) BOUNDS 1,(2)             (12) BR (18)

     (4) ADEC A                   (13) + I, 1

     (5) := 0,K                   (14) := (13), I

     (6) -I,j                     (15) + I, 1

     (7) BMZ(13),(6)              (16) := (15), I

     (8) -I,j                     (17) BRL L

     (9) * A[(8)],(6)             (18) BLCKEND

     Здесь (2) - ссылка на результат  второй  триады.  Компилятор

заводит новый тип операнда для  результата  триад  (первое  слово

операнда)

                             ДЕРЕВЬЯ

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

корню которого соответствует последняя триада. Каждая i-я  триада

соответствует поддереву, оператор триады - корень поддерева, опе-

ранд - либо идентификатор(лист), либо номер  триады,  описывающий

поддерево. От того, как рассматриваются  триады  (как  последова-

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

щественным образом зависит  генерируемый  объектный  код.  Дерево

иногда позволяет сгенерировать более эффективный объектный код.

     Пример 1.      A * B + C - D * E

               -

           ┌───┴───┐             (1)  ( * A,B )

           +       *             (2)  ( + (1),C )

        ┌──┴──┐ ┌──┴──┐          (3)  ( * D,E )

        *     C D     E          (4)  ( - (2),(3) )

     ┌──┴──┐

     A     B

     Пример 2        BEGIN A := B; B := C; D := C; END

                        <составная инстр.>

         ┌───────────────────────┼───────────────────────┐

       BEGIN              <список инстр.>               END

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

              <инстр.>  <инстр.>   <инстр.>   <инстр.>

  Дерево         │         │          │          │           Триады

 --------       :=        :=         :=       <пусто>       --------

               ┌─┴─┐     ┌─┴─┐      ┌─┴─┐                  (1) (:=B,A)

               A   B     B   C      D   C                  (2) (:=C,B)

                                                           (3) (:=C,D)

     При представлении инструкций, блоков, описаний и т.д.  триа-

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

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

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

то время как в триадах эти связи подразумеваются.

             Промежуточная форма исходной программы

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

внутреннюю форму, удобную для простой машинной  обработки.  Внут-

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

зависит от дальнейшего использования. Это может быть дерево,  от-

ражающее синтаксис исходной программы. Это  может  быть  исходная

программа в польской записи. Используется также  форма  -  список

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

нения.

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

программа преобразована в дерево,  называемое  синтаксическим.  В

этом дереве внутренние вершины в  основном  соответствуют  опера-

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

входов в таблицу имен. Структура синтаксического дерева  отражает

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

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

колько способов. Во внутренней форме операторы не изменяют  поря-

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

вещи: операторы и операнды. Различие состоит в том, как эти  опе-

раторы и операнды соединяются.

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

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

(переменные, константы, процедуры и т.д.).  Компиляторы,  осущес-

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

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

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

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

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

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

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

пользуется польская запись. Она имеет ряд преимуществ  перед  ин-

фиксной: формула может быть записана без скобок; эта форма  пред-

ставления очень удобна для ЭВМ со стековой адресацией; если  зна-

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

польская запись устраняет эту систему приоритетов).

     В польской записи операнды следуют непосредственно за опера-

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

где будут находиться все операнды,  встретившиеся  при  просмотре

выражения.

     Просмотр начинается с самого левого символа. Прочитав его  и

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

такова:

     1) если сканирующий символ - идентификатор или константа, то

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

щему;

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

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

полученный результат;

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

няется к верхнему операнду в стеке, который затем  заменяется  на

полученный результат.

                             Тетрады

     Для бинарных операций удобной формой представления  являются

тетрады. Тетрада имеет вид: <оператор> <операнд1> <операнд2>

     В тетраде отсутствует поле результата. Если позже  какой-ли-

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

нее непосредственно ссылаться.

     Существуют и другие формы внутреннего представления.

                             Деревья

     Мы опpеделили КС-язык, задаваемые некотоpой гpамматикой, как

множество теpминальных цепочек,  котоpые  можно  вывести  из  на-

чального символа. Можно постpоить деpево вывода цепочки  КСязыка.

Это легко сделать, интеpпpетиpуя подстановки, как  шаги  постpое-

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

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