RaccでSQLを構文解析

この記事はRuby Advent Calendar 2016の21日目の記事です。  
 
僕のようなものが書いていいのか、と思いつつ、
最近開発している、Raccでsqlを構文解析し、formatするプログラムについてお話しします。  

Ruby Advent Calendar なのにRaccってどうなのと思う方々、多めに見てください。  

**完成イメージ**

こんなSQLが、

```sql
select id, name from users
```

```sql
select
  id, name
from
  users
```

こう出力されるつもりです。

単純なWebアプリは大抵はSQLとの戦いだと思うので、このプログラムを用いて開発効率アップしようぜーみたいな発想からやろうと思いました。
(※とりあえず、MySQLのSELECTのみ対応します。)

## Racc
まずはSQLを構文解析して、扱いやすくします。
これにはRuby製のパーサジェネレータ、Raccを使います。  

https://github.com/tenderlove/racc

Raccや構文解析についてはそれだけで本が出ているほどなので、僕が詳しくは説明しません。というかできません。。。
Raccに至っては構文解析がいい感じにできる、くらいしか語れません。。。

ただこれを使うと、Rubyの上で動くプログラミング言語も作れてしまうので、一度触って損はないのでは、と思います。  


今回プログラムの全体構造は以下のような感じになります。

```ruby
class SQLFormatter
rule
  # 構文解析を行うところ。BNFで記述する。
end

---- inner

  def initialize
    @parsed_sql = [] # parseしたsqlを入れて置くところ。
  end

  def parse(str)
    # 字句解析を行うところ。めっちゃ正規表現書くことになる。
    # インスタンス変数にトークンを入れていく。
    do_parse # do_parseで構文解析実行。
  end

  def next_token
    # do_parseがトークンを取り出す時に使う。
    @q.shift
  end

  def parsed_sql
    @parsed_sql
  end

  def format
    # sqlのフォーマットを行う。
  end
---- footer
```

このプログラムをRaccでコンパイルし、できた.rbファイルをrequireして使う、そんな流れになります。  

## 字句解析
構文解析を行うにはまず字句解析を行う必要があります。  
字句解析というのは、文字列である形式言語(プログラムなどの事。今回はSQLのクエリー)をトークンと呼ばれる最小単位に分ける作業です。
そのトークンの烈をもらった構文解析器がトークンを意味のあるプログラムにしてくれます。  

どこをトークン(最小単位)とするかは、どこまで切り分けたいかによるところですが、
今回は、

```
[[:SELECT, "select"], [:SELECT_LIST, "id, name"], [:FROM, "from"], [:FROM_CONDITION, "users"]]
```

こんな感じにできたら構文解析時に扱いやすそうなので、こういう風なデータを作ります。
配列のそれぞれの要素の第一引数にはトークンの名前、第二引数には元々の文字列を渡します。

以下のようになりました。  

```ruby
...

def parse(str)
  @q = []
  until str.empty?
    case str
    when /^\s+/
    when /^SELECT/i
      @q.push [:SELECT, $&]
    when /^\*|^.+(?=\s+FROM)/i
      @q.push [:SELECT_LIST, $&]
    when /^(FROM)(.+)/i
      @q.push [:FROM, $1]
      @q.push [:FROM_CONDITION, $2]
    end
    str = $'
  end
  @q.push [false, '$end']
  do_parse
end

def next_token
  @q.shift
end

...

```

このようにすると、@qに先ほどの形でデータが入ります。
そしてこの@qの要素を、next_token経由で構文解析が取り出すイメージです。
条件が増えるにつれてここの正規表現が増える感じになりそうです。
  

## 構文解析
次は字句解析の結果を受け取り、文として意味のあるものにする構文解析の部分を作ります。
記述する場所は、

```ruby
class MyParser
rule
  # 構文解析を行うところ。BNFで記述する。
end

...

```

ここです。
rule ... endの間にBNFの形式で書いていきます。  

以下のようになります。

