4

增广巴科斯-瑙尔形式中的替代算子 ( /) 是可交换的吗？

例如，是否s = a / b与 相同s = b / a？

4

2 回答 2

3

我还没有找到关于 BNF 或 ABNF 的任何主要来源，它们/在双方都会产生有效匹配时明确指定语义。它们也没有提到上下文无关的语法和它们对非确定性的允许。如果有人知道澄清参考，请分享。

编辑：托尼的回答指出2003 年的RFC 3501指定了 ABNF 交替的语义，至少在该文档中使用它。

RFC 5234：语法规范的增强 BNF：ABNF (2008)

引言对比了 BNF 和 ABNF（此处添加了重点）：

多年来，Backus-Naur Form (BNF) 的修改版本，称为增强 BNF (ABNF)，已在许多 Internet 规范中流行。它平衡了紧凑性和简单性与合理的表现力。在 Arpanet 的早期，每个规范都包含自己对 ABNF 的定义。这包括电子邮件规范、RFC733，然后是RFC822，它们成为定义 ABNF 的常见引用。当前文件将这些定义分开以允许选择性参考。

标准 BNF 和 ABNF 之间的区别涉及命名规则、重复、替代、顺序无关和值范围。

“选择性引用”和“顺序无关”可能与交替排序语义有关，但尚不清楚。

RFC 822：ARPA Internet 文本消息格式标准(1982)

除非我遗漏了什么，否则引用的 RFC 也没有指定/语义。2.2 节回避了这个问题。

2.2. 规则 1 / 规则 2：替代方案

由斜线 ("/") 分隔的元素是替代项。因此“foo / bar”将接受 foo 或 bar。

各种规则定义表明他们认识到避免歧义的实际重要性。例如，以下是 RFC 822 定义optional-field及其依赖项的方式：

 optional-field =
             /  "Message-ID"        ":"   msg-id
             /  "Resent-Message-ID" ":"   msg-id
             /  "In-Reply-To"       ":"  *(phrase / msg-id)
             /  "References"        ":"  *(phrase / msg-id)
             /  "Keywords"          ":"  #phrase
             /  "Subject"           ":"  *text
             /  "Comments"          ":"  *text
             /  "Encrypted"         ":" 1#2word
             /  extension-field              ; To be defined
             /  user-defined-field           ; May be pre-empted

 extension-field =
               <Any field which is defined in a document
                published as a formal extension to this
                specification; none will have names beginning
                with the string "X-">
 
 user-defined-field =
               <Any field which has not been defined
                in this specification or published as an
                extension to this specification; names for
                such fields must be unique and may be
                pre-empted by published extensions>

苏黎世 ACM-GAMM 会议提议的国际代数语言的语法和语义（Backus 1958）

BNF 来自 IAL 表示法。论文介绍了̅o̅r“元语言连接词”，直观上与/. 但是，它也避开了模棱两可的选择问题，大概只是谨慎使用它。

推荐

由于未指定的语义，我的建议是将规则中的每个可能匹配alternation视为有效。如果没有仔细设计语法以避免歧义，这种解释可能会导致相同输入的多个有效解析树。在发生歧义解析时解决它们比使用无意中有效的解析树更安全。

或者，如果您对语法的指定方式有影响，您可以考虑使用语义更清晰的符号。例如，Parsing Expression Grammar: A Recognition-Based Syntactic Foundation (Ford 2004) 提供了确定性优先选择语义（最左边的匹配获胜）。

于 2019-03-01T20:25:36.710 回答
3

一些 RFC 明确阐明了这一点，例如 IMAPv4 的 RFC3501 包括RFC 3501 第 9 节中类似 PEG 的行为的规范：

在后面的规则与前面的规则重叠的替代或可选规则的情况下，前面列出的规则必须优先。例如，“\Seen”在解析为标志时是 \Seen 标志名称而不是标志扩展，即使“\Seen”可以被解析为标志扩展。该规则的一些（但不是全部）实例如下所述。

不过，我不知道这种消歧（哈哈）有多普遍。我看过的许多其他 RFC（我最近几天一直在实现 ABNF 解析器库）只是未指定它。许多 RFC ABNF 语法是明确的（例如 RFC8259 (JSON)）；然而，许多是模棱两可的（例如 RFC5322（Internet 消息））并且需要修正才能与保持歧义的解析器一起工作:-(

于 2019-03-01T20:33:46.727 回答