第52集：语法分析的基本概念

学习目标

理解语法分析的基本概念和作用
掌握上下文无关文法的定义和表示方法
理解推导、句型和句子的概念
了解语法树的构建方法
掌握文法的二义性概念

1. 语法分析的作用

语法分析是编译过程的第二阶段，紧跟在词法分析之后。它的主要作用是：

验证语法正确性：检查词法分析器输出的词法单元序列是否符合编程语言的语法规则
构建语法结构：为合法的输入构建语法树或分析树，反映程序的层次结构
生成错误信息：当发现语法错误时，生成有意义的错误信息，帮助程序员定位和修正错误
为后续阶段做准备：为语义分析和中间代码生成提供结构化的输入

2. 上下文无关文法

2.1 文法的定义

上下文无关文法（Context-Free Grammar，CFG）是描述程序设计语言语法的数学工具。它由以下四元组组成：

G = (V, T, P, S)

其中：

V：非终结符（Non-terminal）的集合，表示语法成分，如表达式、语句等
T：终结符（Terminal）的集合，表示词法单元，如标识符、数字、运算符等
P：产生式（Production）的集合，描述如何从非终结符推导得到终结符和非终结符的组合
S：开始符号（Start symbol），表示文法的起始点，通常是一个非终结符

2.2 产生式的表示

产生式的一般形式为：

A → α

其中：

A 是一个非终结符
α 是由终结符和非终结符组成的字符串

例如，一个简单的算术表达式文法：

E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id | num

这里：

非终结符集合 V = {E, T, F}
终结符集合 T = {+, -, *, /, (, ), id, num}
开始符号 S = E
产生式集合 P 包含上述所有规则

2.3 文法的例子

示例1：简单的算术表达式文法

E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id | num

示例2：简单的语句文法

Stmt → if ( Expr ) Stmt | while ( Expr ) Stmt | { StmtList }
StmtList → Stmt StmtList | ε
Expr → E
E → E + T | T
T → id | num

其中 ε 表示空串。

3. 推导与归约

3.1 推导

推导是从文法的开始符号出发，通过选择产生式规则替换非终结符，最终得到一个终结符串的过程。

直接推导

如果存在产生式 A → α，并且有字符串 βAγ，那么可以将 A 替换为 α，得到 βαγ，记为：

βAγ ⇒ βαγ

多步推导

多步推导是通过一系列直接推导得到的，记为：

α ⇒* β

表示从 α 经过零步或多步推导得到 β。

最左推导与最右推导

最左推导：每次推导都选择最左边的非终结符进行替换
最右推导：每次推导都选择最右边的非终结符进行替换

例如，对于表达式 id + id * id，使用示例1的文法：

最左推导：

E ⇒ E + T ⇒ T + T ⇒ id + T ⇒ id + T * F ⇒ id + id * F ⇒ id + id * id

最右推导：

E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E + id * id ⇒ T + id * id ⇒ id + id * id

3.2 归约

归约是推导的逆过程，从一个终结符串开始，通过选择产生式规则的右部替换为左部的非终结符，最终得到开始符号的过程。

4. 句型与句子

句型：如果从文法的开始符号 S 可以推导出字符串 α（即 S ⇒* α），那么 α 是该文法的一个句型
句子：如果 α 是一个句型，并且 α 只包含终结符，那么 α 是该文法的一个句子

例如，对于示例1的文法：

E、E + T、id + T 都是句型
id + id * id 是句子

5. 语法树

5.1 语法树的定义

语法树（或分析树）是推导过程的图形表示，它具有以下特点：

根节点是文法的开始符号
每个内部节点表示一个非终结符
每个叶节点表示一个终结符或 ε
每个内部节点的子节点对应于该非终结符使用的产生式的右部符号

5.2 语法树的构建

以表达式 id + id * id 为例，使用示例1的文法构建语法树：

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

5.3 语法树与推导的关系

每个语法树对应多个推导过程（最左推导、最右推导等）
不同的推导顺序可能对应同一个语法树
语法树忽略了推导过程中的选择顺序，只关注最终的结构

6. 文法的二义性

6.1 二义性的定义

如果一个文法存在某个句子，它对应两棵或更多不同的语法树，那么该文法是二义性的。

6.2 二义性的例子

考虑以下简单的表达式文法：

E → E + E | E * E | ( E ) | id | num

对于句子 id + id * id，存在两棵不同的语法树：

语法树1（加法优先）：

        E
       / | \
      E  +  E
      |     / | \
      id   E  *  E
           |     |
           id    id

语法树2（乘法优先）：

        E
       / | \
      E  *  E
     / | \   |
    E  +  E  id
    |     |
    id    id

6.3 二义性的消除

消除文法二义性的方法主要有：

增加优先级规则：明确规定运算符的优先级，如乘法优先于加法
增加结合性规则：明确规定运算符的结合性，如左结合或右结合
重写文法：通过引入新的非终结符来重写文法，消除二义性

例如，将上述二义性文法重写为：

E → E + T | T
T → T * F | F
F → ( E ) | id | num

这样就消除了二义性，因为它明确规定了乘法优先于加法，并且都是左结合的。

7. 文法的分类

根据 Chomsky 文法分类，文法可以分为四类：

文法类型	产生式形式	识别器	语言
0型文法	α → β，α, β 是符号串	图灵机	递归可枚举语言
1型文法	αAβ → αγβ，A是非终结符，γ≠ε	线性有界自动机	上下文有关语言
2型文法	A → α，A是非终结符	下推自动机	上下文无关语言
3型文法	A → aB 或 A → a，A,B是非终结符，a是终结符	有限自动机	正则语言

其中，上下文无关文法（2型文法）是程序设计语言语法的主要描述工具。

8. 实战案例：简单表达式文法的分析

8.1 文法定义

E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id | num

8.2 句子推导

对于句子 (id + num) * id，使用最左推导：

E ⇒ T ⇒ T * F ⇒ F * F ⇒ ( E ) * F ⇒ ( E + T ) * F ⇒ ( T + T ) * F ⇒ ( F + T ) * F ⇒ ( id + T ) * F ⇒ ( id + F ) * F ⇒ ( id + num ) * F ⇒ ( id + num ) * id

8.3 语法树构建

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

9. 自测题

语法分析的主要作用是什么？
上下文无关文法由哪四个部分组成？
解释推导、句型和句子的概念。
什么是文法的二义性？如何消除二义性？
对于文法 E → E + E | E * E | ( E ) | id，构造句子 id + id * id 的两棵不同的语法树，说明该文法的二义性。

10. 小结

在本集中，我们介绍了语法分析的基本概念，包括上下文无关文法、推导、句型和句子等核心概念，以及语法树的构建方法和文法的二义性问题。这些概念是理解语法分析器工作原理的基础，也是后续学习各种语法分析算法（如递归下降分析、LL分析、LR分析等）的必要前提。

11. 下集预告

下一集将介绍 递归下降分析器，这是一种自顶向下的语法分析方法，通过递归调用函数来模拟文法的产生式规则，实现简单而直观的语法分析器。

12. 参考资料

《编译原理》（龙书），Alfred V. Aho 等著
《编译原理教程》，蒋立源等著
《编译器设计》，Alexander A. Stepanov 等著
上下文无关文法 - Wikipedia：https://zh.wikipedia.org/wiki/上下文无关文法