　みなさんこんにちは! tukinyanJP です。今回は BE-Lang の処理系について話そうと思います。さて、今まで BE-Lang は Ruby や C で書かれてきましたが、最近 C で書くことが多くなってきました。ですが、 Ruby 版の BE-Lang がなくなったわけではありません。何が言いたいかというと...

Ruby 実装の BE-Lang を超強化させて復活させる というわけです。

実はずっと前から

　実をいうと C で実装し始めた時から Ruby で試験的に実装していました。ですが今まで従来の実装法では、トークンの優先順位 ¹ や、実行速度が速くならないことに気づきました。私は「どうにか簡単で速く、優先順位をつけられる処理系(の実装方法)はないのだろうか。」と悩み Google 先生を使って調べてみました。そこで、私の目に留まった処理系(の実装方法)こそが

再帰下降構文解析

です。例えば、 Ruby で書く四則演算の抽象構文木を生成するものがこちらです。

四則演算抽象構文木生成

min.rb

class Parser
  def initialize(tokens)
    @tokens = tokens
    @pos = 0
  end

  # 式 (expression) = 項 (+|-) 項 ...
  def parse_expression
    node = parse_term
    while peek == "+" || peek == "-"
      op = consume
      node = { op: op, left: node, right: parse_term }
    end
    node
  end

  # 項 (term) = 因子 (*|/) 因子 ...
  def parse_term
    node = parse_factor
    while peek == "*" || peek == "/"
      op = consume
      node = { op: op, left: node, right: parse_factor }
    end
    node
  end

  # 因子 (factor) = 数値 | "(" 式 ")"
  def parse_factor
    token = consume
    if token == "("
      node = parse_expression
      consume # ")" を読み飛ばす
      node
    else
      { type: :number, value: token.to_i }
    end
  end

  private

  def peek
    @tokens[@pos]
  end

  def consume
    token = peek
    @pos += 1
    token
  end
end

tokens = ["1", "+", "1"]
parser = Parser.new(tokens)
ast = parser.parse_expression
p ast

これを実行するとこういう抽象構文木を生成してくれます。

{op: "+", left: {type: :number, value: 1}, right: {type: :number, value: 1}}

ちなみに、このコードでなぜ演算子の優先順位ができるかというと、例えば足し算と引き算のメゾット parse_expression を見てください。

    node = parse_term
    while peek == "+" || peek == "-"
      op = consume
      node = { op: op, left: node, right: parse_term }
    end

このように書いていますよね。先に、 node_term を呼び出している。つまり、 掛け算や割り算の値を先に抽象構文木を生成してから足し算の抽象構文木を生成している ので、優先順位が自然とできるのです。²

では、具体的なコードを。

　では、さっそく実装を始めましょう。始める際に再帰下降構文解析のパーサから書くのもよいのですが、せっかくなので文字列を配列に変換する字句解析器を作りましょう。

Lexer クラス

lexer.rb

require 'strscan'

class Lexer
  def initialize(input)
    @scanner = StringScanner.new(input)
  end

  def tokenize
    tokens = []
    until @scanner.eos?
      @scanner.skip(/\s+|#.*/)
      next if @scanner.eos?
      if val = @scanner.scan(/"[^"]*"/)
        tokens << { type: :str_literal, value: val[1..-2] }
      elsif val = @scanner.scan(/[a-zA-Z_]\w*|-?\d+|&&|\|\||==|!=|>=|<=|>|<|%|[\+\-\*\/\(\)=\[\]\{\}:,\.]/) # ここに正規表現を追加してタイプを追加
        tokens << val
      else
        @scanner.getch
      end
    end
    tokens
  end
end

　なんて美しく書けるんでしょう。これだけで字句解析器は終了です。一応いつもの三行で説明してみますと、

initialize メゾットで文字列スキャナーを生成
tokenize メゾットで先ほど生成したスキャナーを使って分割
そのまま分割したものを返り値にする

たったこれだけで、 1 + 1 という文字列が ["1", "+", "1"] という配列になります。これを再帰下降構文解析パーサにかけることで、先ほどの {op: "+", left: {type: :number, value: 1}, right: {type: :number, value: 1}} のような形にできます。 さぁ本番の再帰下降構文解析パーサですね! 先ほどの四則演算パーサと同じようにしていきましょう。こんな感じですね。

Parser クラス

parser.rb

class Parser
  def initialize(input)
    lexer = Lexer.new(input)
    @tokens = lexer.tokenize
  end

  def parse_expression
    node = parse_compare
    while @tokens.any? && ['&&', '||'].include?(@tokens.first)
      op = @tokens.shift
      right = parse_compare
      node = { type: op, left: node, right: right }
    end
    node
  end

  def parse_compare
    node = parse_add_sub
    while @tokens.any? && ['==', '!=', '>', '<', '>=', '<='].include?(@tokens.first)
      op = @tokens.shift
      right = parse_add_sub
      node = { type: op, left: node, right: right }
    end
    node
  end

  def parse_add_sub
    node = parse_term
    while @tokens.any? && ['+', '-'].include?(@tokens.first)
      op = @tokens.shift
      right = parse_term
      node = { type: op, left: node, right: right }
    end
    node
  end

  def parse_term
    node = parse_factor
    while @tokens.any? && ['*', '/', '%'].include?(@tokens.first)
      op = @tokens.shift
      right = parse_factor
      node = { type: op, left: node, right: right }
    end
    node
  end

  def parse_factor
    token = @tokens.shift
    return nil if token.nil?

    node = if token.is_a?(Hash) && token[:type] == :str_literal
      { type: :str, value: token[:value] }
    elsif token == '('
      n = parse_expression
      @tokens.shift
      n
    elsif token == '['
      parse_array
    elsif token == '{' 
      parse_hash
    elsif token =~ /^-?\d+$/
      { type: :num, value: token.to_i }
    else
      name = token
      return nil if ["do", "elsif", "else", "end"].include?(name)

      # 次が '(' なら関数呼び出しとしてパース
      if @tokens.first == "("
        @tokens.shift # "(" を捨てる
        args = []
        while @tokens.any? && @tokens.first != ")"
          args << parse_expression
          @tokens.shift if @tokens.first == "," # カンマがあれば飛ばす
        end
        @tokens.shift # ")" を捨てる
        { type: :call, name: name, args: args }
      else
        # '(' がなければ単なる変数
        { type: :var, name: name }
      end
    end

    while @tokens.any? && @tokens.first == '['
      @tokens.shift # '['
      index_expr = parse_expression
      @tokens.shift # ']'
      node = { type: :index, target: node, index: index_expr }
    end


    while @tokens.first == "."
      @tokens.shift
      method_name = @tokens.shift      
      args = []
      if @tokens.first == "("
        @tokens.shift # "("
        while @tokens.any? && @tokens.first != ")"
          args << parse_expression
          @tokens.shift if @tokens.first == ","
        end
        @tokens.shift # ")"
      end
      node = { type: :method_call, target: node, name: method_name, args: args }
    end

    node
  end


  def parse_array 
    elements = []
    until @tokens.first == ']' || @tokens.empty?
      elements << parse_expression
      if @tokens.first == ','
        @tokens.shift
      end
    end
    @tokens.shift
    { type: :array, elements: elements }
  end

  def parse_hash
    pairs = []
    until @tokens.first == '}' || @tokens.empty?
      key = parse_expression
      @tokens.shift if @tokens.first == ':'
      val = parse_expression
      pairs << { key: key, value: val }
      @tokens.shift if @tokens.first == ','
    end
    @tokens.shift # '}' を捨てる
    { type: :hash, pairs: pairs }
  end

  def parse_stmt
    case @tokens.first
    when "puts"
      @tokens.shift
      { type: :puts, value: parse_expression }
    when "if", "elsif"
      parse_if_stmt
    when "while"
      parse_while_stmt
    when "def"
      parse_def_stmt
    when "return"
      @tokens.shift # "return"
      { type: :return, value: parse_expression }
    else
      node = parse_expression
      return nil if node.nil?
      if @tokens.first == '='
        @tokens.shift
        right = parse_expression
        if node[:type] == :index
          node = { type: :index_assign, target: node[:target], index: node[:index], value: right }
        elsif node[:type] == :var
          node = { type: :assign, name: node[:name], value: right }
        end
      end
      node
    end
  end

  def parse_if_stmt
    @tokens.shift # "if" または "elsif"
    condition = parse_expression
    
    @tokens.shift if @tokens.first == "do"

    then_stmts = []
    while @tokens.any? && !["elsif", "else", "end"].include?(@tokens.first)
      then_stmts << parse_stmt
    end

    else_stmts = []
    if @tokens.first == "elsif"
      else_stmts << parse_if_stmt
    elsif @tokens.first == "else"
      @tokens.shift
      @tokens.shift if @tokens.first == "do"
      while @tokens.any? && @tokens.first != "end"
        else_stmts << parse_stmt
      end
      @tokens.shift if @tokens.first == "end" # 最後の end
    elsif @tokens.first == "end"
      @tokens.shift
    end

    { type: :if, condition: condition, then: then_stmts, else: else_stmts }
  end

  def parse_while_stmt
    @tokens.shift
    condition = parse_expression
    
    @tokens.shift if @tokens.first == "do"

    body = []
    while @tokens.any? && @tokens.first != "end"
      body << parse_stmt
    end
    @tokens.shift if @tokens.first == "end" # "end" を捨てる

    { type: :while, condition: condition, body: body }
  end

  def parse_def_stmt
    @tokens.shift # "def"
    name = @tokens.shift # def name
    
    params = []
    if @tokens.first == "("
      @tokens.shift # "("
      while @tokens.any? && @tokens.first != ")"
        params << @tokens.shift
        @tokens.shift if @tokens.first == ","
      end
      @tokens.shift # ")"
    end

    @tokens.shift if @tokens.first == "do"

    body = []
    while @tokens.any? && @tokens.first != "end"
      body << parse_stmt
    end
    @tokens.shift
    { type: :def, name: name, params: params, body: body }
  end
end

これも parse_expresion メゾットからどんどん優先順位が高いものを呼んでいるので、ちゃんと動作しますね。これには四則演算、関数定義、配列、ハッシュ、文字列、標準出力、ループ、条件分岐が定義されています。実行してみないと動く感じがしませんよね。初代 Ruby 実装の BE-Lang もテストで行った FizzBuzz の抽象構文木を生成してみたいと思います。

実行したコード

def fizzbuzz(n)
  i = 0
  while i <= n
    if i % 15 == 0 # 15で割り切れるとき
      puts("Fizz Buzz")
    elsif i % 5 == 0 # 5の場合
      puts("Buzz")
    elsif i % 3 == 0 # 3の場合
      puts("Fizz")
    else # どれでもなかった場合
      puts(i)
    end
    i = i + 1
  end
end

fizzbuzz(15) # 15 までの fizzbuzz を求める

出力された抽象構文木

{type: :def,
 name: "fizzbuzz",
 params: ["n"],
 body:
  [{type: :assign, name: "i", value: {type: :num, value: 1}},
   {type: :while,
    condition: {type: "<=", left: {type: :var, name: "i"}, right: {type: :var, name: "n"}},
    body:
     [{type: :if,
       condition: {type: "==", left: {type: "%", left: {type: :var, name: "i"}, right: {type: :num, value: 15}}, right: {type: :num, value: 0}},
       then: [{type: :puts, value: {type: :str, value: "Fizz Buzz"}}],
       else:
        [{type: :if,
          condition: {type: "==", left: {type: "%", left: {type: :var, name: "i"}, right: {type: :num, value: 5}}, right: {type: :num, value: 0}},
          then: [{type: :puts, value: {type: :str, value: "Buzz"}}],
          else:
           [{type: :if,
             condition:
              {type: "==", left: {type: "%", left: {type: :var, name: "i"}, right: {type: :num, value: 3}}, right: {type: :num, value: 0}},
             then: [{type: :puts, value: {type: :str, value: "Fizz"}}],
             else: [{type: :puts, value: {type: :var, name: "i"}}]}]}]},
      {type: :assign, name: "i", value: {type: "+", left: {type: :var, name: "i"}, right: {type: :num, value: 1}}}]}]}
{type: :call, name: "fizzbuzz", args: [{type: :num, value: 15}]}

この抽象構文木をみて「ﾅﾆｺﾚ...」ってなる人もいるでしょう。しかし大丈夫です。安心してください。ちょっとずつひも解いていくとわかるはずです。箇条書きを入れ子にするとわかりやすいかもしれません。

{type: :def, name: "fizzbuzz", params: ["n"], body: 意味: "fizzbuzz" っていう 関数定義 するよー! 引数は n だけだよー! 中身はこれ! (次に続く) ³
- [{type: :assign, name: "i", value: {type: :num, value: 1}}, 意味: "i" っていう 変数定義 するよー! 値の型は数字で、1 だよー! ⁴
- {type: :while, condition: {type: "<=", left: {type: :var, name: "i"}, right: {type: :var, name: "n"}},body: **変数 "i" の値が、変数 "n" (引数) の値以下の場合に body: (中身) を実行するね! ** ⁵
  - [{type: :if, condition: {type: "==", left: {type: "%", left: {type: :var, name: "i"}, right: {type: :num, value: 15}}, right: {type: :num, value: 0}}, then: [{type: :puts, value: {type: :str,value: "Fizz Buzz"}}],else:, ...if 意味: **もし、変数 i の値が 15 で割ったときの余りが 0 なら "FizzBuzz" っていう文字列を表示してねー! でなければ 5で割り切れる場合それでもなければ3で割り切れるか... ** ⁶

こういう感じです。これだけでは実行できた判定にはならないので、この AST をたどって実行する関数を書いていきましょう。

実行する関数

eval.rb

def evaluate(node, env = @env)
  case node[:type]
  when :num, :str
    return node[:value]
  when :array
    node[:elements].map { |e| evaluate(e, env) }
  when :index
    target = evaluate(node[:target], env)
    idx = evaluate(node[:index], env)
    target[idx]
  when :index_assign
    target = evaluate(node[:target], env)
    idx = evaluate(node[:index], env)
    val = evaluate(node[:value], env)
    target[idx] = val
    val
  when :hash
    h = {}
    node[:pairs].each do |pair|
      h[evaluate(pair[:key], env)] = evaluate(pair[:value], env)
    end
    h
  when :def
    @functions[node[:name]] = { params: node[:params], body: node[:body] }
    nil
  when :call
    func = @functions[node[:name]]
    raise "Undefined function: #{node[:name]}" unless func

    local_env = {}
    func[:params].each_with_index do |param, i|
      local_env[param] = evaluate(node[:args][i], env)
    end

    result = catch(:return) do
      last_val = nil
      func[:body].each { |stmt| last_val = evaluate(stmt, local_env) }
      last_val
    end
    result
  when :return
    val = evaluate(node[:value], env)
    throw :return, val
  when :if
    if evaluate(node[:condition], env)
      result = nil
      node[:then].each { |stmt| result = evaluate(stmt, env) }
      result
    else
      result = nil
      node[:else].each { |stmt| result = evaluate(stmt, env) }
      result
    end
  when :while
    result = nil
    while evaluate(node[:condition], env)
      node[:body].each { |stmt| result = evaluate(stmt, env) }
    end
    result
  when :puts
    result = evaluate(node[:value], env)
    print_val(result)
    result
  when :var
    env.key?(node[:name]) ? env[node[:name]] : (@env[node[:name]] || 0)
  when :assign
    env[node[:name]] = evaluate(node[:value], env)
  when "+", "-", "*", "/", "==", "!=", ">", "<", ">=", "<=", "%", "&&", "||"
    left = evaluate(node[:left], env)
    right = evaluate(node[:right], env)
    case node[:type]
    when "+" then left + right
    when "-" then left - right
    when "*" then left * right
    when "/" then left / right
    when "==" then left == right
    when "!=" then left != right
    when ">"  then left > right
    when "<"  then left < right
    when ">=" then left >= right
    when "<=" then left <= right
    when "%"  then left % right
    when "&&" then left && right
    when "||" then left || right
    end
  when :method_call
    target_val = evaluate(node[:target], env)
    args_vals = node[:args].map { |arg| evaluate(arg, env) }
    target_val.send(node[:name], *args_vals)
  else
    raise "未知のノード: #{node[:type]}"
  end
end

これは、巨大な一つの case 文です。 {type: :def} と書かれているところを参照して、そのタイプに合わせた処理をする関数ですね。ここは、特に解説することはありませんね。再起呼び出しを使ったフィボナッチ数列の抽象構文木をここに書いておくので自分なりに解釈してみてください。

実行したコードと抽象構文木

こちらがフィボナッチ数列のコードです。


def fib(n)
    if n <= 1
        return n
    else
        return fib(n - 1) + fib(n - 2)
    end
end

puts(fib(10)) # => 55

こちらは抽象構文木。

{type: :def,
 name: "fib",
 params: ["n"],
 body:
  [{type: :if,
    condition: {type: "<=", left: {type: :var, name: "n"}, right: {type: :num, value: 1}},
    then: [{type: :return, value: {type: :var, name: "n"}}],
    else:
     [{type: :return,
       value:
        {type: "+",
         left: {type: :call, name: "fib", args: [{type: "-", left: {type: :var, name: "n"}, right: {type: :num, value: 1}}]},
         right: {type: :call, name: "fib", args: [{type: "-", left: {type: :var, name: "n"}, right: {type: :num, value: 2}}]}}}]}]}
{type: :puts, value: {type: :call, name: "fib", args: [{type: :num, value: 10}]}}

終わりに

　今回は久しぶりに長編の記事を書いてみました。いやー楽しかったですね。これからもどんどんこの自作言語の記事の更新やっていきます!

ちなみに..初代 Ruby 実装の BE-Lang は、 FizzBuzz を 100まで求めるのに 1.6秒(Ruby起動時間を含め) 今回実装した BE-Lang では 0.8 秒 (Ruby起動時間含め) でした。

実は、 BE-Lang Ruby gems に公開しました! (記事の投稿日を見てください。エイプリルフール..?) うれしいですね! それではみなさん次の記事で! さようなら!

1 + 1 * 2 という式があったとしましょう。ふつうは、 1 * 2 をしてから 1 を足しますよね。しかし従来の Ruby 実装の BE-Lang は (1 + 1) * 2 と解釈して 4 を返していました。 ↩
どうやら再帰下降構文解析は、左再帰に弱いらしいです。多分 i = 0; i = i + 1; みたいなコードのことでしょうか。別に私が実装したものでは正常に動いていたのですが... ↩
def fizzbuzz(n) がこれに当たります。 ↩
i = 1 がこれに当たります。 ↩
while i <= n がこれに当たります。 ↩
if i % 15 == 0 がこれに当たります。 ↩