regex - 正規表現解析タイプ 3 文法

Question

チョムスキー階層を読んでいます... ... 正規表現がタイプ 2 文法 (文脈自由文法) を解析できないことは知っています。また、タイプ 1 とタイプ 0 も解析できません。正規表現はすべてのタイプ 3 文法 (正規文法)を解析/キャッチできますか?

Answer 1

はい、代替、連結、および Kleene スターをサポートしている場合に限ります。((...)|(...))これは、PCRE (Perl/Java/JavaScript/PHP/...) タイプの正規表現に当てはまり(...)(...)ます(...)*。(他にもいくつかの詳細があります — これらの言語のほとんどでは、 「文字列の開始」と「文字列の終了」を示すために\Aandのようなものを使用する必要があり\zます。これは、通常の文法では当然のことと見なされます — しかし、それはアイデア。）

しかし、プログラミングのコンテキストで「正規表現」と呼ばれるすべてのものが、必ずしも上記のすべてを備えているわけではありません。たとえば、POSIX 基本正規表現は、非常に限られた形式の代替のみをサポートします。代替のすべての「分岐」は単一の文字で構成されます (たとえば、PCRE には(a|b|c)と special-case-equivalent の両方があるのに対し[abc]、POSIX BRE には しかありません[abc]。のような表現はできません(ab|c)）。