编译原理
教 材：,计算机编译原理（第二版）,
张幸儿，科学出版社
总学时,56学时
其 中：授 课 46学时
习题课 8学时
总复习 2学时
南京工业大学
编译原理
介绍编译程序的一般原理，
重点掌握如何设计和构造编译程
序，即编译程序构造的原理和技
术。
编译原理
? 第一章 总 论
? 第二章 文法和语言
? 第三章 词 法 分 析
? 第四章 语法分析 —— 自顶向下分析技术
? 第五章 语法分析 —— 自底向上分析技术
? 第六章 语义分析与目标代码生成
? 第七章 运 行 环 境
? 第八章 代码优化
? 第九章 程序错误的检查和校正
第一章 总论
本章讨论程序设计语言与编译程序间
的联系，主要内容包括：高级程序设计语
言的定义、源程序的执行及编译程序的构
造。
1.1 引言
1.2 程序设计语言与程序
1.3 编译程序的构造
1.4 形式语言理论与编译实现技术
本章小结
第一章 总论
1.1 引言
? 机器语言
? 汇编语言
? 高级语言
第一章 总论
1.2 程序设计语言与程序
? 程序及其结构
? 程序设计语言的定义
? 程序的执行
第一章 总论
1.3编译程序构造及有关概念
? 编译程序的构造
? 趟的概念
? 编译程序的分类
? 实际应用中的编译程序
第一章 总论
本章重点
? 程序设计语言的定义,语法、语义、语用、语境
? 源程序的执行,解释、翻译
? 编译程序的组成,词法分析
前端 分析 语法分析
语义分析
后端 综合 代码优化
代码生成
? 几个概念,趟、运行子程序、源语言与目标语言、源程序与目标程序
第一章 总论
第二章 文法与语言
本章我们介绍形式语言的一些基本理论。它
是计算机科学的一个重要组成部分，也是编译理
论的重要基础。
2.1符号串与符号串集合
2.2文法与语言的形式定义
2.3语言的分类
2.4文法等价与等价变换
2.5语法树与句型分析
本章小结
第二章 文法与语言
2.1符号串与符号串集合
2.1.1字母表
2.1.2符号串
符号串、符号串长度、子符号串、符号串的头与尾
符号串的联结、符号串的幂
2.1.3符号串集合
符号串集合、符号串集合的乘积、字母表的闭包与正闭包
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.2 语言的形式定义
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.1.1重写规则
重写规则 非终结符 终结符
单规则 元语言符号
2.2.1.2文法的定义
文法 字汇表
2.2.1.3 应用文法产生语言的句子
直接推导 推导 广义推导
句型及句子 短语 简单短语 句柄
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.2 语言的形式定义
文法和语言 递归规则
文法和语言的关系
(1) 给定一个文法，就能从结构上唯一地确定其语言
即 G?L(G)
(2) 给定一种语言，能确定其文法，但这种文法不是唯一的
即 L?G1或 G2或 G3…
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
2.3.3对上下文无关文法的进一步讨论
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
文法的定义
0型文法
1型文法
2型文法
3型文法
例 1 例 2 例 3 例 4
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
3型语言与有穷状态自动机
2型语言与下推自动机
1型语言与线性界限自动机
0型语言与图灵机
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
2.3.3对上下文无关文法的进一步讨论
定理 2.4 (Chomsky范式 )
定理 2.5 (Greibach范式 )
自嵌套的上下文无关文法
定理 2.6
定理 2.7
定理 2.8
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1 文法等价的概念
2.4.2 压缩文法等价变换
2.4.3 增广文法等价变换
2.4.4 消去单规则等价变换
2.4.5 范式文法等价变换
2.4.6 消去左递归的文法等价变换
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
? 压缩了的文法
? 无用规则的判别算法
条件 1 Z?xUy,其中 x,y∈V *,Z为识别符号；
条件 2 u?t,其中 t∈ V T＋ 。
若满足上述条件, 则规则 U∷ =u是有用的 。
第二章 文法与语言
+
*
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
2.4.3增广文法等价变换
2.4.4 消去单规则等价变换
2.4.5 范式文法等价变换
2.4.6 消去左递归的文法等价变换
? 规则左递归的消去
1) 改写规则左递归成右递归
2)沿用扩充 BNF表示法
? 文法左递归的消去
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
? 压缩了的文法
? 无用规则的判别算法
条件 1 Z?xUy,其中 x,y∈V *,Z为识别符号；
条件 2 u?t,其中 t∈ V T＋ 。
若满足上述条件, 则规则 U∷ =u是有用的 。
第二章 文法与语言
+
*
明显的多余规则,U∷ =U；
U∷ =u
例如：文法 G[Z],Z∷=Be
A∷=Ae ｜ A｜ e
B∷ =Ce｜ Af
C∷ =Cf
D∷ =f
定理 2.11 如果一个文法中所有规则都满足上
述两个条件, 则该文法不包含多余规则 。
定义 2.33 如果文法 G无多余规则, 即每个规
则 U∷ =u都满足上述条件 1和条件 2,则称该
文法是压缩了的 。
2.5 语法树与句型分析
2.5.1语法树的概念
2.5.1.1语法分析数的引进
2.5.1.2从推导构造语法树
2.5.1.3从语法树构造推导
2.5.1.4二义性
2.5.2 句型分析
2.5.2.1句型分析的概念
2.5.2.2分析技术
2.5.2.3句型分析的基本问题
第二章 文法与语言
本章重点
? 文法与语言的形式定义,Chomsky文法及其分类、上下文无关文法的主要
特性、文法的等价变换以及句型分析
? 规则、推导、归约、短语、简单短语、句柄、识别符号,VN VT。
? 文法的分类（上下文无关文法）；
? 文法的等价变换（消去左递归）
? 句型分析、语法树、二义性、规范句型、规范推导、规范归约
第二章 文法与语言
教 材：,计算机编译原理（第二版）,
张幸儿，科学出版社
总学时,56学时
其 中：授 课 46学时
习题课 8学时
总复习 2学时
南京工业大学
编译原理
介绍编译程序的一般原理，
重点掌握如何设计和构造编译程
序，即编译程序构造的原理和技
术。
编译原理
? 第一章 总 论
? 第二章 文法和语言
? 第三章 词 法 分 析
? 第四章 语法分析 —— 自顶向下分析技术
? 第五章 语法分析 —— 自底向上分析技术
? 第六章 语义分析与目标代码生成
? 第七章 运 行 环 境
? 第八章 代码优化
? 第九章 程序错误的检查和校正
第一章 总论
本章讨论程序设计语言与编译程序间
的联系，主要内容包括：高级程序设计语
言的定义、源程序的执行及编译程序的构
造。
1.1 引言
1.2 程序设计语言与程序
1.3 编译程序的构造
1.4 形式语言理论与编译实现技术
本章小结
第一章 总论
1.1 引言
? 机器语言
? 汇编语言
? 高级语言
第一章 总论
1.2 程序设计语言与程序
? 程序及其结构
? 程序设计语言的定义
? 程序的执行
第一章 总论
1.3编译程序构造及有关概念
? 编译程序的构造
? 趟的概念
? 编译程序的分类
? 实际应用中的编译程序
第一章 总论
本章重点
? 程序设计语言的定义,语法、语义、语用、语境
? 源程序的执行,解释、翻译
? 编译程序的组成,词法分析
前端 分析 语法分析
语义分析
后端 综合 代码优化
代码生成
? 几个概念,趟、运行子程序、源语言与目标语言、源程序与目标程序
第一章 总论
第二章 文法与语言
本章我们介绍形式语言的一些基本理论。它
是计算机科学的一个重要组成部分，也是编译理
论的重要基础。
2.1符号串与符号串集合
2.2文法与语言的形式定义
2.3语言的分类
2.4文法等价与等价变换
2.5语法树与句型分析
本章小结
第二章 文法与语言
2.1符号串与符号串集合
2.1.1字母表
2.1.2符号串
符号串、符号串长度、子符号串、符号串的头与尾
符号串的联结、符号串的幂
2.1.3符号串集合
符号串集合、符号串集合的乘积、字母表的闭包与正闭包
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.2 语言的形式定义
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.1.1重写规则
重写规则 非终结符 终结符
单规则 元语言符号
2.2.1.2文法的定义
文法 字汇表
2.2.1.3 应用文法产生语言的句子
直接推导 推导 广义推导
句型及句子 短语 简单短语 句柄
第二章 文法与语言
2.2文法与语言的形式定义
2.2.1 文法的形式定义
2.2.2 语言的形式定义
文法和语言 递归规则
文法和语言的关系
(1) 给定一个文法，就能从结构上唯一地确定其语言
即 G?L(G)
(2) 给定一种语言，能确定其文法，但这种文法不是唯一的
即 L?G1或 G2或 G3…
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
2.3.3对上下文无关文法的进一步讨论
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
文法的定义
0型文法
1型文法
2型文法
3型文法
例 1 例 2 例 3 例 4
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
3型语言与有穷状态自动机
2型语言与下推自动机
1型语言与线性界限自动机
0型语言与图灵机
第二章 文法与语言
2.3语言的分类
2.3.1 Chomsky语言分类法
2.3.2形式语言与自动机
2.3.3对上下文无关文法的进一步讨论
定理 2.4 (Chomsky范式 )
定理 2.5 (Greibach范式 )
自嵌套的上下文无关文法
定理 2.6
定理 2.7
定理 2.8
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1 文法等价的概念
2.4.2 压缩文法等价变换
2.4.3 增广文法等价变换
2.4.4 消去单规则等价变换
2.4.5 范式文法等价变换
2.4.6 消去左递归的文法等价变换
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
? 压缩了的文法
? 无用规则的判别算法
条件 1 Z?xUy,其中 x,y∈V *,Z为识别符号；
条件 2 u?t,其中 t∈ V T＋ 。
若满足上述条件, 则规则 U∷ =u是有用的 。
第二章 文法与语言
+
*
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
2.4.3增广文法等价变换
2.4.4 消去单规则等价变换
2.4.5 范式文法等价变换
2.4.6 消去左递归的文法等价变换
? 规则左递归的消去
1) 改写规则左递归成右递归
2)沿用扩充 BNF表示法
? 文法左递归的消去
第二章 文法与语言
2.4 文法等价与等价变换
2.4.1文法等价的概念
2.4.2压缩文法等价变换
? 压缩了的文法
? 无用规则的判别算法
条件 1 Z?xUy,其中 x,y∈V *,Z为识别符号；
条件 2 u?t,其中 t∈ V T＋ 。
若满足上述条件, 则规则 U∷ =u是有用的 。
第二章 文法与语言
+
*
明显的多余规则,U∷ =U；
U∷ =u
例如：文法 G[Z],Z∷=Be
A∷=Ae ｜ A｜ e
B∷ =Ce｜ Af
C∷ =Cf
D∷ =f
定理 2.11 如果一个文法中所有规则都满足上
述两个条件, 则该文法不包含多余规则 。
定义 2.33 如果文法 G无多余规则, 即每个规
则 U∷ =u都满足上述条件 1和条件 2,则称该
文法是压缩了的 。
2.5 语法树与句型分析
2.5.1语法树的概念
2.5.1.1语法分析数的引进
2.5.1.2从推导构造语法树
2.5.1.3从语法树构造推导
2.5.1.4二义性
2.5.2 句型分析
2.5.2.1句型分析的概念
2.5.2.2分析技术
2.5.2.3句型分析的基本问题
第二章 文法与语言
本章重点
? 文法与语言的形式定义,Chomsky文法及其分类、上下文无关文法的主要
特性、文法的等价变换以及句型分析
? 规则、推导、归约、短语、简单短语、句柄、识别符号,VN VT。
? 文法的分类（上下文无关文法）；
? 文法的等价变换（消去左递归）
? 句型分析、语法树、二义性、规范句型、规范推导、规范归约
第二章 文法与语言
