Edited at
移行Day 16

AdventCalendar Day16 [超Ruby入門]


はじめに

本記事は、超Ruby入門16日目の記事です。

コメント頂ける方は、ガイドラインを読んで頂けると幸いです。


目的

Brainf_ckを実装し、言語自体に興味も持たせる。


目標

Rubyを楽しむ

サンプルを発展させ、友人に自慢する。


事前準備

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.

------------.<++++++++.--------.+++.------.--------.>+.

この入力の出力がわかりますか?そう、お馴染みHello,World!です

世にも奇妙な言語を、Brainfuckと言います。

Brainfuckとは、8つの命令で完結するチューニング完全なプログラミング言語です。

命令
意味

>
ポインタを右に1つ動かす

<
ポインタを左に1つ動かす

+
ポインタの指す値を1増やす

-
ポインタの指す値を1減らす

.
ポインタが指す値をASCIIコードに従い出力する。

,
入力から1バイト読み込んで、ポインタが指す先に代入する。

[
ポインターの指す値が0なら、対応する]まで進み、次の命令を実行。

]
ポインターの指す値が0以外なら、対応する[まで戻り、次の命令を実行。

命令は上記表の8つ。

より詳しい説明は、実用Brainf*ckプログラミングを見て下さい。


本題

それでは、brainfuckの処理系を実装してみましょう。

まずは、+.を実装してHという文字を出力するプログラムを作ります。

class BrainF_ck

def initialize
@tape = []
@pc = 0
@c_position = 0
end

def exec(code)
chars_code = code.chars ## 入力を一文字ずつに区切る
while @pc < chars_code.length
case chars_code[@pc]
when "+"
inc
when "."
show
end
@pc += 1
end
end

private
# inc means (+)
def inc
@tape[@c_position] ||= 0
@tape[@c_position] += 1
end

# show means (.)
def show
puts @tape[@c_position].chr
end
end

brainf_ck = BrainF_ck.new
code = ARGV[0]
brainf_ck.exec(code)

$ruby brainf_ck.rb +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

> A

-は、+と同様に実装すれば簡単ですね。

><は、このままでは少し問題があります。下記のように入力を与えると>が引数として認識されないのです。今回は、ファイルから入力データを呼び出すことにしましょう。

$ruby brainf_ck.rb >+++++.

class BrainF_ck

def initialize(code)
@tape = []
@pc = 0
@c_position = 0
@code = code
end

def exec
chars_code = @code.chars ## 入力を一文字ずつに区切る
while @pc < chars_code.length
case chars_code[@pc]
when "+"
inc
when "-"
dec
when "."
show
when ">"
right
when "<"
left
end
@pc += 1
end
end

private

# dec means (-)
def dec
@tape[@c_position] ||= 0
@tape[@c_position] -= 1
end

# right means (>)
def right
@c_position += 1
end

# left means (<)
def left
@c_position -= 1
end

end

code = ARGF.read
brainf_ck = BrainF_ck.new(code)
brainf_ck.exec

ここまでは、すんなり命令どおりに実装出来ました。

難しいのは、[]なんです。

少し時間をとってどのように実装すればいいか考えてみましょう。

一つの例は、ジャンプする場所を予めHashで持たせておくことです。

def analyze_jump(code)

stack = []
chars_code = code.chars ## 入力を一文字ずつに区切る
jump_p = {}
chars_code.each_with_index do |word, current|
if word == "["
left = current
right = current
loop do
if code[right] == "["
stack.push(1)
end
if code[right] == "]"
stack.pop()
end
if stack.length == 0
break
end
right += 1
end
jump_p[left] = right
jump_p[right] = left
end
end
jump_p
end

上記のコードでは、stackというデータ構造を利用しています。

スタックとは、後に入れたものが先に出る構造です。

[が見つかった時、入れ子がなければpopが一回だけ実行されてstackの中身がなくなります。

もし入れ子があれば、入れ子の数だけstackにpushされ、同じ数だけpopが実行されます。

この処理に、よって入れ子を考慮してジャンプの位置をhashにできます。


全体コード

class BrainF_ck

def initialize(code)
@tape = []
@pc = 0
@c_position = 0
@code = code
@jump_position = analyze_jump(@code)
end

def exec
chars_code = @code.chars ## 入力を一文字ずつに区切る
while @pc < chars_code.length
case chars_code[@pc]
when "+"
inc
when "-"
dec
when "."
show
when ">"
right
when "<"
left
when "["
jump_right
when "]"
jump_left
end
@pc += 1
end
end

private
# inc means (+)
def inc
@tape[@c_position] ||= 0
@tape[@c_position] += 1
end

# dec means (-)
def dec
@tape[@c_position] ||= 0
@tape[@c_position] -= 1
end

# show means (.)
def show
puts @tape[@c_position].chr
end

# right means (>)
def right
@c_position += 1
end

# left means (<)
def left
@c_position -= 1
end

def jump_right
if @tape[@c_position] == 0
@pc = @jump_position[@pc]
end
end

def jump_left
if @tape[@c_position] != 0
@pc = @jump_position[@pc]
end
end

def analyze_jump(code)
stack = []
chars_code = code.chars ## 入力を一文字ずつに区切る
jump_p = {}
chars_code.each_with_index do |word, current|
if word == "["
left = current
right = current
loop do
if code[right] == "["
stack.push(1)
end
if code[right] == "]"
stack.pop()
end
if stack.length == 0
break
end
right += 1
end
jump_p[left] = right
jump_p[right] = left
end
end
jump_p
end

end

code = ARGF.read
brainf_ck = BrainF_ck.new(code)
brainf_ck.exec


hello.txt

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.

------------.<++++++++.--------.+++.------.--------.>+.

$ruby brainf_ck.rb hello.txt


課題

,を実装せよ

命令
意味

,
入力から1バイト読み込んで、ポインタが指す先に代入する。

初めの文字に、<が与えられた時にどのような処理をするか考えて実装せよ。


参考文献

Brainfuck

今すぐBrainf*ckを始めるべき10の理由


深めたい人

ふつうのコンパイラをつくろう