CPU Design. Эзотерический язык LMCode

ejgnu08xo_snpfvu1i1hsn3w3l4.gif
Часть I
Часть II
Часть III
Часть IV

Эта статья посвящена созданию интерпретатора некого эзотерического языка LMCode, в основе которого лежит архитектура Little Man Computer. О Little Man Computer можно прочитать в предыдущих статьях.

  • Пусть команде INP соответствует ,
  • команде OUT соответствует .
  • команде ADD соответствует +
  • команде SUB соответствует
  • команде STA соответствует ~
  • команде LDA соответствует ^

Напишем программу, которая загружает число из устройства ввода в аккумулятор, сохраняет число в памяти, прибавляет число из памяти к аккумулятору (удваивает число), и выводит удвоенное число в устройство вывода.
На ассемблере LMC эта программа будет выглядеть так (начальной ячейкой пусть будет 20)

 INP
 STA 20
 ADD 20 
 OUT


На языке LMCode эта программа будет выглядеть как ,~+.
В нашей LMCode-машине память кодов и память данных разделены (гарвардская архитектура), создадим строку str_arr для загрузки LMCode-кода. Строка str_arr будет представлять память команд. Также создадим массив массив data_arr, который будет представлять память данных.
Загрузим в str_arr программу ,~+.

       #include 
        int main(void) {
          int i=0; // индекс строки
          int j=0; // индекс массива данных
          int acc = 0;
        char str_arr[100] = ",~+.";
        int data_arr[10]={0}; 
     
        while ( str_arr[i] != '\0') {
            if (str_arr[i]==',') 
               scanf("%d", &acc);
            if (str_arr[i]=='+') 
               acc=acc+data_arr[j];
            if (str_arr[i]=='~') 
               data_arr[j]=acc;
            if (str_arr[i]=='.') 
               printf("Output: %d",acc);
          i++;          
          }
          printf("\n");
          for (int k = 0; k<10; k++)
          printf("%d ", data_arr[k]);
         return 0;
        } 


При загрузке в устройство ввода числа 123 получаем число 246.
Проверить можно в oline ide ideone.com

Добавим команды для

  • перехода к следующей ячейке >
  • перехода к следующей ячейке <


При обработке символа > будем увеличивать индекс j массива data_arr

if(str_arr[i]=='>') 
   j++;


При обработке символа < будем уменьшать индекс j массива data_arr

if(str_arr[i]=='<') 
   j--;

Для прыжка вперёд по команде ? будем осуществлять переход на метку !
Для этого будем пропускать все символы между ? и !

if(str_arr[i]=='?') {
   while(str_arr[i] != '!' ) {
    i++;
    } 
} 

Для сравнения напишем программу, в которой число 5 вносится в пять ячеек подряд

      #include 
    int main(void) {
      int i=0;
      int j=0;
     
      int acc = 0;
      char str_arr[100] = ",~>~>~>~>~";
     
      int data_arr[10]={0}; 
    while ( str_arr[i] != '\0') {
        if(str_arr[i]==',') 
           scanf("%d", &acc);        
        if(str_arr[i]=='+') 
           acc=acc+data_arr[j];
        if(str_arr[i]=='>') 
           j++;
        if(str_arr[i]=='<') 
           j--;
        if(str_arr[i]=='~') 
           data_arr[j]=acc;
        if(str_arr[i]=='.') 
           printf("%d",acc);
        if(str_arr[i]=='?') {
        while(str_arr[i] != '!') 
            i++; 
                } 
        i++;          
      }
      printf("\n");
      for (int k = 0; k<10; k++)
        printf("%d ", data_arr[k]);
     
       return 0;
    }  
    


В итоге получим массив 5 5 5 5 5 0 0 0 0 0
ideone.com

и ту же самую программу, в которой несколько шагов вперёд пропускаются командой безусловного перехода ,~>~?>~>~>~!
Получим массив 5 5 0 0 0 0 0 0 0 0
ideone.com

Добавим флаг pzf
Флаг будет поднят, только если число в аккумуляторе больше или равно нулю.

    if(acc>=0){
         pzf=1;}
    else {
         pzf=0;}        


Переход вперёд по условию pzf == 1 будем осуществлять командами { и }

if(str_arr[i]=='{') && (pzf==1){
        while(str_arr[i] != '}' ) 
       i++; 
       } 


Напишем программу, которая выводит максимальное число (из двух возможных).
Чтобы пропустить шаги по загрузке чисел в память, инициализируем эти числа
data_arr[0]=3 и data_arr[1]=5

