Transact-SQL のLIKE句をPOSIX正規表現で表現する

## 概要

* SQL Server などで使用されているTransact-SQLのLIKE句をPOSIX正規表現に（ある程度）翻訳
* 有限オートマトンを使用して構文解析
* **完全に翻訳したわけではありません**

## 動機

::: note warn
これ以降、
POSIX正規表現のことを、**正規表現**と記述します。
Transact-SQLのことを、**SQL**と記述します。
他のSQL、正規表現文法だと異なる点があります。
:::

どこかの誰かが言いました（言ってない）。  
**SQLのLIKEで判断なんてダッセーよな！正規表現で対応しようぜ！**  

という話が出たので対応していきます。  
ところですごい車輪を再発明しているような感覚があるのですが、調べ方が悪かったのか実装例は見つかりませんでした。  
実装例を知っている方がいらっしゃいましたら、是非コメントで教えていただきたいです。

## Transact-SQLの特別な文字

対応すべき文字は以下の通りです。

| 文字 | 意味 | 正規表現 |
| --- | --- | --- |
| `%` | 任意長の文字 | `*.` |
| `_` | 任意の一文字 | `.` |
| `[(char[])]` | char[]のなかの一文字 | **`[(char[])]`** |

以上の文字を、正規表現に変換していきます。  
注意すべき点は、**`[]`の中に含まれる上記の文字は、`]`をのぞいてすべて文字リテラルとして扱う**という点です。  
例えば、SQLで`aaa[&%]bbb`と記述されるものを正規表現で表すと、`aaa[&*.]bbb`とは**ならず、`aaa[&%]bbb`となります**（つまり、`aaa&bbb`か`aaa%bbb`のどちらかがマッチします）。  
`]`は角括弧閉じの意味と解析されるので、`[]abc]`のように記述しても、意味的には`abc]`と等しくなり、「`]`か`a`か`b`か`c`のいずれか」という意味にはなりません。  

::: note warn
この問題を回避するためには、エスケープ指定が必要です。  
しかし、SQLの構文では、エスケープ文字の指定にESCAPE句が必要であり、LIKE句の文字列だけではどの文字がエスケープ文字なのかを指定できません。  
そのため、本変換機能では角括弧閉じ`]`は角括弧の中に入れることが出来ません。
:::

## 正規表現の特別な文字

正規表現で利用される文字のエスケープ処理を行う必要があります。  
これらの文字はSQLのLIKE句での比較では問題になりません。  
正規表現で意味を持ち、エスケープする必要のある文字は`\.^$|()[]{}+*?`ですが、`[]`**だけはSQLでも正規表現でも同じ意味**を持ちます。  
そのため、`[]`はエスケープする必要はありません。

## 変換処理

では、どのようにして変換処理を行えばよいでしょう？  
単純に置換するだけでは、`[%]`のような、置換しなくてもよい文字まで置換してしまいます。  

今回は、簡単な有限オートマトンを用いた構文解析を行うことにしました。  
状態遷移図は以下のようになります（ムーアモデルもどきです）。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2853945/768a3760-8486-9c95-cf7a-d02dd2bd886c.png)

### やってみる

実例を上げて変換を試してみましょう。  
まずは簡単な例から。  
`%Apple 100[%]%`という、とにかくリンゴが100%入っていればよいという内容を変換してみます。

変換は前の文字から順に行います。
|状態|変換前|変換処理|変換後|備考|
| --- | --- | --- | --- | --- |
|開始| `%Apple 100[%]%` | `開始/^` | `^` ||
|括弧外| `%Apple 100[%]%` | `%/.*` | `^.*` ||
|括弧外| `Apple 100[%]%` | `A/A` | `^.*A` ||
|括弧外| `pple 100[%]%` | `p/p` | `^.*Ap` ||
|括弧外| `ple 100[%]%` | `p/p` | `^.*App` ||
|括弧外| `le 100[%]%` | `l/l` | `^.*Appl` ||
|括弧外| `e 100[%]%` | `e 100/e 100` | `^.*Apple 100` |同様に...|
|括弧外| `[%]%` | `[/[` | `^.*Apple 100[` |ここで状態が遷移する|
|括弧内| `%]%` | `%/%` | `^.*Apple 100[%` |角括弧内状態|
|括弧内| `]%` | `]/]` | `^.*Apple 100[%]` |角括弧外に遷移する|
|括弧外| `%` | `%/.*` | `^.*Apple 100[%].*` ||
|括弧外|  | `文字列終わり/$` | `^.*Apple 100[%].*$` ||
|終了|  |  | `^.*Apple 100[%].*$` |正規表現が得られた|

