🎉 第 3.13.4 章：巴科斯-诺尔范式 (BNF) 与语法图

各位未来的计算机科学家们，大家好！本章将介绍用于定义编程语言结构（即语法）的强大工具。
有没有想过计算机是如何知道你写的 Python 代码是否有效，或者你在写电子邮件地址时是否出现了拼写错误的？这些规则都是通过像巴科斯-诺尔范式 (BNF) 这样的形式化文法系统，以及像语法图这样的视觉辅助手段来设定的。

理解这些概念对于计算理论 (Theory of Computation) 至关重要，因为它们精确地规范了“有效的程序”或“有效的数据”是什么样子的。让我们深入了解计算机语言的规则手册吧！

1. 定义语法：语言的文法

在研究 BNF 之前，请记住任何语言（无论是 Python、英语，甚至是一个简单的日期格式）都有关于如何组合其元素的规则。

什么是语法？

语法 (Syntax) 指的是支配语言中句子或指令结构的规则。如果你遵循了语法规则，你的句子或指令就是正确构成的，即使它在逻辑上可能讲不通。
示例：“The computer runs quickly”具有正确的英语语法。“Runs computer quickly the”则语法错误。

在编程中，我们需要一种精确、无歧义的方式来编写这些规则——这正是 BNF 和语法图的用武之地。

2. 巴科斯-诺尔范式 (BNF)

巴科斯-诺尔范式 (Backus-Naur Form, BNF) 是一种标准记号系统，用于表示编程语言或其他形式语言的产生式规则（文法）。它允许我们通过将复杂的结构分解为更简单的组件来对其进行定义。

BNF 中的关键符号（字母表大杂烩）

不必纠结于正式的名称，重点在于理解这些符号的含义和作用。

  • 非终结符 (Non-Terminal Symbols)： 代表需要进一步定义的类别或组件。它们总是括在尖括号中。
    示例： <digit>（数字），<variable name>（变量名）
  • 终结符 (Terminal Symbols)： 指在语言中字面出现的实际字符或关键字。它们不能再进一步分解。
    示例： a, 5, =, IF, ;
  • 定义符号 (::=)： 意为“被定义为”或“可替换为”。它将要定义的非终结符与它的定义分隔开。
  • 选择符号 (|)： 代表一种选择，意为“或 (OR)”。

💡 记忆小贴士： 可以把尖括号 < > 想象成包裹住一个概念，而普通文本则是最终具体的字符。

分步指南：制定简单的产生式规则

产生式规则 (Production rule)（或定义）规定了如何构建一个非终结符。

让我们来定义一个简单的 <digit>：

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

解读： 一个 <digit> 被定义为 (::=) 终结符 0 或者 (|) 终结符 1 或者……以此类推。

现在，让我们定义一个 <binary number>（二进制数）：

一个二进制数要么是单个 0 或 1，要么是 0 或 1 后面跟着另一个二进制数（这被称为递归）。

<binary digit> ::= 0 | 1
<binary number> ::= <binary digit> | <binary digit> <binary number>

如果递归规则看起来很棘手，别担心！ 它仅仅意味着你可以重复该结构。如果我们使用这个规则，可以生成：

  • 1（使用第一个选项）
  • 10（使用第二个选项：<binary digit> (1) 后面跟着 <binary number> (0)）
  • 1011（以此类推……）
使用 BNF 检查语言语法

为了检查一个特定的字符串是否符合该语言，我们尝试将该字符串追溯回初始的非终结符。这个过程称为语法分析 (Parsing)。

示例：检查“5F”是否为有效的十六进制位。

假设规则如下：

<hex digit> ::= <digit> | <letter A-F>
<letter A-F> ::= A | B | C | D | E | F
<digit> ::= 0 | ... | 9

字符串“5F”作为单个 <hex digit> 是无效的，因为规则只允许一个数字或一个字母。它不允许一个数字和一个字母同时出现。
如果我们想定义一个双字符的十六进制代码，我们需要一条新规则：

<hex code two char> ::= <hex digit> <hex digit>

现在，“5F”在 <hex code two char> 下就是有效的了。

🔑 核心要点：BNF

BNF 是一种基于文本的形式文法，使用非终结符 (<>)、终结符（字面文本）、定义 (::=) 和 选择 (|) 来定义语言结构。

3. 语法图（视觉化文法）

虽然 BNF 对计算机来说很精确，但语法图 (Syntax Diagrams)（或称铁路图）提供了一种表示相同产生式规则的直观方式。对于人类来说，它们通常更容易一眼看懂。

