...

空白言語WhiteSpaceを実装してみる

空白言語WhiteSpaceを実装してみる

どうもおはようポテト(@ohayoupoteto22)です。

空白のみの言語、WhiteSpaceを実装するんだぞ

ということで今回はRubyでWhiteSpaceを実装してみます。

ブログ主の単なる備忘録ではありますが参考になれば幸いです⸝⸝- ̫ -⸝⸝

ブログ主

早速いってみよう!

そもそもWhiteSpaceって?


一言で表すならWhiteSpaceは空白に相当する文字のみで構成されたプログラミング言語です。

Whitespace(ホワイトスペース)は、プログラミング言語のひとつであり、またそれを動作させるインタプリタを指している。WhitespaceはGPLにより配布されている。実用言語ではない難解プログラミング言語のひとつ。
引用:Wikipedia

空白のみのソースコード

例えばこれ。こちら空白やタブ、改行のみで構成されていますが、WhiteSpaceの場合これもコードです。

こんなん気付かんわ

くるみ

ちなみに上のコードは1から10までの文字を出力するものです。

$ ruby whitespace.rb count.ws
1
・
・
10
そんな摩訶不思議なWhiteSpaceの概要についてサラッと見てみましょう。

WhiteSpaceの概要

WhiteSpaceはIMPコマンドパラメーターの3つで構成されています。

以下、それぞれについて簡単にまとめてみました。

IMPごとのコマンドとパラメーター

IMPは一言で表すなら「どんな種類の処理をしたいか指定するもの」です。
処理の種類は5つあり、どのIMPを指定するかによって選べるコマンドとパラメーターも決まってきます。

スタック操作

その名の通りスタックを操作するものです。IMPは[Space]。

IMPコマンドパラメーター詳細
[space]
[Space]数値パラメーターで指定した数値をスタックに積む
[LF][Space]スタックの一番上の値を複製する
[LF][Tab]スタックの上から2つの値を入れ替える
[LF][LF]スタックの一番上の値を削除する

演算

スタックの上に積まれてる2つのリテラルを取り出しそれらで演算を行い、結果を再びスタックに積みます。IMPは[Tab][Space]。

IMPコマンドパラメーター詳細
[Tab][Space]
[Space][Space]足し算
[Space][Tab]引き算
[Space][LF]掛け算
[Tab][Space]割り算
[Tab][Tab]剰余

ヒープ操作

その名の通りヒープに値を保存したり取り出したりし、変数のような扱いができます。IMPは[Tab][Tab]。

IMPコマンドパラメーター詳細
[Tab][Tab]
[Space]スタックの一番上を値としその次のものをアドレスとし、ヒープ上のそのアドレスに対応する位置にその値を保存する
[Tab]スタックの一番上をアドレスとし、ヒープ上のそのアドレスに対応する位置にある値をスタックに積む。

制御命令

指定した箇所にマークをつけるたりそこにジャンプしたりすることができます。これにより繰り返しなどが実現できます。IMPは[LF]。

IMPコマンドパラメーター詳細
[LF]
[Space][Space]ラベルマークする
[Space][Tab]ラベル関数を呼ぶ
[Space][LF]ラベルパラメーターで指定したマークにジャンプする
[Tab][Space]ラベルスタックの一番上が0の場合にジャンプする
[Tab][Tab]ラベルスタックの一番上が負の値の場合にジャンプする
[Tab][LF]関数の実行を終了し呼び出し元に戻る
[LF][LF]プログラムを終了する

入出力

スタックの一番上の値を取り出し出力したり、スタックからアドレスを取り出しそのアドレスの位置に入力された文字を書き込んだりします。IMPは[Tab][LF]。

IMPコマンドパラメーター詳細
[Tab][LF]
[Space][Space]スタックの一番上の値に等しい文字コードに対応する文字を出力する
[Space][Tab]スタックの一番上の数値を文字列として出力する
[Tab][Space]入力された文字に対応するアヒープ上のドレスの位置に、スタックの一番上の値を積む
[Tab][Tab]入力された数値に対応するヒープ上のアドレスの位置に、スタックの一番上の値を積む
なんとなーく分かった!

くるみ

大まかな概要はこんな感じ。詳細は公式のチュートリアルをご参照ください。
というわけで実際に実装していきましょう。

WhiteSpaceをRubyで実装してみる

字句解析

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?メソッドを使ってトークンが最後尾まで達したかを判定しています。

構文解析

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それぞれの操作を書いていきます。

スタック操作

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
    end

演算

  #-----演算-----
  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)
    end

ヒープ操作

  #-----ヒープ操作-----
  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])
    end

制御命令

  #-----制御命令-----
  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
  end

入出力

    #-----入出力-----
    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

これで終わりっ。

お疲れ様!

くるみ

まとめ

以上「空白言語WhiteSpaceをRubyで実装してみる」でした。

参考になれば幸いです!では⸝⸝- ̫ -⸝⸝

参考になったらシェアしよう

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA