Ruby: 入れ子の配列だけをパースできるパーサを作る（手書きの再帰下降パーサ）

たとえば ((), (), (())) という文字列を入力として与えると

p parse("((), (), (()))")
#=> [[], [], [[]]]

このように入れ子の配列を出力する（入れ子の配列に変換する）パーサを作ります。

---

入力文字列として使える文字は (, ), ,, 半角スペースの4つだけとします。

いきなり全部やろうとすると大変なので、4つのステップに分けましょう。
以下、「配列」と書いているところは Ruby の配列のイメージで大丈夫です。

• (1) () をパースできる
  • 空配列
• (2) (()) や ((())) をパースできる
  • 配列の入れ子
• (3) (要素, 要素) や (要素, 要素, 要素) をパースできる
  • 配列の要素のくりかえし
• (4) ((), (()))
  • 入れ子とくりかえしの組み合わせ

(0) 全体像と字句解析

全体のイメージはこんな感じ。これを育てていきます。

def parse(src)
  # ここを書いていく
end

src = "()"
tokens = tokenize(src)
tree = parse(tokens)
p tree

字句解析はこれでOK。

$tokens = nil

def tokenize(src)
  src.delete(" ").chars
end

def parse(tokens)
  $tokens = tokens
  # TODO
end

p parse(tokenize("()"))

たとえば tokenize("( )") の結果は ["(", ")"] になります。今回はスペースはあってもなくても同じなのでここで取り除いてしまいます。

グローバル変数 $tokens というのがありますが、きちんと書くなら次のようにパーサクラスのインスタンス変数になるでしょう。

class Parser
  def initialize(tokens)
    @tokens = tokens
    @pos = 0 # 後で出てくる $pos も同様
  end
  # ...
end

この記事ではシンプルさを優先してグローバル変数を使っています。「パーサのしくみを知る」のに必要なもの以外のノイズを減らすため。練習用・おためし用の小さなコードなので問題ないでしょう。

(1) 空配列

トークンの列を先頭から順番に見ていって、最初のトークンが (、次のトークンが ) という順番になっていたら空配列であるとみなし、結果として [] を返します。

$tokens = nil
$pos = nil # 現在のカーソル位置

def tokenize(src); src.delete(" ").chars end

# 現在のカーソル位置のトークンを返す
def peek
  $tokens[$pos]
end

# "(" から、対応する ")" までをパースする
def parse_array
  if peek() == "(" # $toekns[0] をチェック
    # 期待したトークンだったらカーソルを進める
    $pos += 1
  else
    raise "$tokens[0] は ( であるはず"
  end

  if peek() == ")" # $toekns[1] をチェック
    $pos += 1
  else
    raise "$tokens[1] は ) であるはず"
  end

  # 入力トークン列が ["(", ")"] だったらここまで到達するはず
  # → 空配列を返す
  []
end

def parse(tokens)
  # トークン列とカーソル位置をリセット
  $tokens = tokens
  $pos = 0

  parse_array()
end

p parse(tokenize("()")) #=> []

