欢迎来到“上下文无关语言”(Context-Free Languages) 的世界！

在你的计算理论 (Theory of Computation) 学习旅程中，你已经认识了正则语言 (Regular Languages)（即我们用正则表达式和有限状态机来描述的语言）。它们对于简单任务非常实用，例如检查密码是否包含数字。

不过，正则语言有一个弱点：它们只有“短期记忆”。它们无法进行计算，也无法处理深度嵌套的结构。这就是上下文无关语言派上用场的时候了！在本章中，我们将学习如何使用巴科斯范式 (Backus-Naur Form, BNF) 和语法图 (Syntax Diagrams) 来描述这些功能更强大的语言。

快速回顾：请记住，语言不过是一组字符串的集合。如果一个语言过于复杂，无法用正则表达式来描述，那么它很可能就是一种上下文无关语言。

如果初次接触觉得有点抽象，请不要担心！把它想象成从基础算术进阶到代数——我们只是在为这项工作添置更好的工具而已。

1. 为什么我们需要上下文无关语言？

课程大纲提到，你需要解释为什么我们使用 BNF 而不是正则表达式。

试想一下，如果你想检查一个数学表达式是否具有对称的括号，例如 \( ( ( ) ) \)。有限状态机无法做到这一点，因为它需要无限数量的状态来“计算”开启了多少个括号，以便知道需要关闭多少个。

上下文无关语言可以处理：

  • 嵌套 (Nesting)：结构内的结构（例如括号内的括号）。
  • 递归 (Recursion)：引用自身的规则。
  • 匹配对 (Matching pairs)：例如语言 \( \{0^n1^n | n \ge 1\} \)，其中 0 的数量必须与 1 的数量完全相等。

你知道吗？大多数程序语言（如 Python 或 Java）都是上下文无关的。这就是为什么当你忘记关闭大括号时，编译器能够侦测出来的原因！

重点总结：正则表达式无法描述需要“计算”或“平衡”的语言（如 \( 0^n1^n \)）。上下文无关语言功能更强大，并使用 BNF 来描述。

2. 巴科斯范式 (BNF)

BNF 是一种用于描述语言语法（规则）的表示法。它使用一组产生规则 (production rules) 来展示语言中的合法字符串是如何构建的。

BNF 的符号

要阅读 BNF，你只需要知道三个主要符号：

  1. < >：这些角括号包围的是非终结符 (non-terminal)。你可以把它想象成一个“变量”或“类别”，可以进一步细分。
  2. ::=：这意味着“定义为”。
  3. |：这意味着“或”(OR)。它允许不同的选择。
任何不在角括号内的项目都是终结符 (terminal)。这些是最终出现在字符串中的实际字符或符号（例如 "a"、"1" 或 "+"）。

一个简单的例子

让我们定义一个数字 (digit)：
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

现在，让我们使用递归来定义一个整数：
<number> ::= <digit> | <digit><number>

等等，刚刚发生了什么？第二条规则说明一个数字要么是单个数字，要么是一个数字后跟随另一个数字。这让我们能够组成任意长度的数值（例如 5、52 或 521）！

记忆小撇步：将非终结符 (< >) 想象成“乐高说明书”，而将终结符想象成实际的“乐高积木”。你根据说明书来决定如何组合这些积木。

重点总结：BNF 使用递归和产生规则来定义复杂结构如何由简单结构构建而成。

3. 语法图 (Syntax Diagrams)

语法图（有时被称为铁路图，Railroad Diagram）只是表现 BNF 规则的一种可视化方式。它就像火车路线图——你跟随箭头从左到右，看看一个字符串是否合法。

如何阅读它们：

  • 矩形：代表非终结符（在其他地方定义的规则）。
  • 圆形或椭圆形：代表终结符（实际的字符）。
  • 箭头：显示你必须走的路线。
  • 循环：代表重复（递归）。

比喻：想象一条火车轨道。如果你能通过路径上的符号从起点走到终点，那么你的字符串就是“语法正确的”。

常见错误：学生经常忘记你必须遵循箭头的方向。除非有专用的返回循环，否则你不能向后走！

重点总结：语法图是 BNF 的可视化替代方案。矩形是“子规则”，而椭圆形/圆形是“最终字符”。

4. 制定产生规则

你可能会被要求编写自己的 BNF 规则。让我们看一个针对必须以 '1' 开头的简单二进制字符串 (Binary String) 的逐步示例。

第 1 步：定义基本组成部分。
<bit> ::= 0 | 1

第 2 步：定义重复部分。
我们需要一种方法来表示多个位元 (bits)。
<bits> ::= <bit> | <bit><bits>

第 3 步：合并它们以得出最终规则。
字符串必须以 1 开头。
<binary_string> ::= 1 | 1<bits>

快速复习盒：
- 终结符：路径的“终点”（例如 'a', 'b', '1'）。
- 非终结符：可以进一步展开（例如 <word>）。
- 递归规则：引用自身的规则（例如 <list> ::= <item> | <item><list>）。

重点总结：要创建 BNF 规则，请从最小的部分开始，并使用递归来允许重复模式。

上下文无关语言总结

1. 为什么？正则表达式无法处理嵌套或类似 \( 0^n1^n \) 的“匹配”模式。
2. BNF：一种基于文本的方法，使用 <非终结符>、::=（定义）和 |（或）来定义规则。
3. 语法图：一种使用路径、矩形和圆形来展示相同规则的可视化方法。
4. 递归：这是允许 BNF 描述无限长或嵌套字符串的“秘密武器”。

做得好！你已经涵盖了 AQA A Level 计算机科学中关于上下文无关语言的要点。继续练习这些 BNF 规则吧——一旦你掌握了窍门，它们就像拼图一样有趣！