正規表現をチョムスキー言語学まで遡って理解する(翻訳)

概要 原著者の許諾を得て翻訳・公開いたします。 英語記事: Exploring the Linguistics Behind Regular Expressions 原文公開日: 2017/11/20 著者: Alaina Kafkes 訳注: 原文タイトルは「正規表現を背後で支える言語学を理解する」といったニュアンスです。翻訳記事タイトルでは内容を把握しやすくするため「チョムスキー」を加えました。 正規表現をチョムスキー言語学まで遡って理解する(翻訳) 正規表現は、新人/ベテランを問わずプログラマーに恐怖心を呼び起こします。私が最初に正規表現(しばしばregexと略記されます)というものを目にしたときも、()だの*だの文字だの数字だので構成された祈祷書を読んでいるうちにめまいがしてきたのを覚えています。正規表現はナンセンスで理解不能なものに思えたのです。 正規表現は、高度なコンピュータサイエンス(CS)学科で扱われるのだろうと思っていました。それならば正規表現に取り組む気になったことでしょう。しかし私が正規表現に出会ったのは、学部4年になるまで先延ばしにしていた入門クラスだったのです。このコースの目的は、暗号学/人間とコンピュータのインタラクション/機械学習の概念を紹介することで、コードを1行も書いたことがない学生をCSに引きずり込むことでした。ところで機械学習はこの中で唯一の最新かつ最大の技術系バズワードですね。 レクチャーには数回ぐらいしか出席していませんでしたが、その中で出された課題の1つで私は頭を抱えてしまいました。CSに影響を与えたコンピュータサイエンティストか学者についてエッセイを1本書かなければならなかったのです。そのときはノーム・チョムスキーを選択しました。 そのときは知る由もありませんでしたが、チョムスキーについて学ぶうちに私は正規表現というウサギの穴に再び引きずり込まれ、いつしか正規表現が魔法のごとく別の何かに姿を変える様子にすっかり魅了されてしまいました。私が正規表現で夢中になったのは、正規表現のパワーの源たる、同じ名前の言語的なコンセプトの方でした。 正規表現を背後で支える言語学、すなわちほとんどのプログラマーに知られていない背景を知ることで、皆さまも正規表現を好きになっていただければと思います。ここでは特定のプログラミング言語での正規表現の使い方を解説するつもりはありませんが、言語としての正規表現をご紹介することで、皆さまが選んだプログラミング言語で正規表現がどのように機能しているのかを深く追求するきっかけになれば幸いです。 まずはチョムスキーに話を戻しましょう。チョムスキーのどのあたりが正規表現に関係あるのでしょうか?そもそもチョムスキーがCSと何の関係があるのでしょうか? なりゆきコンピュータサイエンティスト Wikipediaにはノーム・チョムスキーは言語学者、哲学者、認知科学者、歴史家、社会批評家、政治活動家と記載されていますが、コンピュータサイエンティストとは書かれていません。チョムスキーはそれらのすべての分野で重要な業績を残しているため、CSへの間接的な貢献は見落とされがちです。 チョムスキーの学術上の業績を調べるうちに、チョムスキーのコンピューティングへの興味が偶然であったという思いが強くなりました。このことから、チョムスキーの業績は一見CSとは無関係に見えたとしても、分野を問わずコンピューティングやIT業界に何かしら寄与しているという私の信念が裏付けられました。 とりわけチョムスキーによる言語学方面の功績は、CSの学際的な研究が与えたインパクトの好例です。チョムスキー階層は、コンピュータサイエンティスト/ソフトウェアエンジニア/ホビイストが日常的に書いているコードに転換されました。 そう、CSに正規表現なるものをもたらしたのは、この階層という概念だったのです。しかしチョムスキーから正規表現への飛躍を理解する前に、チョムスキー階層の概要について説明します。 言語の規則と秩序 チョムスキー階層とは、形式文法の秩序化です。それぞれの文法が、階層上で上位の文法の真部分集合となるような、形式言語の統語論的(syntactic)な規則を考えてみましょう。ある形式言語の文法は他のものよりも厳密であることから、チョムスキーは形式言語を彼の名を冠した階層に編成することを追求しました。 先ほど、形式文法は統語論的な規則であるということについて簡単に触れました。この規則は、与えられた形式言語で有効なあらゆる句(phrase)を与えます。文法は、言語を作り上げる規則を提供します。言語学者の言い方を借りれば、ある言語の形式文法は、非終端(nonterminal: 入力または中間文字列値)を終端(terminal: 出力文字列値)に変換できるフレームワークを提供します。 この目新しい語彙を解明するために、既成の形式文法を用いて非終端の集合を終端に変換する例を1つお目にかけましょう。なんちゃって形式言語「Parseltongue」(訳注: ハリー・ポッターシリーズの「蛇語」のこと)には次の形式文法があるとします。 終端: {s, sh, ss} 非終端: {snake, I, am} 生成規則: {I → sh, am → s, snake → ss} この生成規則を使って、「I am … Continue reading 正規表現をチョムスキー言語学まで遡って理解する(翻訳)