空白言語WhiteSpaceとは？Rubyで実装してみた
WhiteSpaceとは？
Whitespace（ホワイトスペース）は、プログラミング言語のひとつであり、またそれを動作させるインタプリタを指している。WhitespaceはGPLにより配布されている。実用言語ではない難解プログラミング言語のひとつ。
WhiteSpaceは空白に相当する文字のみで構成されたプログラミング言語です。
上記のものは空白やタブ、改行のみで構成されていますが、WhiteSpaceの場合これもコードです。
$ ruby whitespace.rb count.ws 1 ・ ・ 10
ちなみに処理としては1から10までの文字を出力するもので、実際に実行しても正常に動作していますね。
仕様
WhiteSpaceは下記3つの要素で構成されています。
- IMP
- コマンド
- パラメーター
IMPは一言で表すなら「どんな種類の処理をしたいか指定するもの」です。処理の種類は5つあり、どのIMPを指定するかによって選べるコマンドとパラメーターも決まってきます。
スタック操作
その名の通りスタックを操作するものです。IMPは[Space]。
| IMP | コマンド | パラメーター | 詳細 |
|---|---|---|---|
| [space] | [Space] | 数値 | パラメーターで指定した数値をスタックに積む |
| [space] | [LF][Space] | - | スタックの一番上の値を複製する |
| [space] | [LF][Tab] | - | スタックの上から2つの値を入れ替える |
| [space] | [LF][LF] | - | スタックの一番上の値を削除する |
演算
スタックの上に積まれてる2つのリテラルを取り出しそれらで演算を行い、結果を再びスタックに積みます。IMPは[Tab][Space]。
| IMP | コマンド | パラメーター | 詳細 |
|---|---|---|---|
| [Tab][Space] | [Space][Space] | – | 足し算 |
| [Tab][Space] | [Space][Tab] | – | 引き算 |
| [Tab][Space] | [Space][LF] | – | 掛け算 |
| [Tab][Space] | [Tab][Space] | – | 割り算 |
| [Tab][Space] | [Tab][Tab] | – | 剰余 |
ヒープ操作
その名の通りヒープに値を保存したり取り出したりし、変数のような扱いができます。IMPは[Tab][Tab]。
| IMP | コマンド | パラメーター | 詳細 |
|---|---|---|---|
| [Tab][Tab] | [Space] | - | スタックの一番上を値としその次のものをアドレスとし、ヒープ上のそのアドレスに対応する位置にその値を保存する |
| [Tab][Tab] | [Tab] | - | スタックの一番上をアドレスとし、ヒープ上のそのアドレスに対応する位置にある値をスタックに積む。 |
制御命令
指定した箇所にマークをつけるたりそこにジャンプしたりすることができます。これにより繰り返しなどが実現できます。IMPは[LF]。
| IMP | コマンド | パラメーター | 詳細 |
|---|---|---|---|
| [LF] | [Space][Space] | ラベル | マークする |
| [LF] | [Space][Tab] | ラベル | 関数を呼ぶ |
| [LF] | [Space][LF] | ラベル | パラメーターで指定したマークにジャンプする |
| [LF] | [Tab][Space] | ラベル | スタックの一番上が0の場合にジャンプする |
| [LF] | [Tab][Tab] | ラベル | スタックの一番上が負の値の場合にジャンプする |
| [LF] | [Tab][LF] | - | 関数の実行を終了し呼び出し元に戻る |
| [LF] | [LF][LF] | - | プログラムを終了する |
入出力
スタックの一番上の値を取り出し出力したり、スタックからアドレスを取り出しそのアドレスの位置に入力された文字を書き込んだりします。IMPは[Tab][LF]。
| IMP | コマンド | パラメーター | 詳細 |
|---|---|---|---|
| [Tab][LF] | [Space][Space] | - | スタックの一番上の値に等しい文字コードに対応する文字を出力する |
| [Tab][LF] | [Space][Tab] | - | スタックの一番上の数値を文字列として出力する |
| [Tab][LF] | [Tab][Space] | - | 入力された文字に対応するアヒープ上のドレスの位置に、スタックの一番上の値を積む |
| [Tab][LF] | [Tab][Tab] | - | 入力された数値に対応するヒープ上のアドレスの位置に、スタックの一番上の値を積む |
大まかな概要はこんな感じ。詳細は公式のチュートリアルをご参照ください。
WhiteSpaceをRubyで実装してみる
1. 字句解析
def tokenize # 字句解析
result = []
scanner = StringScanner.new(@code)
while !(scanner.eos?) # スキャンが最後尾まで達したか
para = nil # パラメーターをnilに
unless scanner.scan(/\A( |\n|\t[ \n\t])/)
raise Exception, "undefined imp"
end
imps = {
" " => :stack,
"\t " => :arithmetic,
"\t\t" => :heap,
"\n" => :flow,
"\t\n" => :io
}
imp = imps[scanner[0]]
case imp
#-----スタック操作-----
when :stack
unless scanner.scan(/ |\n[ \t\n]/)
raise Exception, "undefined cmd of stack"
end
cmds = {
" " => :push,
"\n " => :duplicate,
"\n\t" => :swap,
"\n\n" => :discard
}
cmd = cmds[scanner[0]]
if cmd == :push # pushの場合パラメータを取得
unless scanner.scan(/[ \t]+\n/) # \nが来るまではパラメーター
raise Exception, "undefined parameter of stack"
end
para = scanner[0]
end
#-----演算-----
when :arithmetic
unless scanner.scan(/ [ \t\n]|\t[ \t]/)
raise Exception, "undefined cmd of arithmetic"
end
cmds = {
" " => :addition,
" \t" => :subtraction,
" \n" => :multiplicate,
"\t " => :integer_division,
"\t\t" => :modulo
}
cmd = cmds[scanner[0]]
#-----ヒープ操作-----
when :heap
unless scanner.scan(/ |\t/)
raise Exception, "undefined cmd of heap"
end
cmds = {
" " => :store,
"\t" => :retrieve
}
cmd = cmds[scanner[0]]
#-----制御命令-----
when :flow
unless scanner.scan(/ [ \t\n]|\t[ \t\n]|\n\n/)
raise Exception, "undefined cmd of flow"
end
cmds = {
" " => :mark,
" \t" => :call,
" \n" => :jump_uncondionally,
"\t " => :jump_zero,
"\t\t" => :jump_negative,
"\t\n" => :end_and_transfer,
"\n\n" => :end,
}
cmd = cmds[scanner[0]]
unless (cmd == :end_and_transfer) || (cmd == :end) #end_and_transferもしくはend以外のコマンドの場合パラメータを取得
unless scanner.scan(/[ \t]+\n/) # \nが来るまではパラメーター
raise Exception, "undefined parameter of flow"
end
para = scanner[0]
end
#-----入出力-----
when :io
unless scanner.scan(/ [ \t]|\t[ \t]/)
raise Exception, "undefined cmd of io"
end
cmds = {
" " => :output_character,
" \t" => :output_number,
"\t " => :read_character,
"\t\t" => :read_number
}
cmd = cmds[scanner[0]]
end
result << [imp,cmd,para] # それぞれを配列に格納
end
result
endまず字句解析をします。scanメソッドはStringScannerクラスのもので、eos?メソッドを使ってトークンが最後尾まで達したかを判定しています。
2. 構文解析
def evaluate
@tokens = []
@tokens_sub =tokenize # パラメータを数値に変換するための配列
@stack = []
@call_stack = []
@heap = {}
pc = 0 # カウンター
@tokens_sub.each do |im,cm,pa| # パラメーターを全て数値に変換
pa2 = pa
if pa #パラメーターがnilでない場合のみ
pa2.gsub!(/ /,"0")
pa2.gsub!(/\t/,"1")
sign= pa2.slice!(0) # 符号を取得
pa2 = pa2.to_i(2) # 10進数に変換
if sign == "1"
pa2 = pa2 * (-1) # 負の値に
end
end
@tokens << [im,cm,pa2] # 本命の@tokensに格納
end
count=0
while true do
imp , cmd , para = @tokens
count = count +1
(省略)そして構文解析。変数pcはマークする際やジャンプする際に使用するカウンターのようなものです。
次にIMPそれぞれの操作を書いていきます。
3. スタック操作
case imp
#-----スタック操作-----
when :stack
pc = pc + 1
cmds = {
" " => :push,
"\n " => :duplicate,
"\n\t" => :swap,
"\n\n" => :discard
}
case cmd
when :push
@stack.push(para)
when :duplicate
@stack.push(@stack.first)
when :swap
top_second = @stack.delete_at(@stack.size-2) # topの2つを入れ替える
@stack.push(top_second)
when :discard
@stack.pop
end4. 演算
#-----演算-----
when :arithmetic
pc = pc + 1
elm = @stack.pop
elm2 = @stack.pop
case cmd
when :addition # 和
@stack.push(elm2 + elm)
when :subtraction # 差
@stack.push(elm2 - elm)
when :multiplicate # 積
@stack.push(elm2 * elm)
when :integer_division # 商
@stack.push(elm2 / elm)
when :modulo # 剰余
@stack.push(elm2 % elm)
end5. ヒープ操作
#-----ヒープ操作-----
when :heap
pc = pc + 1
case cmd
when :store # ハッシュに保存
value = @stack.pop
key =@stack.pop
@heap.store(key,value)
when :retrieve # スタックに追加
key = @stack.pop
@stack.push(@heap[key])
end6. 制御命令
#-----制御命令-----
when :flow
case cmd
when :mark
pc += 1
when :jump_uncondionally # ジャンプ
n = 0
@tokens.each {|im,cm,pa|
if cm == :mark && pa == para
pc = n+1
end
n += 1
}
when :call
@call_stack.push(pc) # スタックに現在の位置をプッシュ
n=0
@tokens.each {|im,cm,pa|
if cm == :mark && pa == para
pc = n+1
end
n += 1
}
when :jump_zero # スタックの先頭が0ならジャンプ
if @stack.pop == 0
n = 0
@tokens.each {|im,cm,pa|
if cm == :mark && pa == para
pc = n+1
end
n += 1
}
else
pc += 1
end
when :jump_negative # スタックの先頭が負ならジャンプ
if @stack.pop < 0
n = 0
@tokens.each {|im,cm,pa|
if cm == :mark && pa == para
pc = n+1
end
n += 1
}
else
pc += 1
end
when :end_and_transfer
pc = @call_stack.pop
pc =pc +1
when :end # 終了
exit
end7. 入出力
#-----入出力-----
when :io
pc = pc + 1
case cmd
when :output_character # 文字を出力
print @stack.pop.chr
when :output_number # 数値を出力
puts @stack.pop.to_s
when :read_character # 文字コードの入力
key = @stack.pop
print("入力=>")
value =STDIN.gets.ord # 文字コードに変換
@heap.store(key,value)
when :read_number #数値の入力
key = @stack.pop
print("入力=>")
value =STDIN.gets.to_i # 整数に変換
@heap.store(key,value)
endこれでIMPそれぞれの処理は書けました。あとはtokenizeとevaluateを呼び出してあげるだけです。
require "strscan"
class WhiteSpace
def initialize
@code = ""
@file_name = ARGV[0]
@file = open(@file_name) # コマンドライン引数で渡されたファイルの内容を取得
@file.each do |line|
@code << line
end
tokenize()
evaluate()
end
(中略)
end
WhiteSpace.newこれで完成です 🎉