grammar - 如何处理 BNF 中的大字母?
问题描述
给定一种定义为的语言:
任何一对匹配的符号都是有效的字符串。
例如
00
,55
,YY
还有一大堆非终结符号(比如说4,294,967,296
它们)......
您将如何定义 BNF 语法来表达该语言?(上下文相关或其他。)
我特别有兴趣了解是否有一种方法可以在不编写4,294,967,296
规则的情况下做到这一点:即一个如此庞大的语法,它失去了用 BNF 定义的所有好处,因为它已成为一组“蛮力”有效文字。
解决方案
BNF 的大多数用途是描述上下文无关文法。
您当然可以将 BNF 表示法用于非上下文无关文法;您需要做的就是在左侧放置多个终端。然而,这在实践中通常不是很有用,因为非上下文无关文法不提供对所解析语言结构的直观描述,也不会导致解析语言的算法。人们会期望任何实用的语法形式主义要么给人类读者一个很好的描述,要么允许自动生成解析器,或者两者兼而有之。(这不会使非上下文无关文法在语言的形式分析中无用;在数学理论中,没有必要取悦读者或解析器生成器。)
但是如果我们限制自己使用上下文无关文法,我们会立即遇到障碍,因为上下文无关文法不能表达重复,例如 { ωω | ω∈Σ<sup>* }。根据定义,复制几乎不是上下文无关的,因为上下文无关意味着非终结符的扩展不能依赖于非终结符出现的上下文。因此,表达重复所需的“这个非终结符必须与那个非终结符具有相同的扩展”的规则不能是上下文无关的。
当然,语言{ ωω | ω∈Σ },这就是你要描述的,是上下文无关的,但这仅仅是因为它可以枚举所有的可能性(它必须是一个有限的数字,因为我们坚持字母 Σ 是一个有限集)。
那么,这让你何去何从?
基本上,你可以自由地发明任何适合你目的的形式,只要你清楚地为读者定义它的含义。这种形式主义可能会也可能不会导致自动解析器生成的可能性,但如果这不是您的目标,那么这个事实就无关紧要了。大多数 EBNF 方言——其中有很多,实际上没有一个可以在没有帮助的情况下真正生成解析器——允许以某种方式嵌入用自然语言编写的语法描述,这些语法很难或不可能用无上下文描述语法。如果您查看 EBNF 示例,您可能会发现一大堆不同的说法“是字符集的任何元素”,而实际上并没有详尽地列出整个字符集,鉴于 Unicode 的存在,这将是一个荒谬的任务。16 个代码点,比 2 32少很多。但仍然超过一百万。)
推荐阅读
- javascript - 我需要一种方法来获取网站网址中的内容。由于 cors 问题,许多网站没有出现在 iframe 中
- django - 在 Django Allauth 确认电子邮件中访问帐户信息
- c++ - 如何在 C++ Builder 6 中“取消单击”按钮
- javascript - 在消息部分使用带有链接的 ant-design-vue 通知
- php - 使用 Smarty 修改特定页面
- javascript - 根据现有响应创建新的 json 响应
- java - 有没有办法在 Spring 中从 URI 中获取路径变量列表?
- typescript - GraphQL CodeGen - 使用单个请求执行任意次数的相同突变
- c# - 使用路由参数的 DotNet Core 自定义授权属性
- mysql - 是否可以进一步优化这个 MySQL 查询?