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

в 19:43, , рубрики: C, diy или сделай сам, little man computer, LMC, ассемблер, Программирование, Си, эзотерические языки

CPU Design: Эзотерический язык LMCode - 1
Часть 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-машине память кодов и память данных разделены (гарвардская архитектура), создадим строку command_mem для загрузки LMCode-кода. Строка command_mem будет представлять память команд. Также создадим массив данных data_mem, который будет представлять память данных.

Загрузим в command_mem программу ,~+. 

#include <stdio.h>
int main(void) {
int i=0; // индекс текущей команды
int j=0; // индекс массива данных
int acc = 0; //аккумулятор
char command_mem[100] = ",~+."; //память команд
int data_mem[10]={0};           // память данных
     
while (command_mem[i] != '') {
if (command_mem[i]==',') // считываем число в аккумулятор 
    scanf("%d", &acc);   
if (command_mem[i]=='+') // прибавляем число из data_mem
    acc=acc+data_mem[j]; // к аккумулятору
if (command_mem[i]=='~') // загружаем число из аккумулятора
    data_mem[j]=acc;     // в память данных  
if (command_mem[i]=='.') // выводим число из аккумулятора на экран  
    printf("Output: %d",acc);
i++; //увеличиваем индекс текущей команды         
}
//переход на новую строку
printf("n"); 
// выводим массив данных
for (int k = 0; k<10; k++)
   printf("%d ", data_mem[k]);
return 0;
}

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

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

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

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

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

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

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

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

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

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

