Интепретатор Brainfuck
Всем привет!
Я планировал написать одну большую статью про изотерический язык программирования Brainfuck, но как всегда что-то пошло не так и я не успел дописать код. Так что я решил разбить статью на две и первую выпустить под конец 2021.
Давайте же начнём!
Введение
Прежде чем начать нам нужно немного узнать о языке Brainfuck. Информации из вики достаточно для понимания:
Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — иметь половое сношение (оск.)), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
У нас в распоряжении есть 8 команд (brainfuck с функциями не будем рассматривать), а именно:
>— перейти к следующей ячейке памяти<— перейти к предыдущей ячейке памяти+— увеличить значение текущей ячейки на единицу-— уменьшить значение текущей ячейки на единицу.— напечатать значение из текущей ячейки,— ввести значение (stdin) и положить в текущую ячейку[— перейти к коду после], если в текущей ячейке ноль]— вернуться к коду после], если в текущей ячейке не ноль
Этих 8-ми команд хватит чтобы реализовать любую программу, т.к. язык полный по Тьюрингу, но наша задача заключается не в написании, а в интерпретации кода на brainfuck.
Давайте же перейдём к планированию нашего интерпретатора.
Структура интерпретатора
Не будем усложнять себе работу и реализуем самый простой интерпретатор.
Работа выполним в два этапа:
- парсинг (или разбор токенов) программы в удобный для нас вид
- выполнение программы
Этап разбора токенов
На данном этапе мы должны входной поток токенов преобразовать в некий набор идентификаторов для нашей программы. По сути это отображение одного множества на другое, но не будем усложнять статью :)
Считайте просто что мы символ заменяем на некоторую константу (хотя мы будем использовать перечисление).
Вроде всё просто, но тут есть две интересные команды, которые немного усложняют наш процесс разбора — [ и ].
Из-за них этап разбора немного усложняется, так как нам нужно запомнить позиции этих токенов, чтобы на этапе интерпретации можно было легко реализовать переход. Чуть дальше вы поймете о чём я говорю.
Всё конечно не очень так сложно. Просто нам нужно сохранить индекс токена в некий буфер, когда мы достигаем команды [, а на команде ] должны проставить индексы для [ и ] в подготовленной нами программе для интерпретатора.
Этап выполнения кода
После того как этап разбора токенов закончен, то можно перейти к выполнению программы.
Данный этап можно разбить на три шага:
- берём токен по текущему индексу (ip — instruction pointer)
- выполняем его
- увеличиваем ip
Только нужно сделать небольшое уточнение — команды [ и ] могут менять ip.
Вроде это всё что нужно знать для того чтобы сделать свой интерпретатор brainfuck.
Реализация
Писать рабочий интерпретатор я буду на Rust, но так же приложу код на C++ в конце статьи.
Базовый код
// набор команд
#[derive(Debug, Clone, Copy)]
pub enum Command {
// >
Next,
// <
Previous,
// +
Increment,
// -
Decrement,
// .
Put,
// ,
Read,
// [
LoopBegin(usize),
// ]
LoopEnd(usize),
}
// наш интерпретатор
pub struct Emulator {
// вспомогательный буфер для `[` и `]`
stack: Vec<usize>,
// спарсенная программа
app: Vec<Command>,
// ячейки с памятью программы
mem: Vec<u8>,
// указатель на инструкцию
ip: usize,
// указатель на ячейку памяти
mp: usize,
}
impl Emulator {
// инициализация переменных
pub fn new(mem_size: usize) -> Emulator {
Emulator { stack: Vec::new(), mem: vec![0; mem_size], app: Vec::new(), ip: 0, mp: 0 }
}
}
// токен валидный для brainfuck?
pub fn is_valid_token(t: char) -> bool {
t == '>' || t == '<' || t == '+' || t == '-' || t == '.' || t == ',' || t == '[' || t == ']'
}
fn main() {
// создаём объект интерпретатора
let mut emulator = Emulator::new(30_000);
// читаем программу из stdin и выполняем её
match emulator.from_stdin().and_then(|_| emulator.execute()) {
Err(err) => println!("error: {}", err),
_ => (),
}
}
Парсинг
Начнём с преобразования токена в наш enum через реализацию трейта From:
impl From<char> for Command {
fn from(token: char) -> Self {
match token {
'>' => Command::Next,
'<' => Command::Previous,
'+' => Command::Increment,
'-' => Command::Decrement,
'.' => Command::Put,
',' => Command::Read,
'[' => Command::LoopBegin(0),
']' => Command::LoopEnd(0),
// если дошло до этого кода, то где-то в коде проблема!
token => panic!("unknown token `{}`", token),
}
}
}
Дальше реализуем парсинг токенов:
// --- все эти функции написаны в блоке impl Emulator ---
// чтение программы с stdin
pub fn from_stdin(&mut self) -> Result<(), String> {
// вывод > без перевода строки
print!("> ");
io::stdout().flush().map_err(|e| e.to_string())?;
// читаем в буфер весь stdin
let mut buffer = String::new();
io::stdin().read_line(&mut buffer).map_err(|e| e.to_string())?;
// и отдаём буфер в парсящую функцию
self.from_buffer(&buffer)
}
pub fn from_buffer(&mut self, buffer: &str) -> Result<(), String> {
// цикл по токенам
for token in buffer.chars() {
// успешно спарсено?
self.parse_token(token)?;
}
// валидируем количество скобок []
match self.stack.len() > 0 {
true => Err("number of brackets does not match".to_string()),
false => Ok(()),
}
}
// парсинг отдельного токена
fn parse_token(&mut self, token: char) -> Result<(), String> {
// нам нужны только токены brainfuck
if is_valid_token(token) {
// получаем номер текущей ячейки (длина программы)
let index = self.app.len();
// преобразуем char в Command через трейт From
let cmd = match token.into() {
// если это `[`
command @ Command::LoopBegin(_) => {
// то запоминаем индекс команды
self.stack.push(index);
// и возвращаем её
command
}
// если `[`
Command::LoopEnd(_) => {
// вытаскиваем последний индекс
let start = match self.stack.pop() {
Some(value) => value,
None => return Err("loop start not found".to_string()),
};
// правим начало цикла устанавливая V вот этот индекс (он указывает на конец)
self.app[start] = Command::LoopBegin(index);
// и добавляем команду с концом цикла, который смотрит на начало
Command::LoopEnd(start)
}
// любые другие команды просто отдаём дальше
cmd => cmd,
};
// добавляем команду в массив программы
self.app.push(cmd);
}
// всё ок
Ok(())
}
Интерпретация
Теперь же перейдём к коду интерпретации:
// --- все эти функции написаны в блоке impl Emulator ---
// один шаг выполнения
pub fn step(&mut self) -> Result<(), String> {
// матчим текущую команду
match self.app[self.ip] {
Command::Next => {
// проверка на выход за границы (верхняя граница)
if self.mp + 1 == self.mem.len() {
return Err("out of memory".to_string());
}
// увеличиваем индекс на ячейку памяти
self.mp += 1;
}
Command::Previous => {
// проверка нижней границы памяти
if self.mp == 0 {
return Err("cannot access negative memory index".to_string());
}
// уменьшаем индекс на ячейку памяти
self.mp -= 1;
}
Command::Increment => {
// добавим к текущей ячейке единицу с учётом возможного переполнения, т.к. у нас ячейки имеют тип u8
self.mem[self.mp] = self.mem[self.mp].overflowing_add(1).0;
}
Command::Decrement => {
// уменьшаем значение ячейки на единицу (не забываем про переполнение)
self.mem[self.mp] = self.mem[self.mp].overflowing_sub(1).0;
}
Command::Put => {
// выводит текущее значение в stdout
print!("{}", self.mem[self.mp] as char);
io::stdout().flush().map_err(|e| e.to_string())?;
}
Command::Read => {
// берём из потока stdin один байт и записываем в память
self.mem[self.mp] = match io::stdin().bytes().next() {
Some(Ok(value)) => value,
Some(Err(err)) => return Err(err.to_string()),
None => return Err("cannot read byte from stdin".to_string()),
}
}
Command::LoopBegin(index) => {
// если в текущей ячейки ноль, то
if self.mem[self.mp] == 0 {
// выходим из текущего цикла установкой нового ip
self.ip = index;
}
}
Command::LoopEnd(index) => {
// если не ноль, то
if self.mem[self.mp] != 0 {
// возвращаемся в начало цикла
self.ip = index;
}
}
}
// увеличиваем указатель на текущую инструкцию
self.ip += 1;
Ok(())
}
// выполнить всю программу
pub fn execute(&mut self) -> Result<(), String> {
// выполняем программу, пока ip не выйдет за границы программы
while self.ip < self.app.len() {
self.step()?;
}
Ok(())
}
Тест
Теперь можно собрать приложение и проверить работу "Hello World!":
$ echo "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>." | ./app
> Hello World!
Больше примеров для проверки можете найти в интернете или написать самим!
Я оставил пару примеров в репозитории, но для более удобной работы вам предстоит реализовать загрузку кода из файла.
Заключение
В следующей статье рассмотрим компиляцию brainfuck в исполняемое приложение!
Весь написанный код можно взять в репозитории и там же можно найти C, C++, Go версии.
Всем пока!