
                             Создание компилятора
                                 языка МИЛАН.

    Источник: А.М.Дворянкин, "Основы трансляции", учебное пособие,  Волгоград-
ский государственный технический университет, 1997, 80 стр.

    Для построения компилятора с языка МИЛАН необходимо определить выходной
язык - язык команд некоторой ЭВМ. Определим ЭВМ,  как некоторую стековую маши-
ну, имеющую три вида памяти:

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

    Память адресуется пословно.  В слове памяти для  хранения  программ  может
храниться одна одноадресная команда (код операции и адрес операнда).  В  слове
памяти для хранения данных и в слове стековой  памяти  может  помещаться  одно
число. Определим систему команд процессора машины:

    LDA,a - (load - загрузить) содержимое слова памяти с адресом a  помещается
в стек.
    STA,a - (store - запомнить) из стека читается данное и помещается в  ячей-
ку памяти с адресом a.
    INP - (input - ввод) число с устройства ввода помещается в стек.
    OUT - (output - вывод) из стека читается число и  выдается  на  устройство
вывода.
    JMP,m - (jump - перейти) безусловная передача управления команде  с  номе-
ром (адресом) m.
    JMT,m - (jump-true - перейти,  если истина) условная передача  управления:
из стека читается данное,  если оно TRUE (равно 0),  то передается  управление
команде с номером m. Иначе выполняется следующая команда.
    JMF,m - (jump-false - перейти, если ложь) условная передача управления: из
стека читается число,  если оно FALSE (равно 1),  то передается управление ко-
манде с номером m. Иначе выполняется следующая команда.
    HLT - (halt - остановиться) останов процессора.
    ADD - (add - сложить) сложение: со стека снимается 2  числа,    эти  числа
складываются и результат засылается в стек.
    SUB - (subtract- вычесть) вычитание: со стека снимается 2 числа, из второ-
го числа первое и результат засылается в стек.
    MUL - (multiply - умножить) умножение: со стека снимаются два числа,  вто-
рое число делится на первое и результат засылается в стек.
    DIV - (divide - разделить) деление: со стека снимаются 2  числа,    второе
число делится на первое и результат засылается в стек.
    INV - (invert - инвертировать) инвертирование числа:  со  стека  снимается
число, умножается на -1 и результат засылается в стек.
    Все арифметические команды безадресные.  Они выбирают аргументы из стека и
результат посылают в стек. Верхний элемент стека - всегда второй операнд. Сле-
дующий за ним - первый операнд.
    CMP,s - (compare - сравнить) сравнение: со стека снимается 2 числа b и  a,
производится операция сравнения a с b с кодом s и результат заносится в  стек.
Коды операций сравнения определяются в таблице лексем.
    Сканер передает блоку генерации массив лексем,  массив  идентификаторов  и
массив констант.
    Синтаксические диаграммы компилятора представлены на рисунке.

      begin       L      end
 W: o───────>o────────>o───────>o
                         z01

        S
 L: o───────>o
    │   tz   │
    └<───────┘


      ud(k)     prsv                         E
 S: o────────>o───────>o────────────────────────────────────────────>┐
    │                                       z03                      │
    │                                                                │
    │ output     os        E       zs                                │
    ├────────>o───────>o───────>o───────>o──────────────────────────>┤
    │                                                 z04            │
    │                                                                │
    │ while       B       do        L                 od             │
    ├────────>o───────>o───────>o───────>o──────────────────────────>┤
    │  z05                z06                         z07            │
    │                                                                │
    │   if        B      then       L      else       L        fi    │
    └────────>o───────>o───────>o───────>o───────>o────────>o───────>┤
                 z06                     │  z08                z09   │
                                         │                           │
                                         │            fi             │
                                         └──────────────────────────>┘
                                                      z10

        E       otn(s)         E
 B: o────────>o───────>o────────────────>o──────────────────────────>o
                                                      z02

      ots(k)      T
 E: o────────>o───────>o────────────────>o═══════════════════════════o
    │                          z17       │                           │
    │             T                      │             T       ots(k)│
    └───────────────────────────────────>┴<───────o<────────o<───────┘
                 z16                         z15

        P
 T: o────────>o══════════════════════════o
              │                          │
              │             P      otu(k)│
              └<───────o<───────o<───────┘
                 z14

        os        E       zs
 P: o────────>o───────>o───────>o
    │                           │
    │                           │
    │           id(k)           │
    ├──────────────────────────>┤
    │           z11             │
    │                           │
    │           int(k)          │
    ├──────────────────────────>┤
    │           z12             │
    │                           │
    │           read            │
    └──────────────────────────>┘
                z13

    Для описания семантических функций будем использовать следующие  обозначе-
