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

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

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

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

---

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

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

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



<!-- ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ -->

# (0) 全体像と字句解析

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

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

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

字句解析はこれでOK。

```ruby
$tokens = nil

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

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

p parse(tokenize("()"))
```

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

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

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

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



<!-- ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ -->

# (1) 空配列

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


```ruby
$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) 入れ子

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

```ruby
$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) くりかえし

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

```ruby
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` という文字を使います。


```ruby
$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) を組み合わせるだけ。


```ruby
$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("(((), (())))")) #=> [[[], [[]]]]
```

これで完成です :tada:



<!-- ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ -->

# おまけ

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

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

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

```ruby
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
```



# 発展

<!-- 四則演算と剰余のみのexprコマンドをRubyで作ってみた - Qiita -->
https://qiita.com/sonota88/items/80b4c02cc1a23fcbe9d1

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

---

<!-- 『RubyでつくるRuby』のMinRubyのパーサを書いた（手書きの再帰下降パーサ） - Qiita -->
https://qiita.com/sonota88/items/84e4c16e5602b9771e92