#include 
int main(void) {
  int i=0;
  int j=0;
  int acc = 0;
  int pzf = 1;
  char str_arr[100] = "^>-{^?}<^!."; //maximum
 
  int data_arr[10]={0}; 
  data_arr[0]=3; 
  data_arr[1]=5;
 
while ( str_arr[i] != '\0') {
        if(str_arr[i]==',') 
           scanf("%d", &acc);       
    if(str_arr[i]=='+') 
       acc=acc+data_arr[j];
        if(str_arr[i]=='-') 
           acc=acc-data_arr[j];
    if(str_arr[i]=='>') 
       j++;
        if(str_arr[i]=='<') 
           j--;
        if(str_arr[i]=='~') 
           data_arr[j]=acc;
        if(str_arr[i]=='^') 
           acc=data_arr[j];
        if(str_arr[i]=='.') {
                printf("Output: %d",acc); 
                printf(" ");};
 
        if(str_arr[i]=='?') {
        while(str_arr[i] != '!') 
          i++; 
          } 
        if (str_arr[i]=='{' && pzf==1) {
        while(str_arr[i] != '}') 
          i++;   
          } 
 
    if(acc>=0){
        pzf=1;}
    else {
        pzf=0;} 
        i++;          
  }
  printf("\n");
  for (int k = 0; k<10; k++)
    printf("%d ", data_arr[k]);
  return 0;
}


ideone.com