ния:
    A+i - адрес слова со значением i-ой константы;
    B+j - адрес слова со значением j-ого идентификатора;
    xC  - глобальная переменная - счетчик генерируемых команд (слова в  памяти
команд имеют адреса 1, 2, 3 и т.д); начальное значение xC=0;
    GEN(x,y) - функция генерации команды с кодом x и операндом  y  (операнд  в
некоторых командах может отсутствовать); счетчик команд xC увеличивается на 1,
формируется слово с командой и записывается по адресу xC в память команд;
    k,m,n,s - локальные переменные.
    Опишем семантические функции компилятора:
    z01: GEN(HLT,0) - сгенерировать команду останова.
    z02: GEN(CMP,s) - сгенерировать команду сравнения.
    z03: GEN(STA,B+k) - вершина стека - результат вычисления,  пересылается  в
слово памяти, отведенное для k-ого идентификатора.
    z04: GEN(OUT) - сгенерировать команду вывода результата вычисления E.
    z05: Запомнить xC+1 - адрес,  с которого начинается вычисление условия,  в
локальной переменной n.
    z06: GEN(JMF,0) - команда обхода конструкции L при значении условия FALSE.
Адрес перехода пока не известен. Он будет вычислен после окончания распознава-
ния всего оператора. В переменной m запоминается адрес этой команды.
    z07: GEN(JMP,n) - генерация команды возврата на проверку условия  повторе-
ния цикла.  Значение xC+1 заслать в поле операндов команды,  адрес которой был
запомнен в переменной m.
    z08: GEN(JMP,0) - генерация команды выхода из конструкции выбора.    Адрес
перехода пока не известен. Значение xC - адрес этой команды, запомнить в пере-
менной n.  В поле операнда команды,  адрес которой был запомнен в m,   заслать
значение xC+1.
    z09: В поле операнда команды, адрес которой в n,  заслать xC+1 - адрес ко-
манды, с которой будет начинаться реализация следующей конструкции.
    z10: В поле операнда команды, адрес которой в m,  заслать xC+1 - адрес ко-
манды, с которой будет начинаться реализация следующей конструкции.
    z11: GEN(LDA,B+k) - сгенерировать команду загрузки в стек  значения  k-ого
идентификатора.
    z12: GEN(LDA,A+k) - сгенерировать команду загрузки в  стек  значения  k-ой
константы.
    z13: GEN(INP,0) - сгенерировать команду ввода числа с устройства ввода.
    z14: Если k=0, то GEN(MUL), иначе GEN(DIV).
    z15: Если k=0, то GEN(ADD), иначе GEN(SUB).
    z16: k=0.
    z17: Если k=1, то GEN(INV).

    Пример:

    begin
       a:=1;
       b:=0;
       while a<=4 do
          b:=b+a*a;
          a:=a+1
       od;
       output(b)
    end

    После работы сканера построены: массив идентификаторов {a,b},  массив кон-
стант: {1,0,4} и массив лексем:

    1. (begin,0)  10. (while,0)  19. (id,1)    28. (od,11)
    2. (id,1)     11. (id,1)     20. (otu,0)   29. (tz,0)
    3. (prsv,0)   12. (otn,5)    21. (id,1)    30. (output,0)
    4. (int,1)    13. (int,3)    22. (tz,0)    31. (os,0)
    5. (tz,0)     14. (do,29)    23. (id,1)    32. (id,2)
    6. (id,2)     15. (id,2)     24. (prsv,0)  33. (zs,0)
    7. (prsv,0)   16. (prsv,0)   25. (id,1)    34. (end,0)
    8. (int,2)    17. (id,2)     26. (ots,0)
    9. (tz,0)     18. (ots,0)    27. (int,1)

    Рассмотрев работу компилятора,  используя синтаксические схемы и  описания
семантических функций, получим код программы:

    1. LDA,A+1     7. CMP,5      13. ADD       19. LDA,B+k
    2. STA,B+1     8. JMF,19     14. LDA,B+1   20. OUT
    3. LDA,A+2     9. LDA,B+2    15. LDA,A+1   21. HLT
    4. STA,B+2    10. LDA,B+1    16. ADD
    5. LDA,B+1    11. LDA,B+1    17. STA,B+1
    6. LDA,A+3    12. MUL        18. JMP,5

    Построенный компилятор обрабатывает только синтаксически правильные  прог-
раммы. Для того, чтобы компилятор обнаруживал синтаксические ошибки, необходи-
мо дополнить синтаксические диаграммы компилятора дополнительными дугами пере-
хода в ошибочных ситуациях и семантическими функциями сообщений об ошибках.