( → ) という順番になっているかチェックしているので、たとえば ) や (( のような入力を渡すとパース失敗という結果になります（期待通りに失敗する）。

(2) 入れ子

再帰呼び出しを使います。再帰が出てくるのでここからちょっと難しくなりますね。

$tokens = nil
$pos = nil

def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end

# "(" と対応する ")" までの中身をパースする
def parse_elements
  elements = []

  if peek() == ")"
    return elements
  end

  elements << parse_array() # 再帰

  elements
end

def parse_array
  if peek() == "("
    $pos += 1
  else
    raise "$tokens[#{$pos}] は ( であるはず"
  end

  ary = parse_elements() # 再帰

  if peek() == ")"
    $pos += 1
  else
    raise "$tokens[#{$pos}] は ) であるはず"
  end

  ary
end

def parse(tokens)
  puts "tokens: " + $tokens.inspect

  # トークン列とカーソル位置をリセット
  $tokens = tokens
  $pos = 0

  parse_array()
end

p parse(tokenize("()"    )) #=> []
p parse(tokenize("(())"  )) #=> [[]]
p parse(tokenize("((()))")) #=> [[[]]]

(3) くりかえし

くりかえしだけをやってみます。

p parse(tokenize(""     )) #=> []
p parse(tokenize("x"    )) #=> ["x"]
p parse(tokenize("x,x"  )) #=> ["x", "x"]
p parse(tokenize("x,x,x")) #=> ["x", "x", "x"]

最初に「入力文字列として使える文字は (, ), ,, 半角スペースの4つだけ」と言っていましたが、このステップでは単純化のために配列の要素として x という文字を使います。

$tokens = nil
$pos = nil

def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end

def parse_repeat
  elements = []

  if $tokens.size <= $pos
    # 要素が0個の場合
    return elements
  end

  # 最初の要素
  elements << peek()
  $pos += 1

  # 2番目以降の要素
  while peek() == ","
    $pos += 1 # カーソルを , の次に進める
    elements << peek()
    $pos += 1
  end

  elements
end

def parse(tokens)
  puts "tokens: " + $tokens.inspect
  $tokens = tokens
  $pos = 0

  parse_repeat()
end

p parse(tokenize(""     )) #=> []
p parse(tokenize("x"    )) #=> ["x"]
p parse(tokenize("x,x"  )) #=> ["x", "x"]
p parse(tokenize("x,x,x")) #=> ["x", "x", "x"]

(4) 入れ子とくりかえしの組み合わせ

(2) と (3) を組み合わせるだけ。

$tokens = nil
$pos = nil

def tokenize(src); src.delete(" ").chars end
def peek; $tokens[$pos] end

def parse_elements
  elements = []

  if peek() == ")"
    return elements
  end

  elements << parse_array()

  while peek() == ","
    $pos += 1
    elements << parse_array()
  end

  elements
end

def parse_array
  if peek() == "("
    $pos += 1
  else
    raise "$tokens[#{$pos}] は ( であるはず"
  end

  ary = parse_elements()

  if peek() == ")"
    $pos += 1
  else
    raise "$tokens[#{$pos}] は ) であるはず"
  end

  ary
end

def parse(tokens)
  puts "tokens: " + $tokens.inspect
  $tokens = tokens
  $pos = 0

  parse_array()
end

p parse(tokenize("()"))           #=> []
p parse(tokenize("(())"))         #=> [[]]
p parse(tokenize("((), ())"))     #=> [[], []]
p parse(tokenize("((), (), ())")) #=> [[], [], []]
p parse(tokenize("((), (()))"))   #=> [[], [[]]]
p parse(tokenize("(((), (())))")) #=> [[[], [[]]]]

これで完成です

おまけ

  if peek() == "("
    # 期待したトークンだったらカーソルを進める
    $pos += 1
  else
    raise "$tokens[#{$pos}] は ( であるはず"
  end

この部分はメソッドに抽出するとよさそうですね。

あわせて、クラス化まで行ったものも貼っておきます。

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

  def peek
    @tokens[@pos]
  end

  def consume(expected)
    if peek() == expected
      @pos += 1
    else
      raise "@tokens[#{@pos}] は #{expected.inspect} であるはず"
    end
  end

  def parse_elements
    elements = []

    if peek() == ")"
      return elements
    end

    elements << parse_array()

    while peek() == ","
      @pos += 1
      elements << parse_array()
    end

    elements
  end

  def parse_array
    consume "("
    ary = parse_elements()
    consume ")"
    ary
  end
end

def tokenize(src)
  src.delete(" ").chars
end

def parse(tokens)
  puts "tokens: " + tokens.inspect
  Parser.new(tokens).parse_array()
end

発展

• 演算子の優先順位
• AST（抽象構文木）を組み立ててから評価（実行）

---