Пишемо віртуальну машину, компілятор, декомпілятор Brainfuck на Ruby
Напишемо компілятор Brainfuck, щоб було зовсім весело і був справжнісінький «Brainfuck», напишемо його на Ruby.
Діятимемо за такою схемою: 1. Brainfuck компілюватиметься в байткод. 2. Виконаються у віртуальній машині.
Почнемо з віртуальної машини, ми не обмежуватимемо пам'ять у 30 000 осередків з кількох причин: 1. Мова буде повною за Тьюрингом. 2. Накладно створити масив розміром 30000 елементів, тим більше заповнити його нулями, візуально це робить затримку перед запуском в 1-2 секунди. Ми будемо створювати осередки в міру їхнього використання. Як відомо, Brainfuck містить 8 операторів:
- >— Переходить до наступного осередку.
- 0x1 0x1 0x1 0x2 0x2 0x2
Буде скомпільованою версією: +++---
Відразу кажу, нам знадобиться RubyGem — bindata. Встановлює гем: gem install bindata
#!/usr/bin/ruby -Ku require 'bindata'
def self.read_file file if not File.exist? file puts "File " + file + " doesn't exist!" exit 1 end @new_name = file.gsub(/.bf/,'') @@code = File.open(file).readlines.map < line line.chomp >.join.split('') end
def self.validate @a = 0 @@code.each do item if item == '[' @a += 1 end if item == ']' @a -= 1 end end if @a > 0 puts "Unexpected [ or ]" exit 1 end end
def self.compile $cells = Array.new $cell = 0 @fun = Proc.new для command,file if $cells[$cell].nil? $cells[$cell] = 0 end
case command when '+' BinData::Int8be.new(0x1).write(file) $cells[$cell] += 1 when '-' BinData: :Int8be.new(0x2).write(file) $cells[$cell] -= 1 when '>' BinData::Int8be.new(0x3).write(file) $cell += 1 when' 0 and item != ']' loop_code
Пробуємо зібрати код на Brainfuck:
Начебто у нас все вийшло, у нас створився бінарний файл, тепер потрібна віртуальна машина, яка його виконуватиме:
require 'bindata' require 'readline'
def self.run bytecode cells = Array.new @plus = 0x1 @minus = 0x2 @next = 0x3 @previous = 0x4 @read = 0x5 @print = 0x6 cell = 0 ip = 0 while not bytecode.size == ip if cells[cell].nil? cells[cell] = 0 end
case bytecode[ip] when @plus cells[cell] += 1 when @minus cells[cell] -= 1 when @next cell += 1 when @previous cell -= 1 when @read cells[cell] = Readline.readline('',true).chomp.to_i when @print print cells[cell].chr end ip += 1 end end end
ARGV.each do file_name якщо не File.exist? file_name puts "File # doesn't exist!" exit 1 end bytecode = Array.new File.open(file_name) для файлу file.each_byte для ch bytecode[bytecode.size] = ch end end VirtualMachine.run bytecode end
Як ви помітили, у віртуальній машині немає команд циклів, ми всю відповідальність за цикли поклали на компілятор, отже, віртуальній машині не доводиться піклуватися тілі циклу, перевіряти значення комірки і т. д. Віртуальна машина всього лише виконує 6 команд послідовно, думаю таким Таким чином, ми добре збільшили продуктивність, краще один раз довго компілювати, ніж спостерігати, як гальмує Hello World!.
Ну що ж, ми написали компілятор і віртуальну машину, отже тепер реалізуємо декомпілятор. На жаль, ми зробили виконуваний файл таким способом, що зберегти цикли нам не вдалося, але напевно це і на краще, тому що можна декомпілювати і дивитися напомилки.
Ось код декомпілятора:
ARGV.each для file_name @file_name = "decompilled_"+file_name+".bf" @count = 0 File.open(@file_name,'w') do line File.open( file_name) do file file.each_byte do b case b when 0x1 line.write '+' when 0x2 line.write '-' when 0x3 line.write '>' when 0x4 line.write '
Все насправді дуже просто. Єдине чого нам не вистачає, це відладчика, це якраз те, чим я, мабуть, займуся завтра.
Все це робилося «Just for fun», на практиці, а, писати віртуальні машини та компілятори високорівневими мовами не варто.