正規表現の真の力 (2012)

StackOverflowのPHPタグを頻繁に見ていると、正規表現を使ってHTMLの特定の側面を解析する方法についての質問を pretty 頻繁に見かけます。そのような質問に対する一般的な回答は次のとおりです。「HTMLは正規ではないため、正規表現でHTMLを解析することはできません。代わりにXMLパーサーを使用してください。」この声明は、質問の文脈では、非常に誤解を招くか、完全に間違っているかのどちらかです。 この記事で証明しようとしているのは、現代の正規表現が実際にどれほど強力であるかということです。 「正規」とは実際には何を意味するのか？ 形式言語理論の文脈では、すべての生成規則が次のいずれかの形式を持つ文法を持つ場合、あるものは「正規」と呼ばれます。 B -> a B -> aC B -> ε これらの -> ルールを「左辺は右辺に置き換えることができる」と読むことができます。したがって、最初のルールは「Bはaに置き換えることができる」、2番目のルールは「BはaCに置き換えることができる」、3番目のルールは「Bは空文字列に置き換えることができる」（εは空文字列の記号）となります。 B、C、aとは何でしょうか？慣例により、大文字は「非終端」と呼ばれる記号（さらに分解できるもの）を表し、小文字は「終端」と呼ばれる記号（それ以上分解できないもの）を表します。 すべてが抽象的に聞こえるかもしれませんが、例を見てみましょう。 自然数を文法として定義する。 N -> 0 N -> 1 ... N -> 9 N -> 0N N -> 1N ... N -> 9N この文法が言っていることは次のとおりです。 自然数（N）は... 0から9までのいずれかの数字、または... 0から9までのいずれかの数字の後に別の自然数（N）が続く この例では、0から9までの数字は終端（それ以上分解できないため）であり、Nは唯一の非終端（分解でき、さらに分解されるため）になります。 上記のルールをもう一度見て、正規文法の定義と比較すると、それらが基準を満たしていることがわかります。最初の10個のルールはB -> aの形式であり、次の10個のルールはB -> aCの形式に従っています。したがって、自然数を定義する文法は正規です。 また、上記の文法が非常に単純なものを定義しているにもかかわらず、すでにかなり冗長であることに気づくかもしれません。同じ概念をもっと簡潔に表現できれば、もっと良くないでしょうか？ そして、そこに正規表現が登場します。 上記の文法は、正規表現 [0-9]+ と同等です（これははるかに単純です）。そして、この種の変換は任意の正規文法で行うことができます。すべての正規文法には、有効な文字列を定義する対応する正規表現があります。 正規表現は何をマッチできるのか？ したがって、疑問が生じます。正規表現は正規文法のみをマッチできるのか、それともそれ以上もマッチできるのか？ 答えは「はい」と「いいえ」の両方です。形式文法の意味での正規表現は（定義により pretty much）正規文法のみを解析でき、それ以上はできません。しかし、プログラマーが「正規表現」について話すとき、彼らは形式文法について話しているのではありません。彼らは、自分の言語が実装している正規表現の派生について話しています。そして、それらの正規表現の実装は、元の正規性の概念とはほとんど関係がありません。現代の正規表現のどのフレーバーも、正規言語以上のものをマッチさせることができます。どのくらいかは、この記事の残りの部分で説明します。 話を簡単にするために、ここではPCRE正規表現の実装に焦点を当てます。これは私が最もよく知っている（PHPで使用されているため）からです。他のほとんどの正規表現の実装も pretty much 同様なので、ほとんどのことはそれらにも当てはまるはずです。 言語の階層 正規表現がマッチできるものとできないものを分析するために、まず他の種類の言語を見ていく必要があります。良い出発点はチョムスキー階層です。 チョムスキー階層: /------------------------------------------- | | | 再帰的可算言語 | Type 0 | | | /----------------------------------- | | | | | | 文脈依存言語 | | Type 1 | | | | /--------------------------- | | | | | | | 文脈自由言語 | | | Type 2 | | | | | | | | /------------------- | | | | | | | | | | | 正規言語 | | | | Type 3 | | | | | | | | | | | ご覧のとおり、チョムスキー階層は形式言語を4つのタイプに分類します。 正規言語（Type 3）は最も能力が低く、次に文脈自由言語（Type 2）、文脈依存言語（Type 1）、そして最後に全能の再帰的可算言語（Type 0）が続きます。 チョムスキー階層は包含階層であるため、上記の画像でより小さなボックスはより大きなボックスに完全に含まれています。たとえば、すべての正規言語は文脈自由言語でもあります（逆は当てはまりません）。 したがって、階層を一段階上に進みましょう。 正規表現は任意の正規言語をマッチできることはすでにわかっています。しかし、文脈自由言語もマッチできるでしょうか？（リマインダー: ここで「正規表現」と言うとき、私は明らかにプログラマーの意味で言っているのであり、形式言語理論の意味ではありません。） 文脈自由言語のマッチング 答えは「はい、できます！」です。たとえば、文脈自由言語の古典的な例である {a^n b^n, n>0}、「同じ数のa文字の後に同じ数のb文字が続く」を考えてみましょう。この言語の（PCRE）正規表現は次のとおりです。 /^(a(?1)?b)$/ 正規表現は非常にシンプルです。(?1)は最初のサブパターン、すなわち(a(?1)?b)への参照です。したがって、基本的に(?1)をそのサブパターンで置き換えることができ、再帰的な依存関係を形成します。 /^(a(?1)?b)$/ /^(a(a(?1)?b)?b)$/ /^(a(a(a(?1)?b)?b)?b)$/ /^(a(a(a(a(?1)?b)?b)?b)?b)$/ # など 上記の展開から、この式が同じ数のaとbを持つ任意の文字列をマッチできることは明らかでしょう。したがって、正規表現は少なくとも一部の非正規、文脈自由文法をマッチさせることができます。しかし、すべてをマッチさせることができるでしょうか？ それに答えるために、まず文脈自由文法がどのように定義されているかを見ていく必要があります。文脈自由文法では、すべての生成規則は次の形式を取ります。 A -> β ここでAは再び非終端記号であり、βは終端記号と非終端記号の任意の文字列です。したがって、文脈自由文法のすべての生成規則は、左辺に非終端記号、右辺に任意の記号文字列を持ちます。例として、次の文法を見てみましょう。 function_declaration -> T_FUNCTION is_ref T_STRING '(' parameter_list ')' '{' inner_statement_list '}' is_ref -> '&' is_ref is_ref -> ε parameter_list -> non_empty_parameter_list parameter_list -> ε non_empty_parameter_list -> parameter non_empty_parameter_list -> non_empty_parameter_list ',' parameter // ... // ... // ... ここで見ているのはPHP文法の抜粋です（いくつかのサンプルルールのみ）。構文は以前使用したものとは少し異なりますが、理解しやすいはずです。言及する価値のある側面は、ここでの大文字のT_SOMETHING名も終端記号であるということです。これらの記号は通常トークンと呼ばれ、より抽象的な概念をエンコードします。たとえば、T_FUNCTIONはfunctionキーワードを表し、T_STRINGはgetUserByIdやsome_other_nameのようなラベルトークンです。 私はこの例を使用して1つのことを示しています。文脈自由文法は、すでに pretty 複雑な言語をエンコードするのに十分な強力さを持っています。そのため、pretty ほぼすべてのプログラミング言語が文脈自由文法を持っています。特にこれには、整形式のHTMLも含まれます。 さて、実際の質問に戻りましょう。正規表現はすべての文脈自由文法をマッチさせることができるでしょうか？ ここでも、答えは「はい！」です。これは pretty 簡単な証明です。なぜなら、正規表現（少なくともPCREおよび類似のもの）は、文法を構築するための上記に非常に似た構文を提供しているからです。 / (?(DEFINE) (?<addr_spec> (?&local_part) @ (?&domain) ) (?<local_part> (?&dot_atom) | (?&quoted_string) | (?&obs_local_part) ) (?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) ) (?<domain_litera