Для прыжка назад добавим переменную pz_prev.
Если текущим символом является {, то «поднимаем флаг» pz_prev

if (str_arr[i]=='}') 
     pz_prev=1; 


Если метка } предшествует команде {, значит надо совершать прыжок назад

if (str_arr[i]=='{' && pzf==1 && pz_prev==1) {
        while(str_arr[i] != '}') 
         i--;    
         } 


Напишем программу, которая выводит чётные числа с 10 до 0.
Загрузим числа 10 и 2 в массив data_arr, далее, пока число в acc больше или равно нулю, будем от 10 отнимать 2 и выводить результат

     #include 
    int main(void) {
      int i=0;
      int j=0;
      int acc = 0;
      int pzf = 1;
      int pz_prev=0;
     
     char str_arr[100] = "}^.>-<~{";
     
      int data_arr[10]={0}; 
      data_arr[0]=10; 
      data_arr[1]=2;
     
    while ( str_arr[i] != '\0') {
        if(str_arr[i]==',') 
           scanf("%d", &acc);       
        if(str_arr[i]=='+') 
           acc=acc+data_arr[j];
        if(str_arr[i]=='-') 
           acc=acc-data_arr[j];
        if(str_arr[i]=='>') 
           j++;
        if(str_arr[i]=='<') 
           j--;
        if(str_arr[i]=='~') 
          data_arr[j]=acc;
        if(str_arr[i]=='^') 
          acc=data_arr[j];
        if(str_arr[i]=='.') {
                printf("Output: %d",acc); 
                printf(" ");
                };
        if (str_arr[i]=='}') 
          pz_prev=1; 
     
        if(str_arr[i]=='?') {
        while(str_arr[i] != '!') 
          i++;  
          } 
     
        if (str_arr[i]=='{' && pzf==1 && pz_prev==0) {
        while(str_arr[i] != '}') 
           i++;  
           } 
       if (str_arr[i]=='{' && pzf==1 && pz_prev==1) {
        while(str_arr[i] != '}') 
          i--;   
          } 
         if(acc>=0){
                 pzf=1;}
        else {
                  pzf=0;}       
     
        //printf("i=%d",i);printf(" ");
        i++;   
      }
      printf("\n");
      for (int k = 0; k<10; k++)
        printf("%d ", data_arr[k]);
      return 0;
    }   


ideone.com

Для того, чтобы перемножить два числа A и B, необходимо A раз к B прибавить B.
В цикле на каждой итерации вычитать из A единицу, и, пока А не ноль, прибавлять В к В.
LMCode-программа }>>>^<+>~<<< ^>-<~{>>>^. перемножает числа А+1 и В, т.е. один множитель необходимо заведомо уменьшить на единицу.
Так происходит потому, что цикл завершится только тогда, когда в acc окажется -1.
Например, умножим 5 на 5.
Для этого предварительно поместим необходимые значения в data_arr

      data_arr[0]=4; 
      data_arr[1]=1;
      data_arr[2]=5;


ideone.com

Добавим безусловные переходы назад.
Для этого добавим переменную prev.
Также добавим переходы вперёд/назад по условию acc=0. Для таких переходов создадим флаг zf и переменную z_prev.
Переходы по условию zf == 1 будем осуществлять командами ( и )
Перемножим 5 и 5 используя безусловный переход и переход по условию zf == 1.
Предварительно поместим необходимые значения в data_arr

      data_arr[0]=5; 
      data_arr[1]=1;
      data_arr[2]=5;


LMCode-прогамме !>>>^<+>~<<<^>-<~(?)>>>^. соответствует ассемблерная прогамма

 INP
 STA 20
 INP 
 STA 21
 INP 
 STA 22
 LDA 23
 ADD 22
 STA 23
 LDA 20
 SUB 21
 STA 20
 BRZ 14
 BRA 06
 LDA 23
 OUT
 HLT


Код на Си

#include 
    int main(void) {
      int i=0;
      int j=0;
      int acc = 0;
      int pzf = 1;
          int zf =1;
      int pz_prev=0;
      int z_prev=0;
          int prev=0;
     char str_arr[100] ="!>>>^<+>~<<<^>-<~(?)>>>^.";
                 
      int data_arr[10]={0}; 
      data_arr[0]=5; 
      data_arr[1]=1;
          data_arr[2]=5;
     
    while ( str_arr[i] != '\0') {
        if(str_arr[i]==',') 
           scanf("%d", &acc);       
        if(str_arr[i]=='+') 
           acc=acc+data_arr[j];
        if(str_arr[i]=='-') 
           acc=acc-data_arr[j];
        if(str_arr[i]=='>') 
           j++;
        if(str_arr[i]=='<') 
           j--;
        if(str_arr[i]=='~') 
          data_arr[j]=acc;
        if(str_arr[i]=='^') 
          acc=data_arr[j];
        if(str_arr[i]=='.') {
                printf("Output: %d",acc); 
                printf(" ");
                };
        if (str_arr[i]=='}') 
          pz_prev=1;
            if (str_arr[i]==')') 
          z_prev=1;   
            if (str_arr[i]=='!') 
          prev=1;   
        // безусловный переход
                if (str_arr[i]=='?' && prev==0) {
        while(str_arr[i] != '!') 
           i++;  
           } 
       if (str_arr[i]=='?' && prev==1) {
        while(str_arr[i] != '!') 
          i--;   
          } 
                // переход по условию acc=0 
                if (str_arr[i]=='(' && zf==1 && z_prev==0) {
        while(str_arr[i] != ')') 
           i++;  
           } 
       if (str_arr[i]=='(' && zf==1 && z_prev==1) {
        while(str_arr[i] != ')') 
          i--;   
          } 
        // переход по условию acc>=0 
        if (str_arr[i]=='{' && pzf==1 && pz_prev==0) {
        while(str_arr[i] != '}') 
           i++;  
           } 
       if (str_arr[i]=='{' && pzf==1 && pz_prev==1) {
        while(str_arr[i] != '}') 
          i--;   
          }
        // флаги                  
         if(acc>=0){
                 pzf=1;}
        else {
                  pzf=0;}       
                if(acc==0){
                 zf=1;}
        else {
                  zf=0;}                  
     
        //printf("i=%d",i);printf(" ");
        i++;   
      }
      printf("\n");
      for (int k = 0; k<10; k++)
        printf("%d ", data_arr[k]);
      return 0;
    }


ideone.com

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

Проверим, как вычисляются числа Фибоначчи.

#include 
    int main(void) {
      int i=0;
      int j=0;
      int acc = 0;
      int pzf = 1;
      int zf =1;
      int pz_prev=0;
      int z_prev=0;
      int prev=0;
      
     char str_arr[100] ="}>>^>+.~<+.~<<^>-<~{";
                         
      int data_arr[10]={0}; 
      data_arr[0]=5; 
      data_arr[1]=1;
          data_arr[2]=1;
     
    while ( str_arr[i] != '\0') {
        if(str_arr[i]==',') 
           scanf("%d", &acc);       
        if(str_arr[i]=='+') 
           acc=acc+data_arr[j];
        if(str_arr[i]=='-') 
           acc=acc-data_arr[j];
        if(str_arr[i]=='>') 
           j++;
        if(str_arr[i]=='<') 
           j--;
        if(str_arr[i]=='~') 
          data_arr[j]=acc;
        if(str_arr[i]=='^') 
          acc=data_arr[j];
        if(str_arr[i]=='.') {
                printf("Output: %d",acc); 
                printf(" ");
                };
        if (str_arr[i]=='}') 
          pz_prev=1;
            if (str_arr[i]==')') 
          z_prev=1;   
            if (str_arr[i]=='!') 
          prev=1;   
        // безусловный переход
                if (str_arr[i]=='?' && prev==0) {
        while(str_arr[i] != '!') 
           i++;  
           } 
       if (str_arr[i]=='?' && prev==1) {
        while(str_arr[i] != '!') 
          i--;   
          } 
                // переход по условию acc=0 
                if (str_arr[i]=='(' && zf==1 && z_prev==0) {
        while(str_arr[i] != ')') 
           i++;  
           } 
       if (str_arr[i]=='(' && zf==1 && z_prev==1) {
        while(str_arr[i] != ')') 
          i--;   
          } 
        // переход по условию acc>=0 
        if (str_arr[i]=='{' && pzf==1 && pz_prev==0) {
        while(str_arr[i] != '}') 
           i++;  
           } 
       if (str_arr[i]=='{' && pzf==1 && pz_prev==1) {
        while(str_arr[i] != '}') 
          i--;   
          }
        // флаги                  
         if(acc>=0){
                 pzf=1;}
        else {
                  pzf=0;}       
                if(acc==0){
                 zf=1;}
        else {
                  zf=0;}                  
     
        //printf("i=%d",i);printf(" ");
        i++;   
      }
      printf("\n");
      for (int k = 0; k<10; k++)
        printf("%d ", data_arr[k]);
      return 0;
    }


ideone.com

© Habrahabr.ru