複雑な正規表現はもう卒業!単純なパーサーに置き換える方法(Ruby実装例)

正直に告白します。私は正規表現を扱うのがあまり好きではありません。日常的によく使うものの、/^foo.*$/ より少しでも複雑になると、立ち止まって考えてしまうのです。\A(?=\w{6,10}\z)(?=[^a-z]*[a-z])(?=(?:[^A-Z]*[A-Z]){3}) のような式を一瞥で読み解ける人も確かにいるでしょうが、私の場合は何分も検索して調べる羽目になり、決して気分の良いものではありません。Ruby のコードを読むときとの大きな違いです。

ちなみに、上記の例は正規表現の先読み(lookahead)について解説した記事から引用したものです。

状況：検索クエリのトークン化

Honeybadger では現在、検索UIの改善に取り組んでいます。多くの検索システムと同様に、私たちのシステムでも簡易的なクエリ言語を採用しています。変更前は、カスタムの日付範囲で検索したい場合、次のようなクエリを手入力する必要がありました。

occurred:[2017-06-12T16:10:00Z TO 2017-06-12T17:10:00Z]

つらいですね!

新しい検索UIでは、日付に関連するクエリを入力し始めたタイミングを検出して、便利なデートピッカー(日付選択カレンダー)をポップアップ表示したいと考えています。もちろん、これはほんの始まりにすぎません。将来的には、文脈に応じたヒント表示を、より多くの種類の検索語へと拡張していく予定です。いくつか例を挙げます。

assigned:jane@email.com context.user.id=100
resolved:false ignored:false occurred:[
params.article.title:"Starr's parser post"       foo:'ba

これらの文字列をトークン化するには、次の条件を満たす必要があります。

• 空白文字でトークンを区切る。ただし '' 、"" 、[] で囲まれた部分は除く
• 引用符などで囲まれていない空白そのものも、1つのトークンとして扱う
• tokens.join("") を実行すると、元の入力文字列を完全に復元できる

たとえば、次のような結果になります。

tokenize(%[params.article.title:"Starr's parser post"       foo:'ba])
=> ["params.article.title:\"Starr's parser post\"", "       ", "foo:'ba"]

最初のアプローチ：正規表現を使う

最初に思いついたのは、キャプチャグループ付きの正規表現で「有効なトークン」の形を定義し、String#split を使って文字列を分割するという方法でした。実はかなりクールなテクニックです。

# 正規表現内の括弧(キャプチャグループ)により、区切り文字列も配列に含められる
"foo  bar  baz".split(/(foo|bar|baz)/)
=> ["", "foo", "  ", "bar", "  ", "baz"]

奇妙な空文字列は含まれるものの、当初は有望に見えました。ところが、実際の業務で必要になった正規表現は、はるかに複雑なものでした。最初のドラフトは次のとおりです。

/
  (                          # split がマッチ部分と非マッチ部分の両方を配列に含めるためのキャプチャグループ
    (?:                      # キーの最初の1文字。以下のいずれか
      (?!\s)[^:\s"'\[]{1}    # ..直前に空白がない有効な「キー」文字
      |^[^:\s"'\[]{0,1}      # ..または行頭にある有効な「キー」文字
    )
    [^:\s"'\[]*              # 残りの「キー」文字
    :                        # コロン
    (?:                      # 「値」の文字。以下のいずれか
      '[^']+'                # ..シングルクォートで囲まれた任意の文字列
      | "[^"]+"              # ..またはダブルクォートで囲まれた任意の文字列
      | \[\S+\sTO\s\S+\]     # ..または [x TO y] 形式の文字列
      | [^\s"'\[]+           # ..または空白・特殊文字を含まない任意の文字列
    )
  )
/xi 

これを触っているうちに、嫌な予感がしてきました。エッジケースを発見するたびに正規表現を修正する必要があり、それがさらなる複雑さを生んでいくのです。加えて、このコードは JavaScript でも動作させる必要があったため、否定後読み(negative lookbehind)のような一部の機能は利用できませんでした。

……そんなとき、ふとこの状況全体の馬鹿馬鹿しさに気づいたのです。私が採用していた正規表現によるアプローチは、ゼロからシンプルなパーサーを書くよりも、はるかに複雑だったのです。

パーサーの基本的な仕組み

専門家ではありませんが、シンプルなパーサーはシンプルです。やることは次の3つだけです。

• 文字列を1文字ずつ順番に読み進める
• 各文字をバッファに追加していく
• トークンを区切る条件に遭遇したら、バッファの中身を配列に保存して空にする

これがわかれば、空白で文字列を分割するシンプルなパーサーを作成できます。おおよそ "foo bar".split(/(\s+)/) と同等の動作です。

class Parser

  WHITESPACE = /\s/
  NON_WHITESPACE = /\S/

  def initialize
    @buffer = []
    @output = []
  end

  def parse(text) 
    text.each_char do |c|
      case c
      when WHITESPACE
        flush if previous.match(NON_WHITESPACE)
        @buffer << c
      else
        flush if previous.match(WHITESPACE)
        @buffer << c
      end
    end

    flush
    @output
  end

  protected

  def flush
    if @buffer.any?
      @output << @buffer.join("")
      @buffer = []
    end
  end

  def previous
    @buffer.last || ""
  end

end


puts Parser.new().parse("foo bar baz").inspect

# Outputs ["foo", " ", "bar", " ", "baz"]

目指す方向への一歩ですが、まだ引用符と角括弧には対応していません。幸い、そこを追加するために必要なのは、わずか数行のコードです。

  def parse(text) 

    surround = nil

    text.each_char do |c|
      case c
      when WHITESPACE
        flush if previous.match(NON_WHITESPACE) && !surround
        @buffer << c
      when '"', "'"
        @buffer << c
        if !surround
          surround = c
        elsif surround == c
          flush
          surround = nil
        end
      when "["
        @buffer << c
        surround = c if !surround
      when "]"
        @buffer << c
        if surround == "["
          flush
          surround = nil
        end
      else
        flush() if previous().match(WHITESPACE) && !surround
        @buffer << c
      end
    end

    flush
    @output
  end

このコードは正規表現ベースのアプローチよりわずかに長いだけであり、そのぶんはるかに素直で理解しやすいものになっています。

まとめ

おそらく、このユースケースにうまく適合する正規表現も、どこかにあるのでしょう。過去の経験から推測するに、「そんなにシンプルなら、自分が愚かに見えてしまう」と感じさせてくれるようなものかもしれません。:)

とはいえ、この小さなパーサーを書く機会は本当に楽しかったです。正規表現アプローチでの行き詰まりから抜け出せただけでなく、おまけとして、複雑な正規表現に依存したコードに比べて、でき上がったコードに対する自信が格段に高まりました。