31 декабря 2017

   Путь к самокомпиляции
Alone Coder

   Как  только я начал реализовывать типы,
компилятор стал стремительно пухнуть. Сох─
ранилась  первая версия на C++, сконверти─
рованная из  Delphi. Это было всего лишь 3
ноября  (проект  начат 14 сентября), а там
уже торчало12 модулей  толщиной 109 кило─
байт. Почему C++? Потому что система долж─
на  работать  под  Linux. А почему Delphi?
Потому что там проще начинать.Читабельнее.
   Мой  язык  тоже  был такой весь из себя
читабельный - с кучей ключевых слов на все
случаи жизни. За счёт этого в поле команды
я  ждал  именно  команду, а  не что-нибудь
иное.Достаточно было проверять 1-2 символа
команды, что я и сделал,когда избавился от
AnsiString.

   Некоторое  зондирование  масс показало,
что народ не хочет заново писать кодогене─
ратор с нашего фирменного языка высочайше─
го уровня (его название вам ничего не ска─
жет) на  промежуточный  язык, который  там
сейчас Си.В тот же момент на меня снизошло
откровение, что  без самокомпиляции я этот
шедевр вообще не отлажу.
   Обычно раскрутку новых языков для само─
компиляции  делают через написание первого
урезанного  компилятора  на  ассемблере. У
меня  уже был урезанный компилятор на C++.
Зачем писать новый? Вот я и не стал писать
новый. Я  переделал  его на C. И смог даже
скомпилировать  IAR'ом  и SDCC. Но на этом
мечты о постоянно висящей в48K памяти си─
стеме  разбились о реальность - размер ко─
да.
   Я перевалил  на ассемблер так много за─
дач (вплоть  до  временного хранения метки
вызова,  пока  вычисляются параметры), что
требовался вполне серьёзный ассемблер. Мо─
жно  было  догадаться, что он будет весить
не меньше, чем сам компилятор. И в48K они
вместе  не влезут. Даже неизвестно, влезет
ли ассемблер со всеми метками компилятора,
когда он будет этот компилятор ассемблиро─
вать. (Я не планировал линкер, вместо него
куски  кода должен был раскидывать загруз─
чик  в ОС - и то, если  в 48K памяти будет
действительно много программ.)
   Вообще  ассемблер может быть с процеду─
рами,  оптимизацией,  макросами, локалами,
автометками  и т.п., или вообще без всего,
даже может быть из токенизированного текс─
та  с разжёванными  выражениями  и метками
фиксированной  длины. А  можно было вообще
сделать компилятор без ассемблера.

   Чтобы долго не думать, я достал из кучи
выписок  проект ассемблера, транслирующего
из  полупереваренного  представления.  Это
когда-то  планировалось  на  замену ALASM.
Должно  было работать страшно быстро, обс─
луживая приходящие токены переходом по та─
блице. Правда, быстро  оно должно было ра─
ботать,если бы было написано на ассемблере
Z80. Я написал  это  на Си. И токенизатор- 
детокенизатор в комплекте.
   Токены  были выбраны с учётом следующих
ограничений:
  - токенизатор не знает коды команд;
  - токенизатор  видит  только  левый кон─
текст, поэтому  не  различает  омонимичные 
команды (например, есть куча разных команд 
LD );
  - детокенизатор (он же экспортёр) просто
подставляет   тексты  токенов  или  прямой 
текст  после  токена  "прямой  текст". Это 
чтобы будущая оболочка ассемблерного реда─ 
ктора  легко  отображала  токенизированное 
представление. 
   Чтобы  это   реализовать,  понадобились
невидимые  токены форматов команд, которые
пишутся  после тела команды, а ещё форматы
выражений, которые  пишутся  после второго
операнда у сложения и т.п. Форматов оказа─
лось так много, что еле хватило 256 кодов.
Но в общем к концу года всё заработало.
   Только  в коде ассемблера былswitch по
токенам.
   Это  был  уже  несколько другой уровень
