构建规范语言表示的一般复杂性是什么？

Question

通常方便地使用一种语言的规范表示(在我的例子中，它们通常是特定于域的语言)；然而，我认为所涉及的语言的表现力有严格的限制，这些语言决定了是否可以确定和/或为使用该语言的任意程序创建规范形式。不幸的是，我一直找不到我(隐约)读到的有关这方面的参考资料。

一方面，创建语言的规范表示似乎与许多硬图问题(例如:图同构)相当复杂，但另一方面，iirc、像gcc、yhc和ghc这样的编译器使用中间表示来生成各种格式的输出(程序集、javascript等)，因此这至少在某些形式上是一个解决问题。

何时可以确定/生成给定语言的规范形式？(这种语言的表达能力如何，以及语言表达能力如何影响规范形式的效用？)如有可能，请提供参考资料或证明。

编辑:例如，一个正规语言 (例如:正则表达式的“纯”形式)不能表达与图灵全语言相同的许多东西。换句话说，您不能用常规语言编写web服务器，但是可以使用lambda演算编写)。我的问题是关于理论可能性的，并且有一个关于复杂性理论的具体答案。如果我有一个DSL需要传输到另一个系统，那么在发送之前生成该代码的规范形式通常是有益的，因为这将使两个不同系统使用的独立表示解耦。然而，如果是P-空间完全，或者是NP-完成将图灵-完全语言翻译成规范形式，那么你就不应该浪费时间试图构建一个规范形式--或者找到另一种方法，或者将语言复杂性降低到可以在多项式时间内规范化的东西。

Answer 1

在我看来，编译成汇编语言可以归类为翻译成规范的形式，以一种实际的方式。