このように、例に挙げたものは、`^.*Apple 100[%].*$`という正規表現で表せることが分かります。

次は、もう少し複雑な例で確認してみます。  
この例では、`[FLMNP]INE%App.%`という文を正規表現にしたいとします。

|状態|変換前|変換処理|変換後|備考|
| --- | --- | --- | --- | --- |
|開始|`[FLMNP]INE%App.%`|`開始/^`|`^`||
|括弧外|`[FLMNP]INE%App.%`|`[/[`|`^[`|角括弧内に遷移|
|括弧内|`LMNP]INE%App.%`|`LMNP/LMNP`|`^[FLMNP`|同様に...|
|括弧内|`]INE%App.%`|`]/]`|`^[FLMNP]`|角括弧外に遷移|
|括弧外|`INE%App.%`|`INE/INE`|`^[FLMNP]INE`||
|括弧外|`%App.%`|`%/.*`|`^[FLMNP]INE.*`||
|括弧外|`App.%`|`App/App`|`^[FLMNP]INE.*App`||
|括弧外|`.%`|`./\.`|`^[FLMNP]INE.*App\.`|`.`はエスケープ処理|
|括弧外|`%`|`%/.*`|`^[FLMNP]INE.*App\..*`||
|括弧外||`文字列終わり/$`|`^[FLMNP]INE.*App\..*$`||
|終了|||`^[FLMNP]INE.*App\..*$`|正規表現が得られた|

このように、正しい状態遷移図を書くことが出来れば、変換処理を再現することが出来そうだということが、お判りいただけたでしょうか？  
手作業で一文字ずつ変換していくわけには行きませんので、続きはコンピュータにやってもらいましょう。

### プログラム

と言っても、状態遷移図の通りに記述するだけです。  
現在の状態をもとに`switch`、入力された文字をもとに`switch`して、  
その状態遷移図に書かれている出力を行い、次の状態に変更するだけの簡単なプログラムです。

``` python:a.py
def convert_to_regex(sql: str) -> str:
  # 0は括弧閉じ　1は括弧開き
  state = 0
  meta = "\\.^$|(){}+*?"
  ret = "^"
  for c in sql:
    # python 3.10以降なら match を使ってもよいかも
    # 角括弧の外
    if state == 0:
      if c == "[":
        state = 1
        ret += "["
      elif c == "_":
        ret += "."
      elif c == "%":
        ret += ".*"
      elif c == "]":
        ret += "\\]"
      elif c in meta:
        ret += "\\" + c
      else:
        ret += c
    # 角括弧の中
    elif state == 1:
      if c == "[":
        ret += "\\["
      elif c == "]":
        state = 0
        ret += "]"
      elif c in meta:
        ret += "\\" + c
      else:
        ret += c
  # 角括弧が閉じられていない場合、構文エラー
  if state == 1:
    raise ValueError
  ret += "$"
  return ret
```

このプログラムを通すことで、SQLのLIKE句を正規表現に変換することが出来ました！

``` text
PS Microsoft.PowerShell.Core\FileSystem::hogehoge> python.exe a.py
%apple100[%]%
^.*apple100[%].*$
PS Microsoft.PowerShell.Core\FileSystem::hogehoge> python.exe a.py
[FLMNP]INE%App.%
^[FLMNP]INE.*App\..*$
```

## まとめ

~~**いかがでしたか？**~~  
構文解析を行う際に、状態遷移図を書き、オートマトンを作成することで分かりやすく実装できる、ということが伝われば幸いです。  
この状態遷移図は、ドキュメントとして残しておくことで、**構造の説明・理解も容易になるというメリット**もあります。  
視覚的に分かりやすいので、もし構文解析などの状態遷移図が必要になりそうな課題の場合、ドキュメントづくりも兼ねてサクッと作ってみてはいかがでしょう？

::: note
ありがとうオートマトンを教えてくれた教授。  
~~あの時何に使うんだとか思ってごめん。~~  
:::