给定一种定义为的语言：
任何一对匹配的符号都是有效的字符串。
例如
00,55,YY
还有一大堆非终结符号（比如说4,294,967,296它们）......
您将如何定义 BNF 语法来表达该语言？（上下文相关或其他。）
我特别有兴趣了解是否有一种方法可以在不编写4,294,967,296规则的情况下做到这一点：即一个如此庞大的语法，它失去了用 BNF 定义的所有好处，因为它已成为一组“蛮力”有效文字。
问问题
170 次
1 回答
2
BNF 的大多数用途是描述上下文无关文法。
您当然可以将 BNF 表示法用于非上下文无关文法；您需要做的就是在左侧放置多个终端。然而，这在实践中通常不是很有用，因为非上下文无关文法不提供对所解析语言结构的直观描述，也不会导致解析语言的算法。人们会期望任何实用的语法形式主义要么给人类读者一个很好的描述，要么允许自动生成解析器，或者两者兼而有之。（这不会使非上下文无关文法在语言的形式分析中无用；在数学理论中，没有必要取悦读者或解析器生成器。）
但是如果我们限制自己使用上下文无关文法，我们会立即遇到障碍，因为上下文无关文法不能表达重复，例如 { ωω | ω∈Σ<sup>* }。根据定义，复制几乎不是上下文无关的，因为上下文无关意味着非终结符的扩展不能依赖于非终结符出现的上下文。因此，表达重复所需的“这个非终结符必须与那个非终结符具有相同的扩展”的规则不能是上下文无关的。
当然，语言{ ωω | ω∈Σ }，这就是你要描述的，是上下文无关的，但这仅仅是因为它可以枚举所有的可能性（它必须是一个有限的数字，因为我们坚持字母 Σ 是一个有限集）。
那么，这让你何去何从？
基本上，你可以自由地发明任何适合你目的的形式，只要你清楚地为读者定义它的含义。这种形式主义可能会也可能不会导致自动解析器生成的可能性，但如果这不是您的目标，那么这个事实就无关紧要了。大多数 EBNF 方言——其中有很多，实际上没有一个可以在没有帮助的情况下真正生成解析器——允许以某种方式嵌入用自然语言编写的语法描述，这些语法很难或不可能用无上下文描述语法。如果您查看 EBNF 示例，您可能会发现一大堆不同的说法“是字符集的任何元素”，而实际上并没有详尽地列出整个字符集，鉴于 Unicode 的存在，这将是一个荒谬的任务。16 个代码点，比 2 32少很多。但仍然超过一百万。）
于 2020-08-03T16:29:26.343 回答