6

我知道EBNF可以用来表达Context Free Grammar，但是这两者有什么区别吗？

我之所以问，是因为有些问题要求将 EBNF 转换为 CFG，但就我目前的理解而言，它们看起来是一样的。因此，这种转换背后的意图是什么？

4

3 回答 3

4

EBNF 可用于编写上下文无关文法。

拉丁字母可以用来写英文。

帕斯卡可以用来表达一个算法。

“上下文无关语法”是一种抽象的东西，你可以用 EBNF 形式写出来以供机器输入。实际的上下文无关文法是一个数学对象。它有标准符号，但标准符号实际上是供人类使用的。

于 2014-02-01T00:44:14.873 回答
3

总结：EBNF不直接等同于CFG形式，但是很多EBNF语法可以机械转换。

上下文无关文法是一个四元组：

  • 一组非终结符V

  • 一组与 Σ 不相交的终端V

  • 一组形式的产生式

    v → ω

其中v是 的元素V并且ω是( 即可能为空的终结符和非终结符字符串。(V ⋃ Σ)*

  • 一个起始符号S，它是 的一个元素V。

（参见Wikipedia 文章及其参考资料。还有另一种等效的形式主义，它使用非终结符的集合V和一个字母表A，它是 和 的V并集Σ。）

为了描述Algol编程语言，John Backus 在 1959 年提出了 CFG 的早期具体语法；这种形式通常被称为Backus-Naur Form，由 Donald Knuth 提出的一个名称，以表彰 Algol 报告的合著者 Peter Naur 的贡献。BNF 和上面的 CFG 形式主义之间的主要区别在于，具有共同左侧的产生式使用|符号缩写：

     v → ω1 | ω2
    ⇒<br/>       v → ω1
      v → ω2

然而，在实践中，使用常规运算符，特别是像 Kleene Star 这样的重复运算符，已被证明更容易编写和理解。BNF 的许多扩展被提出并用于各种语法，尤其是 Niklaus Wirth。特别是，在标准协议文档中使用一种扩展 BNF 形式变得很普遍，包括 RFC（IETF 互联网标准）和各种 ISO 标准。这些形式最终被“标准化”为Extended BNF、ISO/IEC 14977和有点相似的Augmented BNF、RFC-5234。

为了将 EBNF 转换为 CFG 形式，有必要将重复的所有用途——包括有限重复——、交替和可选运算符扩展为原始形式，这需要引入新的非终结符。此外，EBNF 和 ABNF 都允许可能无法转换为 CFG 的规范，包括用英语编写的限制。（请参阅我对Ebnf 的回答中的第一个注释——这是 LL(1) 语法吗？）

于 2014-02-02T17:23:19.580 回答
0

是 - 与 ABNF 和 RBNF 不同，EBNF 的标准允许例外，这意味着它可用于定义非上下文无关语言。

证明：

  1. L1 的语言 = {a^nb^na^m | n, m ≥ 0} 由以下公式生成：

    L1 ::= X,A

    X ::= "a",X,"b" | 空字符串

    A ::= A,"a" | 空字符串

  2. L2 的语言 = {a^nb^ma^m | n, m ≥ 0} 由以下公式生成：

    L2 ::= A,X

  3. L 1 ∩ L 2 = {a^nb^na^n | n ≥ 0} 不是上下文无关的，因为对于给定的 p ≥ 1，我们可以选择 n > p 使得 s = a^nb^na^n 在我们的语言中，我们不能选择 s 的任何子串 q使得 q 的长度为 p，对于某些字符串 x 和 y 和 xq^ny ∈ L 1 ∩ L 2 ， s = xqy （因为 q 必须至少包含一个 a 并且应该包含与左如右）。

    P ::= L1 - L2

    {a^nb^na^n | n ≥ 0} 是 Q 的语言，其中

    Q ::= L1 - P

于 2019-07-29T15:16:44.863 回答