エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

【Tech Talk 動画紹介】高度な正規表現は文字化けと区別がつかない件について

Tech-Talk

こんにちは、SREチームの山本です。

といいましても、今回はSRE的な話ではなくもう少し別の話をさせてください。

エムスリーにおいて隔週で行われている TechTalk という社内勉強会で発表させていただいた「高度な正規表現」についての話となります。

元動画は以下ですのでそちらも参考に願います。

www.youtube.com

みんな大好き「正規表現」

多くのエンジニアの方は「正規表現」に親しんでいることと思います。アレです。文字列をマッチングしたりその一部を切り出したりするために使われるものです。

ただ、我々が毎日遊んでいる間にも実は世の中は進んでおりまして、ツールによっては「回文」にマッチする正規表現や「式にマッチする正規表現」などという代物さえ存在します。

  • /^((.)\g<1>\k<2+0>|.?)$/ (回文マッチ：「しんぶんし」「たけやぶやけた」「こいけけいこ」)
  • /^(?<exp>\(\g<exp>[+\-*\/]\g<exp>\)|\d+)$/ (式にマッチ：((2-(12+(3*5)))/3) などのような優先順位を括弧でつけた加減乗除式)

そもそも「正規表現」とは？

正規表現(regular expression)とは、計算機科学の分野においては実は基本的なところである「形式言語」の理論に出てきます。 かつて、チョムスキー先生 *1という大変有名な学者の方がこの分野を開拓いたしました。実に第二次大戦後あたりの時期に開かれた話ですのでもはや70年以上前ということになります。

「言語」というのは、いわゆる自然言語もその1つですが、何らかの文字列の集まりとして定義されています。この考え方に基づけば、例えば正規表現 a+ というのは {"a", "aa", "aaa", "aaaa"...} という集合(言語)を意味するものとなります。そしてこの正規表現 a+ というものは特定の「文法」と呼ばれる規則を意味していると考えられています。

チョムスキー階層

ここではその形式文法について詳しく書くことは致しませんが、実のところその文法でどの程度の自由度を持たせるかというものが階層構造をなしているとされています。

  • 正規文法/正規言語/有限状態オートマトン
  • 文脈自由文法/文脈自由言語/プッシュダウンオートマトン
  • 文脈依存文法/文脈依存言語/線形拘束オートマトン
  • 無制限文法/帰納加算言語/チューリングマシン

上記の四種類が存在しており、一番上の正規文法/正規言語/有限状態オートマトンというのが、つまりは正規表現に対応いたします。そしてこれが一番きつい制約を持った文法であり、さらに自由な文法を許していくと下の文脈自由文法その他となります。

この階層構造をチョムスキー階層と呼びます。これは真面目な話「(その分野においては)テストに出る」ものです。

正規表現と回文・式

さて、話を元に戻したいと思います。 実は「回文」や「式」は正規文法では表せない典型例なのです。これは文脈自由文法を用いて表される階層にあります。

「正規表現では回文を表せませんが、正規表現で回文を表してみました！」というのはわけのわからないことを供述しているに等しいのです。

正規表現に対する拡張「部分式呼び出し(あるいは「田中哲スペシャル」)」

広く利用されている正規表現エンジンであるOnigurumaやその後登場したOnigmoにおいては、正規表現に対する画期的な拡張が施されています。これを「部分式呼び出し」あるいは「田中哲スペシャル」と呼びます。後者の名前は提案者からの命名です。特に最近導入された機能ではなく、10年以上前から使われています。 具体的にはこの正規表現エンジンはRubyやPHP(のマルチバイト版)などや各種エディタなどで採用されています。残念ながらJavaやPythonなどでは使うことができません。

部分式呼び出しの記法

次のような記法となります。

\g<名前>もしくは \g<数字>

この<名前>ですが、正規表現はその一部に名前をつけることが可能ですので、それがそのまま採用されます。名前をつけない場合は括弧で括るとその括弧の順番に数字が採番されます。 以下に例を出します。

  • 名前をつける
    • (?<url>(?<protocol>https?|ftp):\/\/(?<domain>[\w-]+(\.[\w-]+)+)\/) (https://example.com/ のようなものにマッチ)
    • この場合、全体にurlという名前を付与し、その一部にprotocolやdomainという名前を付与している
  • 数字の場合
    • (https?|ftp):\/\/([\w-]+(\.[\w-]+)+)\/
    • (https?|ftp)が 1番、([\w-]+(\.[\w-]+)+)が2番となる
    • 正規表現全体は自動的に括弧がなくとも0番に採番される

部分式呼び出しの使い方

使い方自体は簡単です。

上の例で言えば、(?<url>(?<protocol>https?|ftp):\/\/(?<domain>[\w-]+(\.[\w-]+)+)\/) のように名前をつけたならば (?<url>(?<protocol>https?|ftp):\/\/(?<domain>[\w-]+(\.[\w-]+)+)\/)\g<url> のように、\g<url> を使えばコピー&ペーストせずとも同じ正規表現を参照しますので、「URLがふたつ連続しているようなもの」を表せます。

ここで「回文正規表現」を再度振り返りましょう。

^((.)\g<1>\k<2+0>|.?)$

なるほど。わからん。

数字じゃなくて名前をつけて少しわかりやすくしてみます。

^(?:<kaibun>(?<char>.)\g<kaibun>\k<char+0>|.?)$

なるほど。わかりやすくなってはっきりしました! なんていう妄想はできませんね。やはりわからん。

定義の中で呼び出す

このわけのわからなさですが、それは kaibunの定義が (?<char>.)\g<kaibun>\k<char+0>|.?) である、つまりkaibunの定義に \g<kaibun> が入っているというのが一因と言えます。