#include <stdio.h>
int main(void) {
int i=0; // индекс текущей команды
int j=0; // индекс массива данных
int acc = 0; //аккумулятор
char command_mem[100] = ",~>~>~>~>~"; //память команд
int data_mem[10]={0};                // память данных
     
while (command_mem[i] != '') {
if (command_mem[i]==',') // считываем число в аккумулятор 
    scanf("%d", &acc);   
if (command_mem[i]=='+') // прибавляем число из data_mem
    acc=acc+data_mem[j]; // к аккумулятору
if (command_mem[i]=='~') // загружаем число из аккумулятора
    data_mem[j]=acc;     // в память данных  
if (command_mem[i]=='.') // выводим число из аккумулятора на экран  
 printf("Output: %d",acc);
if(command_mem[i]=='>')      //переход на следующий элемент данных
    j++;
if(command_mem[i]=='<')      //переход на предыдущий элемент данных
    j--;	
if(command_mem[i]=='?') {   // прыжок на метку !
    while(command_mem[i] != '!') 
        i++; 
    } 	
i++; //увеличиваем индекс текущей команды         
}
//переход на новую строку
printf("n"); 
// выводим массив данных
for (int k = 0; k<10; k++)
   printf("%d ", data_mem[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

Добавим флаг pzflag

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

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

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

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

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

Чтобы пропустить шаги по загрузке чисел в память, инициализируем эти числа
data_mem[0]=3 и data_mem[1]=5

#include <stdio.h>
int main(void) {
int i=0;         // индекс текущей команды
int j=0;         // индекс массива данных
int acc = 0;
int pzflag = 1; // Флаг acc>=0
char command_mem[100] = "^>-{^?}<^!."; // максимум
int data_mem[10]={0}; 
data_mem[0]=3;   //инициализируем начальные значения
data_mem[1]=5;
 
while ( command_mem[i] != '') {
if(command_mem[i]==',')      // считываем число в аккумулятор
    scanf("%d", &acc);	
if(command_mem[i]=='+')      // прибавляем число из data_mem
    acc=acc+data_mem[j];     // к аккумулятору
if(command_mem[i]=='-')      // вычитаем число data_mem
    acc=acc-data_mem[j];     // из аккумулятора
if(command_mem[i]=='>')      // переход на следующий элемент данных
    j++;
if(command_mem[i]=='<')      //переход на предыдущий элемент данных
    j--;
if(command_mem[i]=='~')      // загружаем число из аккумулятора
    data_mem[j]=acc;         // в память данных
if(command_mem[i]=='^')      // загружаем число из data_mem
    acc=data_mem[j];         // в аккумулятор
if(command_mem[i]=='.') {    // выводим число из аккумулятора на экран
    printf("Output: %d",acc); 
    printf(" ");
	};
if(command_mem[i]=='?') {     // прыжок на метку !
    while(command_mem[i] != '!') 
        i++; 
    } 
if (command_mem[i]=='{' && pzflag==1) { // прыжок по условию acc>=0
    while(command_mem[i] != '}') 
        i++; 	 
    } 
if(acc>=0){    // Поднимаем флаг, если acc>=0
    pzflag=1; }
else {
    pzflag=0; }	
i++;   //увеличиваем индекс текущей команды         
}
//переход на новую строку
printf("n");
// выводим массив данных
for (int k = 0; k<10; k++)
printf("%d ", data_mem[k]);
return 0;
}

ideone.com

Для прыжка назад добавим переменную pz_prev.

Если текущим символом является {, то «поднимаем флаг» pz_prev

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

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

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

Напишем программу, которая выводит чётные числа с 10 до 0.

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

#include <stdio.h>
int main(void) {
int i=0;          // индекс текущей команды
int j=0;          // индекс массива данных
int acc = 0;    
int pzflag = 1;  // Флаг acc>=0
int pz_prev=0;   // прыжок назад по условию acc>=0
     
char command_mem[100] = "}^.>-<~{"; // вывод чётных чисел с 10 до 0
int data_mem[10]={0}; 
data_mem[0]=10;   //инициализируем начальные значения    
data_mem[1]=2;
     
while ( command_mem[i] != '') {
if(command_mem[i]==',')  // считываем число в аккумулятор
    scanf("%d", &acc);	
if(command_mem[i]=='+')  // прибавляем число из data_mem
    acc=acc+data_mem[j]; // к аккумулятору
if(command_mem[i]=='-')  // вычитаем число data_mem 
    acc=acc-data_mem[j]; // из аккумулятора
if(command_mem[i]=='>')  // переход на следующий элемент данных
    j++;
if(command_mem[i]=='<')  // переход на предыдущий элемент данных
    j--;
if(command_mem[i]=='~')  // загружаем число из аккумулятора 
    data_mem[j]=acc;     // в память данных
if(command_mem[i]=='^')  // загружаем число из data_mem
    acc=data_mem[j];     // в аккумулятор
if(command_mem[i]=='.') {  // выводим число из аккумулятора на экран 
    printf("Output: %d",acc); 
    printf(" ");
    };
if (command_mem[i]=='}')  // прыгаем назад?
    pz_prev=1; 
     
if(command_mem[i]=='?') {      // прыжок на метку !
    while(command_mem[i] != '!') 
        i++;  
    } 
if (command_mem[i]=='{' && pzflag==1 && pz_prev==0) { // прыжок вперёд
    while(command_mem[i] != '}')                      // по условию acc>=0
        i++;  
    } 
if (command_mem[i]=='{' && pzflag==1 && pz_prev==1) { // прыжок назад
    while(command_mem[i] != '}')                      // по условию acc>=0
        i--; 	 
    } 
if(acc>=0){      // Поднимаем флаг, если acc>=0
    pzflag=1;}
else {
    pzflag=0;}	
     
//printf("i=%d",i);printf(" ");
i++;   //увеличиваем индекс текущей команды
}
//переход на новую строку
printf("n");
// выводим массив данных
for (int k = 0; k<10; k++)
printf("%d ", data_mem[k]);
return 0;
}

ideone.com

Для того, чтобы перемножить два числа A и B, необходимо A раз к B прибавить B.

Будем в цикле на каждой итерации вычитать из A единицу, и, пока А не ноль, прибавлять В к В.

LMCode-программа }>>>^<+>~<<< ^>-<~{>>>^. перемножает числа А+1 и В, т.е. один множитель необходимо заведомо уменьшить на единицу.

Так происходит потому, что цикл завершится только тогда, когда в acc окажется -1.

Например, умножим 5 на 5.

Для этого предварительно поместим необходимые значения в data_mem 

      data_mem[0]=4; 
      data_mem[1]=1;
      data_mem[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 <stdio.h>
    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] != '') {
    	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 <stdio.h>
    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] != '') {
    	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

Автор: Дмитрий

Источник

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js