《编译原理（第三版）》由著名学者陈火旺编写，全面阐述了编译器的设计与实现技术，内容涵盖词法分析、语法分析等多个核心领域。
### 编译原理（第三版）陈火旺
#### 知识点概览
本章节主要涉及形式语言与自动机理论中的基本概念和技术，包括文法、推导过程、语法树以及有限自动机等内容。这些是理解编译器工作原理的基础。
#### 文法与推导
**文法规则**在编译原理中是非常核心的概念之一，它定义了程序语言的语法结构。下面我们将详细解析几个例子：
1. **数字串的生成**
- 文法规则定义了一个由0到9组成的数字串的生成过程。
- **最左推导**示例：
[
N Rightarrow ND Rightarrow NDD RightRightarrow NDDD RightRightarrow DDDD RightRightarrow 0DDD RightRightarrow 01DD RightRightarrow 012D RightRightarrow 0127
]
[
N Rightarrow ND RightRightarrow DD RightRightarrow 3D Right⇒ 34
]
[
N Rightarrow ND Rightrightarrow NDD Rightrightarrow DDD Rightrightarrow 5DD Rightrightarrow 56D Rightrightarrow 568
]
- **最右推导**示例：
[
N RightRightarrow ND RightRightarrow N7 Right⇒ ND7 Right⇒ N27 Right⇒ ND27 Right⇒ N127 RightRightarrow D127 Rightrightarrow 0127
]
[
N RightRightarrow ND Rightrightarrow N4 Rightrightarrow D4 Rightrightarrow 34
]
[
N RightRightarrow ND Rightrightarrow N8 Rightrightarrow ND8 Rightrightarrow N68 Rightrightarrow D68 Rightrightarrow 568
]
- 这些推导过程展示了如何通过不同的步骤生成合法的数字串。
2. **算术表达式的生成**
- 给出以下文法规则：
[
G(E)：E RightRightarrow T | E+T | E-T
]
[
T Right⇒ F | T*F | TF
]
[
F Right⇒ (E) | i
]
- **最左推导**示例：
[
E Rightrightarrow E+T Rightrightarrow T+T Rightrightarrow F+T Rightrightarrow i+T Rightrightarrow i+T*F Rightrightarrow i+F*F Rightrightarrow i+i*F Rightrightarrow i+i*i
]
[
E RightRightarrow T Right⇒ T*F Right⇒ F*F Right⇒ i*F RightRightarrow i*(E) Rightrightarrow i*(E+T) Rightrightarrow i*(T+T) Rightrightarrow i*(F+T) Rightrightarrow i*(i+T) Rightrightarrow i*(i+F) Rightrightarrow i*(i+i)
]
- **最右推导**示例：
[
E RightRightarrow E+T Right⇒ E+T*i Right⇒ E+F*i Right⇒ E+i*i Rightrightarrow T+i*i Rightrightarrow F+i*i Rightrightarrow i+i*i
]
[
E RightRightarrow T Rightrightarrow T*F Rightrightarrow T*(E) Rightrightarrow T*(E+T) Rightrightarrow T*(E+F) Rightrightarrow T*(E+i) Rightrightarrow T*(T+i) Rightrightarrow T*(F+i) Rightrightarrow T*(i+i) RightRightarrow F*(i+i) Right⇒ i*(i+i)
]
- 上述示例展示了如何通过不同的推导路径生成合法的算术表达式。
3. **语法树**
- 语法树是一种图形表示方法，用于展示一个字符串是如何根据文法规则生成的。
- 例如：
[
E
]
[
i+i+i
]
[
E
]
[
+
]
[
T
]
[
E
]
[
+
]
[
T
]
[
T
]
[F]
[i]
[F]
[i]
[F]
[i]
- 语法树有助于理解表达式的结构及其运算顺序。
#### 二义性与确定性
- **二义性**是指存在多个推导路径生成相同的字符串。
- 例如，字符串`iiiei`有两个不同的语法树：
[
S
]
[
i
]
[S]
[
e
]
[S]
[
i
]
5星