そもそも回文ってどう定義されるのでしょうか？

BNF(バッカスナウア記法)

回文の定義は一般的には次のようなものです。

回文 ::= 文字X + 回文 + 文字X | 
         文字 |
         空文字列

このような定義はRFCなどでよく見られますが、BNFと呼ばれるものです。形式言語で言えば文脈自由文法を定義する際によく用いられます。

つまり回文とは以下の三種のどれかであるということです。

  • (Type A) ある文字Xがあって、回文が続いて、さらに文字Xが続く
  • (Type B) ある1文字
  • (Type C) 空文字列

Type Aを見ると、回文の定義に回文が含まれているわけでして、これが再帰的な定義です。

再度部分式呼び出しを凝視してみる

再度、回文正規表現にもどって、以下の文字化けを心の目で見つめてみましょう。

^(?:<kaibun>(?<char>.)\g<kaibun>\k<char+0>|.?)$

  • (?<char>.) = 1文字があって
  • \g<kaibun> = 回文が続いて
  • \k<char+0> = これはいわゆる後方参照(前方参照)であり、つまり(?<char>.) と同じ文字
  • | = あるいは
  • .? = 1文字もしくは0文字

上記の五箇所に分解されるということです。

動画で利用している資料より

回文 ::= 文字X + 回文 + 文字X | 
         文字 |
         空文字列

上記BNFと同じものを部分式呼び出しによって表現しているわけです。

\k<char+0>の +0のところが気になるかもしれませんが、部分式呼び出しにおいては複数の部分式が同時に実行されるためその階層を表現するために使います。ただし事実上 +0以外を使うことはないと思います。

もう1つの例(式)

^(?<exp>\(\g<exp>[+\-*\/]\g<exp>\)|\d+)$

これも文字化けにしか思えない文字の並びですが、オーラを自分の目に集めてしっかりと見てみましょう。「凝(ギョウ)」とか私は叫びながらいつも見ています。

すると見えないものが見えてきます。

  • \( 開き括弧があって
  • \g<exp> 式<exp>があって
  • [+\-*\/] + - * / のどれか一文字があって
  • \g<exp> 再度、式<exp>があって
  • \) 閉じ括弧がある
  • |\d+ もしくは単なる1文字以上の数字

これも、対応したBNFを書いてみてもいいかもしれません。

「文脈自由文法」を表す「正規表現」

部分式呼び出しという拡張は、BNF(文脈自由文法を表すもの)相当のものを「正規表現」に導入した代物であり、つまりすでに言語理論的には「正規表現」ではありません。 ただ、昔から「正規表現」に導入されている「後方参照」なども同じく既に言語理論的には正規表現を逸脱しておりますので、プログラミングツール的にはその手のこだわりを持つ意味はないかと思います。

このような拡張は実用的にどうなのかというのは私の中で15年ほどホットな話題なのですが、実のところ部分式呼び出しの使い手自体が世界的に枯渇しており、他のツールにimportされていないという現実からすれば「使うのが難しすぎて(そして読んでもらうのが難しすぎて)あまり普及していない」といったところじゃないかと感じます。

個人的には「ちょっとしたモノを表現するときにいちいちparserを呼び出さなくて済む」という利点はあると考えます。 しかし、そもそも本格的なものならばparserくらい呼び出せという話ですし、ちょっとしたモノ(ただし文脈自由文法相当)というのがそんなにあるわけではないので悪魔的な表現になるならば割に合わないということは言えそうです。 ただ、単純に「面白い」というエンジニア的な興味を持つ人はいるんじゃないかなと期待したいところです。

まとめ

  • 部分式呼び出しというヤヴァいやつがいる
    • 正規表現の一部に名前をつけて (?<名前>部分式)
    • それを呼び出す \g<名前> (あるいは数字での呼び出しも可)
    • Rubyなどで使える
  • 部分式呼び出しのヤヴァさは部分式定義の中で自分自身を呼び出す利用法
    • (?<釣り合った括弧>\(\g<釣り合った括弧>\)釣り合った括弧|)
  • 対応するBNFを作ってから書くのもアリ
    • 釣り合った括弧 ::= ( + 釣り合った括弧 + ) 釣り合った括弧 | 空文字列
  • 読みにくさ抜群なので実用性に乏しい説を唱える人も多い
  • 手軽に試したい人は以下を参照
    • echo "たけやぶやけた" | ruby -ne 'puts "kaibun!" if(/^((.)\g<1>\k<2+0>|.?)$/)'

We are hiring!

エムスリーでは、我々と一緒に働く仲間を大募集しております。 いきなり面談とまではいかなくとも、今回ご紹介したようなTech Talkは社外の方も参加できますので、是非雰囲気を確かめるだけでもご参加ください。以下のサイトからTech Talkへの参加も可能です！

jobs.m3.com

*1:昨今は計算機分野よりも政治関連で知名度が高くなっています。