言語の標準的な表現を持つと便利なことがよくあります (私の場合、それらは通常ドメイン固有の言語です)。ただし、関連する言語の表現力には厳密な制限があり、その言語の任意のプログラムに対して標準形式を決定および/または作成できるかどうかを決定するものだと思います。残念ながら、これについて読んだことを（漠然と）思い出した参考文献を見つけることができませんでした.
一方では、言語の正規表現を作成することは、多くのハード グラフの問題 (例: グラフ同形性) に匹敵する複雑さであると合理的に思われますが、他方では、iirc、gcc、yhc、および ghc などのコンパイラは中間表現を使用します。さまざまな形式（アセンブリ、JavaScriptなど）で出力を生成するため、これは少なくともいくつかの形式では解決済みの問題です。
特定の言語の正規形を決定/生成できるのはいつですか? (その言語はどの程度表現力があり、言語の表現力は正規形の有用性にどのように影響しますか?) 可能であれば、参照または証明を提供してください。
編集：たとえば、正規言語（例：正規表現の「純粋な」形式）は、チューリング完全言語が表現できるのと同じ多くのことを表現できません。つまり、通常の言語で Web サーバーを作成することはできませんが、ラムダ計算を使用すると作成できます)。私の質問は理論的な可能性に関するもので、複雑性理論に関連する具体的な答えがあります。別のシステムに送信する必要がある DSL がある場合、送信する前にそのコードの標準的な形式を生成すると、2 つの異なるシステムで使用される独立した表現が分離されるため、多くの場合有益です。 でも、それがP空間完全、またはチューリング完全言語を標準形式に変換するためのNP完全である場合、標準形式を構築しようとして時間を無駄にすべきではありません-それを行う別の方法を見つけるか、削減します多項式時間で正規化できる言語の複雑さ。