parsing - 如何在 BNF 中表示否定？

Question

BNF 或 ABNF 是否支持否定。那就是排除集合的某些成员？我在它的语法中没有看到任何这样的否定运算符。

例如，假设所有字母数字字符串的S集合不等于"foo" What is the BNF for S?

Answer 1

上下文无关语法在“差异”或“互补”下不封闭。因此，尽管您可能决定在 BNF 中添加一个运算符“减法”，但即使它有一种简单的表达方式，结果也不会是上下文无关语法。结果：人们不允许在用于表达上下文无关文法的 BNF 文法中使用此类运算符。

Answer 2

虽然不在 BNF 中，但 EBNF 确实有例外符号（通常定义为“-”）。在您的情况下，语法为：

alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9"|"A"|...|"Z";
S= (alphaNum,{alphaNum}) - "foo";

或者，如果您希望它不区分大小写：

foo="f"|"F","o"|"O","o"|"O";
alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9"|"A"|...|"Z";
S= (alphaNum,{alphaNum}) - foo;

这导致接受标准与评论中所做的略有不同，相当于：

alphaNum="a"|"b"|...|"z"|"0"|"1"|...|"9";
S= alphaNum - "f", {alphaNum} 
  |"f", alphaNum - "o", {alphaNum}
  |"f", "o", alphaNum - "o", {alphaNum};

这省略了字符串“f”和“fo”。

但是，重要的是要注意，正如 Ira Baxter 在他们的回答中所说，允许任何例外（否定）因素都会导致问题。ISO标准中也指出了这一点：

4.7 语法异常

句法异常由句法因子组成，该句法因子受到以下限制：由句法异常表示的符号序列可以同样由不包含元标识符的句法因子表示。

注意- 如果句法异常被允许作为任意句法因素，扩展 BNF可以定义比上下文无关文法更广泛的语言类别，包括导致类似罗素悖论的尝试，例如

xx = "A" - xx;

“A”是 xx 的一个例子吗？这种许可是不可取的，因此句法异常的形式仅限于可以证明是安全的情况。因此，虽然句法因素通常等价于一些上下文无关文法，但句法异常总是等价于一些常规文法。可以证明，上下文无关文法和常规文法之间的区别总是另一种上下文无关文法。因此，句法术语（以及因此根据该标准定义的任何文法）等价于某些上下文无关文法。