如何阅读语法图

把语法图想象成一张路线图：

  1. 从图的左侧开始。
  2. 沿着箭头向右走。
  3. 你经过的任何形状都是所需语法的一部分。
  4. 你必须在图的最右侧结束。

图形含义：

  • 椭圆形或圆形： 用于终结符（字面字符或关键字）。你必须使用图中显示的完全相同的符号。
  • 矩形： 用于非终结符（在别处定义的概念，通常在它自己的图表中定义）。

想象一个定义简单“命令”的图表：

一个命令可以定义为关键字 PRINT 后面跟着一个 <String>，或者关键字 INPUT 后面跟着一个 <Variable>。

如果你看到一条路径绕回自身，这表示重复（类似于编程中的迭代）。如果有替代路径（像分叉路口），则表示选择（OR 运算符）。

使用图表检查语法

要检查语法，你只需要尝试在图表中画出一条连续的线，使输入的字符串与遇到的符号精确匹配。如果你能完整地穿过图表，那么输入在语法上就是正确的。

快速复习：BNF 与语法图
  • BNF： 基于文本，精确，适合机器（编译器/解析器）。
  • 图表： 视觉化，直观，适合人类（程序员/学生）。
  • 它们定义的是完全相同的语言文法。

4. BNF 的威力（上下文无关语言）

这是一个高阶概念，但对于考试大纲非常重要，因为它解释了为什么我们使用 BNF 而不是正则表达式 (RE) 之类的方法来定义复杂的编程语言。

在计算理论中，语言按复杂性分级。正则表达式定义了最简单的一类语言，称为正则语言（可以通过有限状态机，即 FSM 来识别）。

然而，编程语言通常属于上下文无关语言 (Context-Free Languages)。BNF 专门用于处理这些更复杂的规则。

为什么正则表达式无法表示一切

正则表达式之所以受到限制，是因为它们没有“记忆”或计数能力。它们只能检查序列和简单的重复。

BNF 通过递归（非终结符引用自身）的使用，允许我们定义需要平衡或内部计数的结构。

需要使用 BNF 的语言（大纲必考点）

大纲明确要求你知道，BNF 可以表示某些正则表达式无法表示的语言。这些语言通常依赖于上下文，或者需要匹配对。

1. 回文 (Palindromes)

  • 回文是指正读反读都一样的字符串（例如：'madam', 'racecar'）。
  • 要检查回文，你必须确保第一个字符与最后一个匹配，第二个与倒数第二个匹配，依此类推。这需要一种正则表达式所缺乏的比较或记忆形式。
  • BNF 规则（针对简单的 'a' 和 'b' 回文）：
    <P> ::= a | b | a <P> a | b <P> b | ε（其中 ε 表示“空字符串”）

2. 包含相等数量特定字符的字符串

  • 一种语言，例如 'A' 的数量必须正好等于 'B' 的数量（例如：'AABB', 'ABAB'，但不是 'AAAB'）。
  • 正则表达式无法计数或确保这种平衡，但 BNF 通过递归结构可以处理它。
你知道吗？

“巴科斯-诺尔范式”这一名称是以 John Backus 和 Peter Naur 的名字命名的，他们在 20 世纪 50 年代末使用它来定义最早的高级编程语言之一——Algol 60 的语法。这种形式化定义对编译器设计来说是一场革命！

🌟 为什么 BNF/上下文无关文法很重要？

几乎所有现代编程语言（如 C++, Java, Python）的语法都是使用 BNF 或其扩展来定义的。这种能力至关重要，因为这些语言需要嵌套括号 ()、平衡方括号 [] 以及匹配 IF/END IF 块等结构——所有这些都需要上下文无关文法提供的“记忆”功能。

5. 总结：核心掌握概念

A. 检查语法
  • 能够阅读 BNF 定义，并通过追溯规则确定示例字符串是否有效。
  • 能够阅读语法图（遵循路径），并确定示例字符串是否有效。
B. 制定简单的 BNF 规则
  • 理解并使用 <非终结符>、::=、| 和终结符。
  • 能够编写包含选择 (OR) 或简单重复/递归的基本规则。
C. 正则表达式的局限性
  • 知道正则表达式定义正则语言（较简单）。
  • 知道 BNF 可以定义上下文无关语言（较复杂）。
  • 能够说明 BNF 可以表示而正则表达式不能表示的具体例子：回文和需要相等数量特定字符的语言。

继续练习推导那些规则吧！你已经成功通过了计算机科学的语法审查关卡！