regex - BNF から正規表現へ

Question

言語をどのように説明できますか

A → AA | ( A ) | ε

正規表現を使用して生成しますか?

Answer 1

できません-正規表現は、可能な言語の小さなサブセットしか認識できません。特に、非公式に言えば、潜在的に認識するために無制限の量のメモリを必要とする言語は、RE 認識可能ではありません。

ここでは、右括弧の数が同じであることを確認するために、見た左括弧の数を記憶するための無制限の量のメモリが必要です。

一般に、BNF で記述された言語を認識できるようにするには、Context-Free Grammar を解析できる何らかのメカニズムが必要です。現代のパーサーはこれが得意です！

Answer 2

他の人が言ったように、単一の正規表現でこれを行うことはできませんが、2 つの「\(」と「\)」でトークン化できます。あなたの言語には角かっこしか入れられないことがわかりましたが、これが非常に役立つかどうかはわかりません。

注:ブラケットが正しくペアになっていることを確認するために通行人も必要です。したがって、「(()()」はトークン化されますが、解析されません。