Regexpの解析タイプ-3文法

Question

読書Chomsky hierarchy ... ... regexpは、タイプ2の文法（文脈自由文法）を解析できないこと、そしてタイプ-1とタイプ0も解析できないことを知っています。 正規表現はすべてのタイプ3文法（regular grammars）を解析/捕捉できますか？

Answer 1

はい、交替、連結、およびクレーネの星をサポートしています。 PCRE（Perl/Java/JavaScript/PHP/...）型の正規表現の場合は、((...)|(...))で置換を実装し、連結を(...)(...)で、クレーネの星を(...)*で実装します。 （これらの言語のほとんどに—がありますが、\Aと\zのようなものを使用して、 "start-of-string"と "end-of-string"を指定する必要があります。通常の文法では—それは考えです）。

しかし、プログラミングの文脈で "正規表現"と呼ばれるものは、必ずしも上記のものすべてを持っているわけではありません。 （たとえば、PCREに(a|b|c)と特殊ケースに相当する[abc]の両方があるのに対し、POSIX BREsは[abc]しか持たないのに対し、代替の1つの「分岐」はすべて単一の文字で構成されています。 (ab|c)のようなものは表現できません）。