```ruby
class SQLFormatter
rule
  query_expression: SELECT select_list table_expression {@parsed_sql.unshift [val[0], [val[1]]]}

  select_list: SELECT_LIST

  table_expression: from_clause

  from_clause: FROM FROM_CONDITION {@parsed_sql.push [val[0], [val[1]]]}
end

  ...
  
```

rule ... endの間がBNFの部分です。
:の後ろの部分には構文規則が入っており、大文字がトークンです。
先ほど字句解析で作ったデータの第一引数に対応しています。

query_expression: と from_clause: の後ろにある`{...}`がアクションと言われるやつで、
構文規則に当てはまったら`{...}`の中が動きます。  

valの中には、字句解析で作ったデータから、当てはまったトークンの第二引数が入ります。
つまり、`from_clause: FROM FROM_CONDITION`のアクションのval[0]には`from`が、val[1]には`users`が入っています。

このようにすると、`@parsed_sql`には、以下のようなデータが入ります。  

```
[["SELECT", ["id, name"]], ["FROM", [" users"]]]
```

## format
さて、最後に扱いやすくしたクエリーを、formatして出力します。  

```ruby

...

def parsed_sql
  @parsed_sql
end

def format(sql_arr=parsed_sql, i=0)
  sql_arr.each do |e|
    if e.is_a?(Array)
      format(e, i)
      i = 0
    else
      puts " " * i + e
      i += 2
    end
  end
end
---- footer
```

クエリーをツリーっぽくしておいたので、再帰がしやすいです。
ループさせ、要素が配列だったらformatに要素を入れ、
そうじゃなかったら出力させています。
iがインデント幅になります。

## コンパイル & 実行

さて、こうしてできたファイルを、Raccでコンパイルして、使ってみます。  

```rb:sql_formatter.y

class SQLFormatter
rule
  query_expression: SELECT select_list table_expression {@parsed_sql.unshift [val[0], [val[1]]]}

  select_list: SELECT_LIST

  table_expression: from_clause

  from_clause: FROM FROM_CONDITION {@parsed_sql.push [val[0], [val[1]]]}
end

---- inner

  def initialize
    @parsed_sql = []
  end

  def parse(str)
    @q = []
    until str.empty?
      case str
      when /^\s+/
      when /^SELECT/i
        @q.push [:SELECT, $&]
      when /^\*|^.+(?=\s+FROM)/i
        @q.push [:SELECT_LIST, $&]
      when /^(FROM)(.+)/i
        @q.push [:FROM, $1]
        @q.push [:FROM_CONDITION, $2]
      end
      str = $'
    end
    @q.push [false, '$end']
    do_parse
  end

  def next_token
    @q.shift
  end

  def parsed_sql
    @parsed_sql
  end

  def format(sql_arr=parsed_sql, i=0)
    sql_arr.each do |e|
      if e.is_a?(Array)
        format(e, i)
        i = 0
      else
        puts " " * i + e
        i += 2
      end
    end
  end
---- footer
```

```
$ racc sql_formatter.y
```

```ruby
require './sql_formatter.tab.rb'

parser = SQLFormatter.new
sql = 'select id, name from users'
parser.parse(sql)
parser.format

#=> select
#=>   id, name
#=> from
#=>    users

```

良さそうです。


## まとめ

今回は記事用に簡単なSQLに対応するように書きましたが、実際に使うとなるともっと複雑なSQLに対応しなければ使いものになりません。
現在実装中で、

これが、

```sql
select id, name from users where users.id = 1 and users.name = "littlekbt" order by id having users.id = 1 group by users.id ASC limit 1
```

こうなるところまではできました。

```sql
select
  id, name
from
  users
where
  users.id = 1 and users.name = "littlekbt"
order by
  id
having
  users.id = 1
group by
  users.id ASC
limit
  1
```

今後は、whereやhavingなどの条件部(search condition)をもっと細かくし、joinにも対応したいと思っています。
完成したらgemにしてActiveRecordのto_sqlの拡張として配布したいな、、、と思っております。

では、瑣末な内容でしたが、ありがとうございました。