7 上下文无关文法的深入探讨

在上一篇中，我们谈到了词法分析及其实现，主要聚焦于如何将输入的源代码转化为记号（token），同时为下一步的语法分析奠定基础。在这一章中，我们将专注于上下文无关文法（CFG），它是语法分析的核心。

什么是上下文无关文法？

上下文无关文法是一种形式文法，广泛应用于编程语言的语法定义。上下文无关文法由四个部分组成：

• 终结符：语言中的基本符号，不能再被替代。例如，在编程语言中，标识符、数字、运算符等都是终结符。
• 非终结符：语法结构的抽象表示，通常用于生成各种句法结构。例如，<expression>、<statement>等。
• 产生式：定义非终结符如何被替代为终结符和其他非终结符。每个产生式的形式通常为：A → α，其中 A 是非终结符，α 是一个由终结符和非终结符组成的串。
• 开始符：文法中的一个特殊非终结符，通常标记为 S，它是生成语言的起点。

示例

我们可以用以下简单的文法来描述一个算术表达式的基本结构：

1. S → E
2. E → E + T | E - T | T
3. T → T * F | T / F | F
4. F → ( E ) | id | num

在这里：

• E、T、F 是非终结符
• +、-、*、/、(、)、id（标识符）和 num（数字）是终结符
• S 是开始符

上下文无关文法的应用

在编译器设计中，CFG用于定义程序的语法结构，从而帮助编译器进行结构分析。语法分析通常通过“推导”过程实现，即根据文法规则将非终结符替换为终结符。

案例：推导过程解析

假设我们要解析表达式 id + num * id，我们可以通过文法产生式逐步推导出该表达式的结构。

1. S → E
2. E → E + T
3. E → T
4. T → T * F
5. T → F
6. F → id
7. F → num

逐步推导可以展示出编译器会如何处理输入字符串，最终形成语法树。

语法树的构建

语法树是一种树形结构，每个节点表示一个语法结构。通过语法树，我们可以清晰地看到源代码的结构信息，便于后续的语义分析和代码生成。

以下是一个简单的语法树示例，用于表示表达式 id + num * id：

   E
  /|\
 E + T
 |   /|\
 F  T * F
 |  |   |
id  F   id
    |
   num

小结

在本节中，我们对上下文无关文法做了详细的介绍，重点讲解了 CFG 的构成、推导过程及其在语法分析中的应用。上下文无关文法是编译器能够理解和分析程序的重要工具。在下一篇中，我们将深入探讨语法分析的具体技术，如自顶向下分析和自底向上分析等方法。这些技术将会利用我们在本节中学到的上下文无关文法知识，生成解析树和更深层次的语法结构。