computer-science - 形式文法可以生成其他文法吗？

Question

我在一个计算类的模型中，我们只是在讨论形式语法。正如我们所定义的，形式文法是：

• 一些终端符号
• 一些非终结符号
• 一个开始符号
• 一些生产规则

鉴于文法生成字符串，您似乎可以选择一种文法来生成另一种文法。几分钟的搜索似乎并没有在这个领域产生太多的讨论。我的问题主要是：

• 这是计算机科学中一个有趣的问题吗？
• 您可以通过生成生成它们的语法来压缩语法，还是复杂性不可减少？

Answer 1

有许多形式主义——例如 BNF 表示法——描述语法并且它们本身可以由上下文无关语法中的字符串表示。

但我不确定这就是你要找的。（通常）不存在表示单个字符串的语法；相反，语法描述了一组（通常是无限的）字符串，没有赋予任何语义。

“命名”的本质意味着像 BNF（或任何编程语言）这样的形式主义的语义不能用上下文无关的语法来捕获。将字符串中的“名称”与其他出现的相同“名称”相关联是典型的上下文相关的。

因此，有一个 CFL 是所有语法（具有给定字母表）的表示集，但这些表示中的绝大多数不对应于有用的甚至有意义的语法。在典型的派生字符串中，产生式右侧的符号实际上不会出现在任何规则的左侧，并且不能在 CFG 中表达它们的要求。

Answer 2

生成另一种语法的语法的问题很有趣，它有一个名称和一些文献——请参阅https://en.wikipedia.org/wiki/Two-level_grammar和那里的链接。

是的，您当然可以实现压缩，因为生成的语法可能实际上是无限的。