正規表現の真の力 (2012)
The true power of regular expressions (2012) (npopov.com)
要約
この記事は、プログラマーが「正規表現」と呼ぶものが、形式言語理論における「正規言語」の定義をはるかに超えて、文脈自由言語など、より複雑な言語構造を処理できることを示しています。PCREなどの現代的な正規表現エンジンは、再帰的なパターンマッチングをサポートしており、これにより、プログラミング言語の構文解析など、本来正規言語ではないものを表現・マッチングすることが可能になります。
全文翻訳
正規表現の真の力
Stack Overflow の PHP タグ を頻繁に見ていると、正規表現を使って HTML の特定の側面を解析する方法についての質問がよく目に飛び込んできます。そのような質問に対する一般的な回答は以下の通りです。
HTML は正規ではないため、正規表現で解析することはできません。代わりに XML パーサーを使用してください。
この声明は、質問の文脈においては、非常に誤解を招くか、あるいはまったくの間違いと言えます。この記事では、最新の正規表現がどれほど強力であるかを実証しようと思います。
「正規」とは実際どういう意味か?
形式言語理論 の文脈では、「正規」とは、すべての生成規則が以下のいずれかの形式を持つ文法を持つものを指します。
B -> a
B -> aC
B -> ε
これらの -> の規則は「左辺は右辺に置き換えることができる」と読むことができます。したがって、最初の規則は「B は a に置き換えることができる」、2番目は「B は aC に置き換えることができる」、3番目は「B は空文字列に置き換えることができる」(ε は空文字列の記号)となります。
では、B、C、a とは何でしょうか? 慣例として、大文字は「さらに分解できる」可能性のある「非終端記号」を指し、小文字は「それ以上分解できない」「終端記号」を指します。
これらはおそらく少し抽象的に聞こえるでしょう。例として、自然数を文法として定義してみましょう。
N -> 0
N -> 1
N -> 2
N -> 3
N -> 4
N -> 5
N -> 6
N -> 7
N -> 8
N -> 9
N -> 0N
N -> 1N
N -> 2N
N -> 3N
N -> 4N
N -> 5N
N -> 6N
N -> 7N
N -> 8N
N -> 9N
この文法が言っていることは以下の通りです。
自然数 (N) は
... 0 から 9 までの数字のいずれか
または
... 0 から 9 までの数字のいずれかに、別の自然数 (N) が続くもの
この例では、数字の 0 から 9 は終端記号(それ以上分解できないため)であり、N は唯一の非終端記号(さらに分解できるため)となります。
上記の規則をもう一度見て、正規文法の定義と比較すると、基準を満たしていることがわかります。最初の 10 個の規則は B -> a の形式であり、2番目の 10 個の規則は B -> aC の形式に従っています。したがって、自然数を定義する文法は正規です。
また、上記の文法は非常に単純なものを定義しているにもかかわらず、すでにかなり冗長であることにも気づくかもしれません。同じ概念をより簡潔な方法で表現できれば、もっと良いのではないでしょうか?
そこで正規表現が登場します。上記の文法は正規表現 [0-9]+ に相当します(これははるかにシンプルです)。そして、この種の変換はあらゆる正規文法で行うことができます。すべての正規文法には、それに対応する正規表現があり、その有効な文字列すべてを定義します。
正規表現は何をマッチできるか?
そこで疑問が生じます。正規表現は正規文法しかマッチできないのか、それともそれ以上のものもマッチできるのか? 答えは「はい」でもあり「いいえ」でもあります。
形式文法の意味での正規表現は(定義によりほぼ)正規文法しか解析できず、それ以上のものはできません。
しかし、プログラマーが「正規表現」について話すとき、彼らは形式文法について話しているのではありません。彼らは、自分の言語が実装している正規表現の派生について話しています。そして、それらの正規表現の実装は、元の規則性の概念とはごくわずかしか関係がありません。
現代のどの正規表現フレーバーも、正規言語以上のものをたくさんマッチさせることができます。その正確な能力については、この記事の残りで説明します。
話を簡単にするために、ここでは PCRE 正規表現の実装に焦点を当てます。なぜなら、私がそれを最もよく知っており(PHP で使用されているため)、他の多くの正規表現実装も同様であるため、ほとんどのことがそれらに適用できるからです。
言語の階層
正規表現が何をマッチでき、何をマッチできないかを分析するために、まず他の種類の言語を見てみましょう。これの出発点として、チョムスキー階層 があります。
チョムスキー階層:
/------------------------------------------\
| |
| 再帰的可算言語 | Type 0
| |
| /-----------------------------------
| |
| | 文脈依存言語 | | Type 1
| |
| | /---------------------------
| | |
| | | 文脈自由言語 | | | Type 2
| | |
| | | /-------------------
| | | |
| | | | 正規言語 | | | Type 3
| | | \-------------------
| | \---------------------------
| \-----------------------------------
\-------------------------------------------
チョムスキー階層は、形式言語を 4 つのタイプに分類しています。
正規言語(タイプ 3)は最も能力が低く、次に文脈自由言語(タイプ 2)、文脈依存言語(タイプ 1)、そして最後に全能の再帰的可算言語(タイプ 0)が続きます。
チョムスキー階層は包含階層であるため、上記の画像で小さいボックスは大きいボックスに完全に含まれています。例えば、すべての正規言語は文脈自由言語でもあります(逆は真ではありません!)。
では、階層を一段階上に進みましょう。正規表現は正規言語をすべてマッチさせることができることはすでにわかっています。しかし、文脈自由言語もマッチできるのでしょうか?
(リマインダー:ここで「正規表現」と言うとき、私は明らかに形式言語理論の文脈ではなく、プログラマーの文脈で言っています。)
文脈自由言語のマッチング
これに対する答えははい、できます!
古典的な文脈自由言語の例として、{a^n b^n, n>0}、「n 個の 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 -> ε
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つのことを示します。文脈自由文法は、かなり複雑な言語をエンコードするのに十分な強力さを持っています。そのため、ほぼすべてのプログラミング言語は文脈自由文法を持っています。特に、これは整形式の HTML も含みます。
さて、実際の質問に戻りましょう。正規表現はすべての文脈自由文法をマッチさせることができますか? 再び、答えははいです!
これは証明するのが非常に簡単です。なぜなら、正規表現(少なくとも PCRE および類似のもの)は、文法を構築するための上記と非常に似た構文を提供しているからです。
/
(?(DEFINE)
(?<addr_spec> (?&local_part) @ (?&domain) )
(?<local_part> (?&dot_atom) | (?"ed_string) | (?&obs_local_part) )
(?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) )
(?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dtext) )* (?&FWS)? \] (?&CFWS)? )
(?<dtext> [\x21-\x5a] | [\x5e-\x7e] | (?&obs_dtext) )
(?<quoted_pair> \\ (?: (?&VCHAR) | (?&WSP) ) | (?&obs_qp) )
(?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)? )
(?<dot_atom_text> (?&atext) (?: \. (?&atext) )* )
(?<atext> [a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+ )
(?<atom> (?&CFWS)? (?&atext) (?&CFWS)? )
(?<word> (?&atom) | (?"ed_string) )
(?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? )
(?<qcontent> (?&qtext) | (?"ed_pair) )
(?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) )
# コメントと空白
(?<FWS> (?: (?&WSP)* \r\n )? (?&WSP)+ | (?&obs_FWS) )
(?<CFWS> (?: (?&FWS)? (?&comment) )+ (?&FWS)? | (?&FWS) )
(?<comment> \( (?: (?&FWS)? (?&ccontent) )* (?&FWS)? \) )
(?<ccontent> (?&ctext) | (?"ed_pair) | (?&comment) )
(?<ctext> [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&obs_ctext) )
# 旧形式トークン
(?<obs_domain> (?&atom) (?: \. (?&atom) )* )
(?<obs_local_part> (?&word) (?: \. (?&word) )* )
(?<obs_dtext> (?&obs_NO_WS_CTL) | (?"ed_pair) )
(?<obs_qp> \\ (?: \x00 | (?&obs_NO_WS_CTL) | \n | \r ) )
(?<obs_FWS> (?&WSP)+ (?: \r\n (?&WSP)+ )* )
(?<obs_ctext> (?&obs_NO_WS_CTL) )
(?<obs_qtext> (?&obs_NO_WS_CTL) )
(?<obs_NO_WS_CTL> [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f )
# 文字クラス定義
(?<VCHAR> [\x21-\x7E] )
(?<WSP> [ \t] )
)
^(?&addr_spec)$
/x
上記は RFC 5322 に準拠したメールアドレスの正規表現です。RFC の BNF 規則を PCRE が理解できる表記法に変換するだけで構築されました。
構文は非常にシンプルです。
すべての規則定義は DEFINE アサーションで囲まれています。これは、これらの規則が直接マッチされるのではなく、定義されるだけであることを意味します。最後に ^(?&addr_spec)$ の部分だけが、何をマッチさせるかを指定します。
規則定義は実際には「規則」ではなく、名前付きサブパターンです。以前の (a(?1)?b) の例では、1 は最初のサブパターンを参照していました。多くのサブパターンがある場合、これは明らかに非現実的なので、名前を付けることができます。したがって (?<xyz> ...) は xyz という名前のパターンを定義します。(?&xyz) はそれを参照します。
また、別の事実に注意してください。上記の正規表現は x 修飾子を使用しています。これは、エンジンに空白を無視させ、# スタイルのコメントを許可するように指示します。これにより、正規表現をきれいにフォーマットして、他の人が実際に理解できるようにすることができます。(この RFC 822 メールアドレス正規表現とは対照的に…)
上記の構文は、文法から正規表現への簡単なマッピングを可能にします。
A -> B C
A -> C D
// は次のように変換されます
(?<A> (?&B) (?&C)
| (?&C) (?&D)
)
唯一の注意点は、正規表現は左再帰をサポートしていないことです。例えば、上記のパラメータリストの定義を見てみましょう。
non_empty_parameter_list -> parameter
non_empty_parameter_list -> non_empty_parameter_list ',' parameter
これを文法ベースの正規表現に直接変換することはできません。以下は機能しません。
(?<non_empty_parameter_list>
(?¶meter)
| (?&non_empty_parameter_list) , (?¶meter)
)
理由はこの non_empty_parameter_list が、その規則定義の最も左の部分として現れることです。これは左再帰と呼ばれ、文法定義では非常に一般的です。その理由は、通常それらを解析するために使用される LALR(1) パーサーが、右再帰よりも左再帰をはるかにうまく処理するためです。
しかし、心配しないでください。これは正規表現の能力にはまったく影響しません。すべての左再帰文法は右再帰文法に変換できます。上記の例では、2 つの部分を入れ替えるだけで簡単です。
non_empty_parameter_list -> parameter
non_empty_parameter_list -> parameter ',' non_empty_parameter_list
これで、正規表現は任意の文脈自由言語(したがって、プログラマーが直面するほぼすべての言語)をマッチさせることができるはずです。唯一の問題は、正規表現は文脈自由言語をマッチさせることはできても、通常は解析できないということです。解析とは、文字列を抽象構文木に変換することです。これは正規表現では不可能です。少なくとも PCRE では(Perl では正規表現に任意のコードを埋め込むことができるので、ほとんど何でもできます…)。
それでも、上記の DEFINE ベースの正規表現定義は私にとって非常に役立つことが証明されています。通常、完全な解析サポートは必要ありませんが、マッチさせたい(例:メールアドレス)か、小さなデータ片を抽出したい(解析ツリー全体ではない)だけです。ほとんどの複雑な文字列処理の問題は、文法ベースの正規表現を使用することで大幅に簡素化できます。
ここで、すでに少し触れたことをもう一度指摘させてください。整形式の HTML は文脈自由です。したがって、一般的な意見に反して、正規表現を使用してそれをマッチさせることができます。しかし、2つのことを忘れないでください。第一に、実際のほとんどの HTML は整形式ではありません(通常はそれに近いものでさえありません)。そして第二に、できるからといってすべきというわけではありません。Brainfuck でソフトウェアを書くこともできますが、なぜかそうしません。
このトピックに関する私の意見は次のとおりです。汎用的な HTML 処理が必要な場合は、好みの DOM ライブラリを使用してください。それは不正な形式の HTML をうまく処理し、解析の負担を軽減してくれます。一方、特定の状況に対処する場合は、簡単な正規表現がしばしば最善の方法です。そして認めなければなりませんが、HTML を正規表現で解析しないように人々に言うことが多いにもかかわらず、私はそれを非常に頻繁に行っています。単純に、ほとんどの場合、正規表現の使用がより簡単な特定の限定された状況に対処しているからです。
文脈依存言語
文脈自由言語について広範囲に説明したので、チョムスキー階層を一段階上に進みましょう。文脈依存言語です。
文脈依存言語では、すべての生成規則は次の形式を取ります。
αAβ → αγβ
これらの文字の組み合わせはより複雑に見えるかもしれませんが、実際には非常にシンプルです。その核心では、文脈自由言語を定義した A → γ というパターンがまだあります。新しいのは、両辺に α と β が追加されていることです。これら 2 つは文脈を形成します(これがこの文法クラスに名前を与えている理由でもあります)。したがって、基本的に A は、左側に α、右側に β がある場合にのみ γ に置き換えることができます。
これをより明確にするために、以下の規則を解釈してみてください。
a b A -> a b c
a B c -> a Q H c
H B -> H C
英語の翻訳は次のようになります。
`A` を `c` に置き換えるが、その左側に `a b` がある場合に限る。
`B` を `Q H` に置き換えるが、その左側に `a`、右側に `c` がある場合に限る。
`B` を `C` に置き換えるが、その左側に `H` がある場合に限る。
文脈依存言語は、「通常の」プログラミングではめったに遭遇しないものです。それらは主に自然言語処理の文脈で重要です(自然言語は明らかに文脈自由ではありません。単語の意味は文脈によって異なります)。しかし、自然言語処理でさえ、人々は通常「穏やかに文脈依存な言語」と呼ばれるものを扱います。なぜなら、それらは言語のモデリングに十分でありながら、はるかに高速に解析できるからです。
文脈依存言語がいかに強力であるかを理解するために、文脈依存言語と全く同じ表現力を持つ別の文法クラスを見てみましょう。非収縮文法です。
非収縮文法では、すべての生成規則は α -> β の形式を取り、α と β は、右辺の記号数が左辺の記号数以下でないという 1 つの制限のみを持つ任意の記号文字列です。形式的には、これは |α| <= |β| という式で表されます。ここで |x| は記号文字列の長さを表します。
したがって、非収縮文法は、入力を短縮しない限り、あらゆる形式の規則を許可します。例えば、A B C -> H Q は無効な規則です。なぜなら、左辺は 3 つの記号を持ち、右辺は 2 つしか持たないからです。したがって、この規則は短縮(または「収縮」)となります。一方、逆の規則 H Q -> A B C は有効です。なぜなら、右辺は左辺よりも多くの記号を持つため、伸長となるからです。
文脈依存言語と非収縮言語のこの同等関係は、文脈依存文法でほぼすべてをマッチさせることができることを明確にするはずです。短縮しないように!
両方の文法種類が同じ表現力を持つ理由の印象を得るために、以下の変換例を見てみましょう。
// 非収縮文法
A B -> C D
// は以下の文脈依存文法に変換できます
A B -> A X
A X -> Y X
Y X -> Y D
Y D -> C D
とにかく、正規表現に戻りましょう。それらは文脈依存言語もマッチさせることができるのでしょうか?
今回は明確な答えを提供できません。確かに一部の文脈依存言語をマッチさせることができますが、すべてをマッチさせることができるかどうかはわかりません。
正規表現で簡単にマッチさせることができる文脈依存言語の例は、前述の文脈自由言語 {a^n b^n, n>0} の変更版です。それを {a^n b^n c^n, n>0}、つまり、ある数の a の後に同じ数の b と c が続く言語に変更すると、文脈依存になります。
この言語の PCRE 正規表現は次のとおりです。
/^
(?=(a(?-1)?b)c)
a+(b(?-1)?c)
$/x
現時点では (?=...) アサーションを無視すると、a+(b(?-1)?c) が残ります。これは、任意の数の a の後に、同じ数の b と c が続くことを確認します。(?-1) は相対サブパターン参照であり、「最後に定義されたサブパターン」を意味します。この場合、それは (b(?-1)?c) です。
ここで新しいのは (?=...) です。これはゼロ幅先読みアサーションと呼ばれるものです。これは、後続のテキストがパターンにマッチすることを確認しますが、実際にはテキストを消費しません。したがって、テキストは実質的に両方のパターンに対して同時にチェックされます。a+(b(?-1)?c) の部分は b と c の数が同じであることを検証し、(a(?-1)?b)c の部分は a と b の数が同じであることを確認します。両方のパターンを組み合わせることで、3 つの文字すべてが同じ数であることが保証されます。
上記の正規表現では、「文脈」という概念が正規表現でどのように実現されているかがすでにわかります。アサーションを使用しています。文脈依存文法の定義に戻ると、次のような形式の生成規則は次のように言うことができます。
αAβ → αγβ
これは次の正規表現 DEFINE 規則に変換できます。
(?<A> (?<= α ) γ (?= β ) )
これは、A は γ であるが、その左側に α、右側に β がある場合に限ると言うことになります。
さて、上記は文脈依存文法を正規表現に簡単に変換できるかのように見えるかもしれませんが、実際にはそうではありません。その理由は、後読みアサーション ((?<= ... )) には 1 つの非常に重要な制限があるためです。それは固定幅でなければならないということです。つまり、アサーションがマッチさせるテキストの長さは事前に知られている必要があります。例えば、(?<= a(bc|cd) ) と書くことはできますが、(?<= ab+) と書くことはできません。最初のケースでは、アサーションはいずれの場合も正確に 3 文字をマッチさせるため、固定幅です。一方、2 番目のケースでは、アサーションは ab、abb、abbb などをマッチさせる可能性があります。これらはすべて長さが異なります。したがって、エンジンはいつマッチを開始すべきかを知ることができず、単純に許可されません。
これは、文脈依存文法から正規表現への直接的な変換をほぼすべて台無しにします。そのような文法のほとんどすべては、可変幅の後読みアサーションを必要とします。
しかし、文脈依存文法から正規表現への直接的な変換がないという事実だけでは、正規表現がそれらすべてをマッチさせることができないという意味ではありません。例えば、上記の {a^n b^n c^n, n>0} 言語も、可変幅の後読みアサーションを必要とする文法を持っています。しかし、正規表現は文法で規則を指定することに縛られていないため、それらを使用しないように回避できます。おそらく、他のすべての文脈依存文法でも同じことが可能かもしれません。正直なところ、わかりません。
では、ここで何を言えるでしょうか? 正規表現は少なくとも一部の文脈依存言語をマッチさせることができますが、すべてをマッチさせることができるかどうかは不明です。
無制限文法
チョムスキー階層の次の文法クラスは、無制限文法です。それらを使用して形成できる言語のセットは、すべての再帰的可算言語のセットです。
無制限文法については、ほとんど言うことはありません。なぜなら、それらは文字通り無制限だからです。無制限文法の生成規則は α -> β の形式を取り、α と β は一切の制限のない記号文字列です。
したがって、基本的に無制限文法は、非収縮文法の「非収縮」部分を削除します。したがって、それらに対しては A B C -> H Q は有効な規則になりますが、以前はそうではありませんでした。
無制限文法は正確にどれほど強力でしょうか? それらは可能な限り強力です。それらはチューリング完全です。無制限文法に基づいた「プログラミング言語」さえ存在します。Thue です。チューリング完全であるため、他の言語ができることはすべて実行できます。
チューリング完全であることの 1 つの含意は、特定の文字列がある文法に準拠しているかどうかをチェックすることが、一般的なケースでは決定不能であるということです。
残念ながら、正規表現と無制限文法の関係については何も言うことができません。そもそも、意味のある無制限文法の例(非収縮でないもの)さえ見つけられませんでした。
しかし、チューリング完全性について話し始めたところで、別の点に移りましょう。
バックリファレンスを持つ正規表現は NP 完全である
以前言及しなかった、非常に強力な正規表現の機能がもう 1 つあります。バックリファレンスです。
例えば、この非常に単純な正規表現を考えてみましょう。
/^(.+)\1$/
(.+) は任意のテキストをマッチさせ、\1 は同じテキストをマッチさせます。一般に \n は「n 番目のサブパターンがマッチしたものを何でも」という意味です。例えば、(.+) が foo をマッチさせた場合、\1 も foo だけをマッチさせ、それ以外はマッチさせません。したがって、式 (.+)\1 は「あるテキストの後にそのコピーが続く」という意味になります。
この単純な正規表現がマッチするものは「コピー言語」と呼ばれ、文脈依存言語の典型的な例です。
同様に、バックリファレンスを使用して上記の他の例の文法をマッチさせることができます。
# {a^n b^n, n>0} (文脈自由)
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
# {a^n b^n c^n, n>0} (文脈依存)
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x
これらがどのように機能するかを説明することは、この記事の範囲外ですが、StackOverflow で優れた説明を読むことができます。
ご覧のとおり、サブパターン再帰サポートなしのバックリファレンスという単純な追加機能でさえ、正規表現に多くの強力さを加えています。この追加機能は実際には非常に強力であり、正規表現のマッチングを NP 完全問題にしています。
NP 完全とはどういう意味でしょうか? NP 完全は、多くの「難しい」問題が含まれる、決定問題の計算複雑性クラスです。NP 完全問題の例としては、巡回セールスマン問題(TSP)、ブール充足可能性問題(SAT)、ナップサック問題(BKP)などがあります。
問題が NP 完全であるための主な条件の 1 つは、他のすべての NP 問題がそれに還元可能であることです。したがって、すべての NP 完全問題は基本的に相互に交換可能です。それらの 1 つに高速な解法を見つけた場合、すべての問題に高速な解法を見つけたことになります。
したがって、誰かが NP 完全問題の高速な解法を見つけた場合、人類の計算上難しい問題のほぼすべてが一挙に解決されることになります。これは文明の終焉を意味するでしょう。
バックリファレンスを持つ正規表現が実際に NP 完全であることを証明するために、既知の NP 完全問題の 1 つを取り上げ、それが正規表現を使用して解決できることを証明できます。例として、3-CNF SAT 問題を選択します。
3-CNF SAT は「3-連鎖正規形ブール充足可能性問題」の略で、理解は非常に簡単です。次のような形式のブール式が与えられます。
(!$a || $b || $d)
&& ( $a || !$c || $d)
&& ( $a || !$b || !$d)
&& ( $b || !$c || !$d)
&& (!$a || $c || !$d)
&& ( $a || $b || $c)
&& (!$a || !$b || !$c)
したがって、ブール式は AND で区切られた多数の節で構成されます。これらの各節は、OR で区切られた 3 つの変数(またはその否定)で構成されます。3-CNF SAT 問題は、与えられたブール式に解が存在するかどうか(それが真になるように)を問います。
上記のブール式は、次の正規表現に変換できます。
$regex = '/^
(x?)(x?)(x?)(x?) .* ;
(?: x\1 | \2 | \4 ),
(?: \1 | x\3 | \4 ),
(?: \1 | x\2 | x\4 ),
(?: \2 | x\3 | x\4 ),
(?: x\1 | \3 | x\4 ),
(?: \1 | \2 | \3 ),
(?: x\1 | x\2 | x\3 ),
$/x';
$string = 'xxxx;x,x,x,x,x,x,x,';
var_dump(preg_match($regex, $string, $matches));
var_dump($matches);
このコードを実行すると、次の $matches 結果が得られます。
array(5) {
[0]=> string(19) "xxxx;x,x,x,x,x,x,x,"
[1]=> string(1) "x"
[2]=> string(1) "x"
[3]=> string(0) ""
[4]=> string(0) ""
}
これは、上記の式が $a = true、$b = true、$c = false、$d = false の場合に満足されることを意味します。
正規表現は非常に単純なトリックで機能します。各 3-節に対して、文字列にはマッチする必要がある x, が含まれています。したがって、(?: \1 | x\3 | \4 ), のようなものがある場合、文字列は \1 が x(真)、\3 が空文字列(偽)、または \4 が x(真)のいずれかである場合にのみマッチさせることができます。
残りはエンジンに任されます。エンジンは、解を見つけるか、ギブアップしなければならないまで、さまざまな方法で文字列のマッチングを試みます。
まとめ
記事はかなり長かったので、主なポイントの要約を以下に示します。
- プログラマーが使用する「正規表現」は、形式言語理論の文脈における規則性の元の概念とはほとんど関係がありません。
- 正規表現(少なくとも PCRE)は、すべての文脈自由言語をマッチさせることができます。したがって、整形式の HTML や、ほぼすべての他のプログラミング言語もマッチさせることができます。
- 正規表現は、少なくとも一部の文脈依存言語をマッチさせることができます。
- 正規表現のマッチングは NP 完全です。したがって、正規表現を使用して他の NP 問題をすべて解決できます。
しかし、忘れないでください。できるからといって、すべきというわけではありません。正規表現で HTML を処理することは、場合によっては本当に悪い考えです。他の場合では、おそらく最善のことでしょう。
あなたの特定の С にとって最も簡単な解決策を確認し、それを使用してください。正規表現を使用して С を解決することを選択した場合、正規表現をきれいにフォーマットできる x 修飾子を忘れないでください。複雑な正規表現の場合は、コードをクリーンで読みやすく保つために、DEFINE アサーションと名前付きサブパターンを活用することも忘れないでください。
以上です。