Недавно решил я попробовать написать какой-нибудь интерпретатор и сделать это на языке C, остановился на языке brainfuck, потому, что его интерпретатор довольно прост в написании.
Что такое brainfuck?
Brainfuck это язык программирования известный своим минимализмом
И правда, в нем всего 8 комманд это "+", "-", ">", "<", "[", "]", ".", ",".
Инструкция |
Действие |
"+" |
Увеличивает значение в текущей ячейке на 1 |
"-" |
Уменьшает значение текущей ячейки на 1 |
">" |
Переход к следующей ячейке |
"<" |
Переход к предыдущей ячейке |
"." |
Вывод на экран содержания текущей ячейки |
"," |
Ввод символа с клавиатуры в текущюю ячейку |
"[" и "]" |
Операторы goto |
Написание самого интерпретатора
Чтобы интерпретатор работал надо подключить определённые библиотеки
stdio для printf, fopen
stdlib для exit
string для memset
#include <stdio.h>
#include <stdlib.h>
#include <string.h>Дальше надо инициализировать массив памяти и определить инструкции:
char stack[30000]; //массив памяти
int indexx = 0; // индекс текущей ячейки
char * plus = "+";
char * minus = "-";
char * next = ">";
char * back = "<";
char * prt = ".";
char * inp = ",";
char * lp = "[";
char * llp = "]";
int rc = 0;
char * endl = "\n";
char * ex = "@";Значек "@" будет использоваться как выход из программы
Следующий шаг это создать метод main и в его теле инициализировать массив
memset(stack, 0, 30000);Далее проверку на кол-во аргументов командной строки
if (argc < 2) {
bf_shell();
exit(0);
} Выходит если аргумент 1, то запускается brainfuck shell - ещё одна фича моего интерпретатора
Код brainfuck shell:
int bf_shell()
{
printf("Startimg BrainFuck Shell...\n");
char command[4096];
int i = 1;
do {
printf("BF> ");
gets(command);
for (int x = 0; x < sizeof(command); x++) {
if (command[x] == *plus) {
stack[indexx]++;
} else if (command[x] == *minus) {
stack[indexx]--;
} else if (command[x] == *next) {
indexx++;
} else if (command[x] == *back) {
indexx--;
} else if (command[x] == *prt) {
putchar(stack[indexx]);
} else if (command[x] == *inp) {
char t[2];
gets(t);
stack[indexx] = (int)t[0];
}else if (command[x] == *endl) {
i = 1;
} else if (command[x] == *ex) {
i = 0;
} else if (command[x] == *lp) {
if (!stack[indexx]) {
rc++;
while (rc) {
i++;
if (command[x] == *lp) {
rc++;
}
if (command[x] == *llp) {
rc--;
}
}
} else continue;
} else if (command[x] == *llp) {
if (!stack[indexx]) {
continue;
} else {
if (command[x] == *llp) {
rc++;
while (rc) {
x--;
if (command[x] == *lp) {
rc--;
}
if(command[x] == *llp) {
rc++;
}
}
x--;
}
}
} else {
continue;
}
}
} while (i);
return 0;
} Дальше идёт тело метода main где интерпретатор интерпретирует символы из файла
FILE * file = fopen(argv[1], "r");
if (file == NULL) {
printf("Cann't open file %s!\n", argv[1]);
exit(1);
}
fseek(file, 0L, SEEK_END);
long size = ftell(file);
fseek(file, 0L, SEEK_SET);
char buf[size];
fread(buf, sizeof(buf), 1, file);И сам цикл интерпретации
for (int i = 0; i < sizeof(buf); i++) {
if (buf[i] == *plus){
stack[indexx]++;
} else if (buf[i] == *minus) {
stack[indexx]--;
} else if (buf[i] == *next) {
indexx++;
} else if (buf[i] == *back) {
indexx--;
} else if (buf[i] == *prt) {
putchar(stack[indexx]);
} else if (buf[i] == *inp) {
char c;
scanf("%c", &c);
stack[indexx] = (int)c;
} else if (buf[i] == *lp) {
if (!stack[indexx]) {
rc++;
while (rc) {
i++;
if (buf[i] == *lp) {
rc++;
}
if (buf[i] == *llp) {
rc--;
}
}
} else continue;
} else if (buf[i] == *llp) {
if(!stack[indexx]) {
continue;
} else {
if (buf[i] == *llp) {
rc++;
while (rc) {
i--;
if (buf[i] == *lp) {
rc--;
}
if (buf[i] == *llp) {
rc++;
}
}
i--;
}
}
} else if (buf[i] == *ex) {
return 0;
}
}Исходник доступен на моем гитхабе
Учтите, что в исходниках все написано в теле метода main.
Комментарии (23)
xi-tauw
19.07.2022 12:52+7char command[4096]; int i = 1; do { printf("BF> "); gets(command);Ух. Писали интерпретатор bf, а написали учебную программу на переполнение стэка.
includedlibrary
19.07.2022 12:56Верно подметили. Лучше использовать
char* fgets(char * restrict str, int size, FILE * restrict stream);
Cywka_70 Автор
21.07.2022 09:12Здесь полностью согласен, но данный пример интерпретатор не предназначен для ввода слишком длинной строки, и писался за 5 минут, поэтому этот недочёт не был замечен.
Apoheliy
19.07.2022 13:03+3Почему бы Вам не сделать интерпретатор чуть более корректным?
30000 - откуда число? Больше быть не может? И если его всё же используете, то лучше бы контролировать границы;
char * plus = "+"; . Э-э-э может лучше так?: char plus = '+'; ... if (buf[i] == plus) ...
Загонять весь файл в стэк? Это очень сурово. Попробуйте открыть файл размером ну хотя бы 1 гигабайт. Подозреваю, у вас всё рухнет;
команду интерпретатора не ввести более 4096 байт? А если ввод перенаправить из файла? (1 гигабайт)
-
Отрицательный индекс в ячейки быть не может?
Cywka_70 Автор
21.07.2022 09:23Число 30000 взято из всех стандартных интерпретаторов bf.
char plus = "+" ; работать не будет, потому что тип данных "" это указатель.
Для примера попробуйте скомпилировать и запустить такой код
#include <studio.h> int main() { char test = "i"; printf("%c\n", test); return 0; }Он выведет только перевод строки, т.к в переменную test записан указатель на символ "i".
Apoheliy
21.07.2022 09:43Ваш напор похвален.
"Число 30000" Вы можете взять любое. Только желательно контролировать, что в результате скачки по ячейкам вы за него не выйдите. Здесь это никто, кроме вас, контролировать не будет.
Про char plus ... - там ставятся одинарные кавычки. И тип данных сразу станет char.
А в целом: Удачи, язык чистый-C - это хорошо.
ironlion
19.07.2022 13:11+2Хранить заведомо односимвольные команды в char * — тоже так себе идея. Если объявить команды, как const char и сравнивать в конструкции switch — будет намного симпатичнее (и эффективнее тоже):
switch (buf[i]) { case cmd_plus: stack[indexx]++; break; case cmd_minus: stack[indexx]--; break; ... }
Или вообще олдскульно:#define CMD_PLUS '+' #define CMD_MINUS '-'Cywka_70 Автор
21.07.2022 11:25Это все хорошо, но почему именно switch case?
if/else тоже хорошо, чем if/else не устроило?
nUser123
19.07.2022 15:34+1По-моему char buf[size] в "методе" main не скомпилируется, так как size не известно на момент компиляции
nickolaym
20.07.2022 01:00Брейнфак - это язык для очень упрощённой машины Тьюринга. А МТ, как известно, работает на ленте, бесконечной в обе стороны.
Поэтому следующая итерация (после исправления всех ошибок и недочётов, которые вам тут сказали) - это поддержка этой самой бесконечной ленты.Самый тупой способ на голом Си, - это, конечно, просто реаллокация. Выделили новый, бОльший блок памяти, скопировали в него старый (со смещением вправо, если двигались влево и выбежали в отрицательные индексы) и вуаля.
Более затейливо - сделать страничную организацию... Ну, в общем, простор для творчества, особенно, на Си.
---
Следующий пункт для улучшения - это интерпретатор.
Каждой скобке соответствует своя парная скобка. Как минимум, логично вместо тупого поиска вперёд-назад по исходнику завести табличку быстрого перехода к паре.
Серии однотипных действий (+/-, </>) также можно хранить в виде групповой операции +n, >n, где n - целое число (положительное или отрицательное по итогу серии).
Итого, у нас получается следующий промежуточный код:
'+' n -- инкремент ячейки
'>' n -- инкремент адреса
'[' n -- условный переход на n команд (промежуточных!) - если текущая ячейка нулевая и вперёд, или если ненулевая и назад
'.' n -- вывод текущей ячейки n раз
',' n -- ввод в текущую ячейку n раз (что означает проглатывание n-1 символов)
То есть, пишем транслятор исходника в промежуточный код. Назвать это компиляцией как-то ещё слишком гордо.
---
Следующая задача - существенно более творческая. Это распознавание и обработка идиом языка.
Например, обнуление ячейки: "[-]"
Или вывод нуль-терминированной строки "[.>]"
Или даже просто вывод n символов подряд ".>.>.>"
Можно расширить промежуточный код специальными командами для этих идиом.
---
Ну и дальше, насколько фантазии хватит.
Cywka_70 Автор
21.07.2022 10:04Этот интерпретатор - очень упрощённый пример, поэтому я не стал заморачиваться, хотя можно было транслировать код bf в код C или ассемблера, а потом компилировать, но зто уже был бы компилятор а не интерпретатор.
PlatinumThinker
21.07.2022 10:13перевод с одного языка на другой это транспилятор
Cywka_70 Автор
21.07.2022 10:30Почему тогда gcc - компилятор? Если фактически он транспилятор из C в ассемблер?
nickolaym
22.07.2022 01:50А никто и не говорит делать трансляцию во что-то сохраняемое - си, ассемблер или объектный код для прямого запуска.
Интерпретатор вполне может транслировать во внутреннее представление, а не заниматься синтаксическим разбором каждой команды каждый раз!
Хорошо у брейнфака каждая элементарная команда - это один символ, и поэтому разбор может быть вырожденным. Но вот уже структурная команда цикла требует чуть более сложного действия. Формально, грамматика-то контекстно-свободная, а не регулярная.
Так почему бы не отделить фазу разбора от фазы исполнения?
nickolaym
20.07.2022 01:05В общем, что хочу сказать. Плюсик за смелость, минусик за незрелость :) Стремительно исправляйте и улучшайте, пока народ не заклевал.
TheCalligrapher
20.07.2022 05:06Чтобы интерпретатор работал надо подключить определённые библиотеки
С каких это пор стандартные заголовки стали назваться "библиотеками"?
char * plus = "+";Язык С конечно же не требует
constздесь, но это не причина не придерживаться элементарных правил константной корректности.memset(stack, 0, 30000);Обнуление агрегата при помощи
memsetв 2022 году? Да еще и с явным указанием размера через магическую константу??? И это при том, что верный термин "инициализация" вам таки знаком. Может быть стоило действительно воспользоваться инициализациейchar stack[30000] = { 0 };gets(command);O_o. Лолшто???
for (int x = 0; x < sizeof(command); x++) {Интересно заметить, что в этом месте автор догадался использовать
sizeof, пусть даже и с лишними скобками. Почему же тогда вmemsetвыше была использована магическая константа?int bf_shell()Зачем эта функция возвращает
int? И, пока не наступила эра C23, все таки пожалуйстаint bf_shell(void)long size = ftell(file); fseek(file, 0L, SEEK_SET);char buf[size];Чтение целого файла в локальный VLA - весьма рискованная идея.
Cywka_70 Автор
21.07.2022 10:58Чем плох memset?
В исходнике нет функции bf_shell вообще, там все действия происходят в main.
И почему возврат int чем-то может не устраивать?
Перед чтением файла программа узнает размер файла и создаёт массив который соответствует размеру файла и только потом файл считается в массив.
TheCalligrapher
21.07.2022 19:26Чем плох memset?
Только тем, что незачем преумножать сущности без необходимости. Зачем притягивать сюда за уши библиотечную функцию
memset, когда ядро языка уже предоставляет вам встроенные возможности для выполнения инициализации?Точно так же можно вызывать какую-нибудь библиотечную функцию для того, чтобы увеличить переменную на 1, вместо классического
++i. Чем это плохо? Да, вроде, ничем... Но зачем?!И, еще раз, в глаза бросается именно то, что вы сами использовали термин "инициализация", но при этом почему-то не воспользовались предоставляемыми вам языком С возможностями инициализации.
И почему возврат int чем-то может не устраивать?
"Не устраивает" не сам возврат
int, а тот факт, что функция очевидно ничего осмысленного не возвращает в этомint. Зачем тогда было делать ееint, если можно было сделать ееvoid? Зачем взваливать на плечи читателя кода вопрос о том, что же это за возвращаемое значение, только для того, чтобы он в результате выяснил, что это возвращаемое значение никакого смысла не несет?Перед чтением файла программа узнает размер файла и создаёт массив который соответствует размеру файла и только потом файл считается в массив.
Так о том и речь. Вы создаете автоматический VLA, размер которого равен размеру файла. Размер файла запросто может оказаться слишком большим для автоматического объекта. Не создавайте потенциально большие объекты "на стеке". Это добром не кончится.
Sadler
21.07.2022 01:41Я в студенческие годы написал транслятор BF в C, это несложно, плюс, после оптимизации gcc даже терпимо работало. Потом поверх этого писал C-подобный язык, транслируемый в BF (да-да, транслируемый затем в С и компилируемый с помощью gcc). В общем, развлекался как умел.
includedlibrary
А в чём смысл статьи? В качестве обучающего материала для написания интерпретаторов статья не годится, потому что в основном языки программирования имеют более сложную структуру, и для интерпретации придётся писать лексический анализатор и синтаксический анализатор, что в статье не рассматривается. В качестве хорошего обучающего материала могу предложить книгу "Build your own lisp". Есть так же её вариации на отличных от си языках
Cywka_70 Автор
ПОЕСНИТЕЛЬНАЯ БРИГАДА:
Смысл статьи - максимально быстро и незапарно получить полные права.