CPU Design. Эзотерический язык LMCode
Часть 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