"простоты" языка.switch можно заменить на
статически  инициализированный массив ука─
зателей на функции, но это  тоже надо реа─
лизовать, и работать будет медленнее - вы─
зов вместо перехода (перехода по указателю
в Си нет). А можно не заменять, тогда надо
уже на уровне ассемблера поддержать вычис─
ляемые метки. Ведь ассемблер получил бы на
вход только имя текущегоswitch'а и имено─
ванную  константу  для веткиcase, которую
надо вычислить и приклеить к имени. Писать
в case  прямо числа было бы неподдерживае─
мо. А так у меня уже был файл со всеми то─
кенами из токенизатора.

   Итак, я  должен  был написать не просто
новый язык,а язык,совместимый с Си,с почти
сравнимыми возможностями. Именно тогда - и
не раньше - я выхожу на самокомпиляцию.

  24.10.2016:
  - убрано ограничение на чередование слов
и знаков в лексере.Теперь синтаксис такой:
var int a
var byte bb
var long LONA
var int array[15]

module vasya(

proc xx local()
(
)

func byte byter local()
(
 var byte byterbb
 let byterbb=byterbb
 let LONA$=LONA$
{let bb$=$3a^(bb$^
        ?byter({stacked}{byterbb=%1111})
             )}
 let bb$=%111^bb$^byterbb
)%101

func long longer
local(long L1 long L2){recursive local}
(
let a$=(+1);
let LONA$=?longer()+$01020304;
let bb$=(%1);
)LONA$

func int dup local(int r){recursive local}
(
var int p1
var uint p2
if(<p1#+ <<< 0)(
  let p2=p1 &+$ffff;
)~()
*(@array$+[7*WORDSIZE])(555){write array}
let p2=*(+@array$+p1*+[WORDSIZE]);
                        {read from array}
)(p1+p1)

  25.10.2016:
  - слово local больше не нужно для нере─
курсивных процедур
  - команда записи в память теперь начина─
ется со словаpoke (как в Бейсике):
   poke (@array$+[7*WORDSIZE]),555
  - выделен   модуль typecodes  с  кодами
типов,  он   используется   в compiler  и
emitcommands

  26.10.2016:
  - равенство и неравенство пишутся как==
и!= (как в Си)
  - полноценная  работа  с массивами через
a[N] (как в Си)
  - реализован давно добавленный типBOOL.
Была  идея  хранить  его прямо во флаговом
регистре (проще всегоCY ), тогда if/while
прямо по флагу:
 AND:
   jr FALSE,$+2+2
   pop af
   push af
   pop bc
 OR:
   jr TRUE,$+2+2
   pop af
   push af
   pop bc
 XOR (только для флага в CY):
   jr FALSE,$+2+3
   pop af
   ccf
   push af
   pop af
 pushvar (только для флага в CY):
   push af;зависит от типа выше
   ld a,(var)
   rlca
 popvar (только для флага в CY):
   rrca
   ld (var),a
   pop af;зависит от типа выше
 LESS (старое меньше нового):
    ;если leftsaved=FALSE
    ;ex de,hl
    ;pop hl
   or a
   sbc hl,de
 MORE (новое меньше старого):
    ;если leftsaved=FALSE
    ;ex de,hl
    ;pop hl
   ex de,hl
   or a
   sbc hl,de
 MOREEQ (старое >= нового):
    ;если leftsaved=FALSE
    ;ex de,hl
    ;pop hl
   or a
   sbc hl,de
   ccf
 EQ:
    ;если leftsaved=FALSE
    ;ex de,hl
    ;pop hl
   or a
   sbc hl,de
   jr z,$+2+1;CY=0
   scf
   ccf
 NOTEQ:
    ;если leftsaved=FALSE
    ;ex de,hl
    ;pop hl
   or a
   sbc hl,de
   jr z,$+2+1;CY=0
   scf
Но я решил, что проще  в аккумуляторе (как
байтовый тип)

  27.10.2016:
  ->= и <= (как в Си)
  -repeat .. until (как в Паскале)
  - в  команду while добавлено слово loop
(там, где в Паскале стоитdo, но do мешает
совместимости с Си)
  - в командуif добавлено слово then (как
в Паскале)
  - при  вызове  рекурсивных функций после
имени  функции  пишется словоrecursive, а
stacked не пишется
  - попытка убрать все повторные обращения
к строкам, чтобы можно было их стримить из
входного  файла (приклеивание областей ви─
димости планировалось возложить на ассемб─
лер)

  28.10.2016:
  - блоки  команд  выделяются не круглыми,
а фигурными скобками (как в Си). Фирменный
вложенный  комментарий  фигурными скобками
теперь оформляется как{ ... }
  -poke теперь выглядит так (совместимо с
Си):
 poke *(a$)=( " as" " ) {write memory}
  - определение  метки для перехода теперь
выглядит  не  как :mylabel , а  как LABEL
mylabel: (совместимо с Си)
  - глобальные  переменные начинаются  с_
(сначала  сделал  с  точки,  но  передумал
из-за несовместимости с Си)
  - функции  в выражениях вызываются через
префикс@ (был ? , он оставлен для булевых
констант/*?*/_TRUE и /*?*/_FALSE ),а про─
цедуры вызываются черезCALL (совместимо с
Си)
  - в  определении  функции  вместо  блока
local теперь  обычное объявление локальных
переменных в теле черезRECURSIVEVAR и фи─
гурную  скобку после объявления (ограничи─
вает место,где локальные переменные сохра─
няются в стеке, а потом восстанавливаются)
  - поддерживаются (и рекомендуются) кома─
нды  большими буквами (как в Обероне, плюс
обычно в Си дефайны именно большими буква─
ми)
  - все несовместимые с Си закорючки можно
экранировать комментарием/*...*/ ,который
для NedoLang'а - не комментарий. Настоящий
комментарий -/**...*/
   Чтобы  понять идею совместимости своего
языка  с Си, ср. пример  из  оригинального
Bourne Shell: 

#define BEGIN  {
#define END    }
#define SWITCH switch(
#define IN     ){
#define ENDSW  }
#define FOR    for(
#define WHILE  while(
#define DO     ){
#define OD     ;}
#define REP    do{
#define PER    }while(
#define DONE   );
#define LOOP   for(;;){
#define POOL   }

  29.10.2016:
  - командаreturn перенесена в тело функ─
ции (как в Си)
  - числовые константы совместимы с Си

  31.10.2016:
  - убрана   зависимость   от   библиотеки
SysUtils (функцияIntToStr ) 
  - в  рекурсивных  процедурах  вычисления
выражения убрана локальная строковая пере─
менная

  01.11.2016:
  - убраны  все  локальные строковые пере─
менные, для этого вif и т.п. генерируются
специальные    метки    для    ассемблера:
@TEMPELSE, @TEMPENDIF...

  02.11.2016:
  - при вызове функции пишется тип функции
и параметров
  - строковые константы работают: компили─
руются с автометкой

  03.11.2016 - компилятор   перенесён  из
Delphi в C++ Builder 

  05.11.2016 - строкиAnsiString заменены
на MYSTRING  (определено  какchar*, но с
длиной  в первом байте), первая компиляция
на  IAR (для  этого  написан  свой  модуль
syscalls  со строковыми и файловыми проце─
дурами, последние в виде заглушек)

  22.11.2016 - создал проект-песочницу на
C++, где  экспериментировал, какие обороты
вообще  может  съесть компилятор. Такое он
ест:
    i=+(uint)+(uint)0;
    j = + +i;
    k = + -i;
   А  вот  фигурные  скобки в произвольном
месте - нет.  А  я так хотел ими экраниро─
вать  сишный код, который не должен видеть
NedoLang. 
   Но компиляторы вообще бывают разные.

  23.11.2016
  - появились указатели (типыpint и т.п.)
  - переменные   выгружаются  в  отдельный
ассемблерный  файл  (до этого они выгружа─
лись из памяти в конце компиляции,а у меня
всё ещё были надежды избавиться от таблицы
меток в компиляторе благодаря ручному про─
писыванию типов в обращениях)

  24.11.2016 - паскалевский  формат строк
заменён на сишный

  25.11.2016:
  - добавлена  командаbreak для выхода из
циклов, потому что я не смог избавиться от
break  везде  в компиляторе. Лучшее, что я
придумал  вместо break , - сложный формат
цикла с предусловием:
//сравнение строк 
//а) символы не совпали (не годно) 
//б) символы совпали (продолжаем,если 
//ненулевые, иначе годно) 
WHILE((
 PRECOND(//precond1
   LET c1=s1[i+FIRST],
   LET c2=s2[i]
 ),COND(c1==c2) LUCK(//cond1==TRUE
                    //(одинаковые символы)
   COND(c1!='') LUCK(//cond2==TRUE
                      //(not end)
     LET i=i+1
   )FAIL(LET result=TRUE),NODO
                            //cond2==FALSE
                           //(end)
 )FAIL(LET result=FALSE),NODO
                            //cond1==FALSE
                  //(неодинаковые символы)
))LOOP{
}
   Всё понятно? Нет? Ладно,дам подсказку:)
#define PRECOND /**/
#define COND /**/
#define LUCK ?
#define FAIL :(
#define NODO FALSE)
   К сожалению, фигурные скобки нельзя ис─
пользовать в тернарном операторе.
  -if теперь заканчивается endif , а else
не обязательно

  30.11.2016 - написаны токенизатор и де─
токенизатор (не отдельно, а  в составе той
же программы)

  01.12.2016 - написан  ассемблер (тоже в
составе)

  02.12.2016 - написан мануал

  05.12.2016:
  - убраны@TEMPELSE,@TEMPENDIF ...,вместо
них нумерованные метки
  - добавлен комментарий// до конца стро─
ки
  - добавлена командаasm

  12.12.2016 - багфиксы в токенизаторе

  13.12.2016 - написал  в отчёте примерно
следующее:
  "Написание  полноценного  компилятора C
или C++ - огромная  задача, требующая про─
фессиональных  программистов. Помимо боль─
шого объёма стандарта языка проблема ещё в
том, что язык содержит множество тонкостей
в разборе текста  и работе с типами, дово─
льно сложных в реализации. Но поскольку мы
используем  только  небольшое подмножество
языка  Си, мы можем реализовать компилятор
только  для  этого  подмножества, а разбор
текста  упростить  с помощью расстановки в
тексте подсказок компилятору.
  На  данный  момент  у нас есть прототип
компилятора  из  языка,  похожего на Си, в
ассемблерный текст.
  ...
  Также имеются зачатки самописного ассе─
мблера, пока  только  под  систему  команд
8-битного процессора Z80. Поддержка других
архитектур  затронет только специально вы─
деленную  часть  компилятора  и ассемблера
(менее 40% объёма исходного текста, причём
довольно  однообразная часть) и может быть
добавлена сравнительно легко.
  Проблема будет в реализации полноценной
системы  команд  (мы заранее не знаем, что
может  потребоваться,  но  можем  примерно
оценить  это  с помощью самокомпиляции, то
есть когда добьёмся, чтобы компилятор ком─
пилировал  собственный  исходный  текст) и
полной  отладке с документированием, кото─
рая может занять времени значительно боль─
ше, чем сама разработка."

   Что нужно сделать для самокомпиляции:

  # константные массивы для размеров типов
и названий  регистров (можно  заменить  на 
функции или на заполнение массивов) 
  #forwardопределения функций или объяв─
ление функции также при использовании 
  - если писать вызов
/*@*/(type).name(/*par1=*/n1,/*par2=*/n2)
    то Си увидит(type).name(n1,n2)
  - если писать вызов
/*@type.*/name(
       /*type par1=*/n1,/*type par2=*/n2)
    то Си увидитname(n1,n2)
  - вместо/*@*/можно писатьCALL, но не
в выражении (т.к. может быть идентификатор 
CALL )
  - при вызове из выражения ожидается иде─
нтификатор  или  дефайн, как  и  в  случае 
true/false
  #include
  #define(коды префиксов и регистров)
  # таблица  меток  должна быть определена
на массиве! или  вообще  её убрать (жёстко 
писать  типы  везде  и  чередовать csegи 
dseg )