Часть 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;
}
Для прыжка назад добавим переменную 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;
}
Для того, чтобы перемножить два числа 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;
Добавим безусловные переходы назад.
Для этого добавим переменную 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;
}
Вообще, флаги можно было не создавать, а вместо них сразу проверять, чему равно число в аккумуляторе.
Проверим, как вычисляются числа Фибоначчи.
#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;
}
Автор: Дмитрий