南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（课件讲义）编译课程复习（许畅）

编译课程复习 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版

许畅 南京大学计算机系 2022年春季 编译课程复习 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅

引论(1) 源程序 编译器 目标程序 2

源程序 编译器 目标程序 引论 (1) 2 南大编译许畅

字符流 引论(2) 词法分析器 符号流 语法分析 语法树 语义分析 语法树 符号表 中间代码生成器 中间表示形式 机器无关代码优化器 中间表示形式 代码生成器 目标机器语言 机器相关代码优化器 目标机器语言 3

引论 (2) 3 南大编译许畅

词法分析 功能和作用 相关概念：字母表、串、语言等 正则表达式 。状态转换图 有穷自动机：确定(DFA)VS.不确定(NFA) NFA和DFA识别串的模拟 正则表达式→NFA)DFA DFA状态最小化

词法分析 • 功能和作用 • 相关概念：字母表、串、语言等 • 正则表达式 • 状态转换图 • 有穷自动机： 确定 (DFA) vs. 不确定 (NFA) • NFA和DFA识别串的模拟 • 正则表达式 ➔ NFA ➔ DFA • DFA状态最小化 4 南大编译许畅

语法分析(1) 功能和作用 。 相关概念：文法（上下文无关文法）、推导（最左和 最右)、语法分析树等 二义性、左递归及其消除 自顶向下分析技术 递归下降 预测分析 FIRST和FOLLOW 预测分析表、分析流程 LL(1)文法 5

语法分析 (1) • 功能和作用 • 相关概念：文法 (上下文无关文法)、推导 (最左和 最右)、语法分析树等 • 二义性、左递归及其消除 • 自顶向下分析技术 – 递归下降 – 预测分析 • FIRST和FOLLOW • 预测分析表、分析流程 • LL(1)文法 5 南大编译许畅

语法分析(2) 自底向上分析技术 句柄、移入-归约的分析框架 LR分析技术 。相关概念：项、项集、项集闭包、项集规范族 。 分析框架：增广文法、语法分析表(ACTION表、GOTO表) SLR(1)分析表的构造(LR(O)项) 规范LR(1)语法分析器(LR(1)项) 。LR(1)项集规范族的构造、LR(1)语法分析表的构造 LALR分析、与SLR和LR分析的比较 二义性文法的分析 6

语法分析 (2) • 自底向上分析技术 – 句柄、移入-归约的分析框架 – LR分析技术 • 相关概念：项、项集、项集闭包、项集规范族 • 分析框架：增广文法、语法分析表 (ACTION表、GOTO表) – SLR(1)分析表的构造 (LR(0)项) – 规范LR(1)语法分析器 (LR(1)项) • LR(1)项集规范族的构造、LR(1)语法分析表的构造 – LALR分析、与SLR和LR分析的比较 – 二义性文法的分析 6 南大编译许畅

语义分析和中间代码生成(1) 基于语法制导的翻译技术 语法制导定义 ·属性（综合属性、继承属性） 语义规则 属性求值、注释语法分析树 求值顺序、依赖图 S属性定义、L属性定义 语法制导定义→翻译方案 7

语义分析和中间代码生成 (1) • 基于语法制导的翻译技术 – 语法制导定义 • 属性 (综合属性、继承属性) • 语义规则 • 属性求值、注释语法分析树 • 求值顺序、依赖图 • S属性定义、L属性定义 – 语法制导定义 ➔ 翻译方案 7 南大编译许畅

语义分析和中间代码生成(2) 中间代码的形式 DAG图、抽象语法树、三地址代码 。类型声明 类型表达式、类型等价 类型的声明、局部变量的存储布局、记录和类 表达式的翻译 数组元素的寻址、数组引用的翻译 控制流语句的翻译 控制流语句、布尔表达式、非回填VS.回填 8

语义分析和中间代码生成 (2) • 中间代码的形式 – DAG图、抽象语法树、三地址代码 • 类型声明 – 类型表达式、类型等价 – 类型的声明、局部变量的存储布局、记录和类 • 表达式的翻译 – 数组元素的寻址、数组引用的翻译 • 控制流语句的翻译 – 控制流语句、布尔表达式、非回填 vs. 回填 8 南大编译许畅

运行时刻环境 存储组织 。 栈式存储分配 畅 活动树 活动记录：布局 过程的调用及返回 非局部数据的访问（不支持嵌套过程VS.支持嵌套过程） 。堆管理：垃圾回收 可达性、引用计数、基于跟踪的回收 9

运行时刻环境 • 存储组织 • 栈式存储分配 – 活动树 – 活动记录：布局 – 过程的调用及返回 – 非局部数据的访问 (不支持嵌套过程 vs. 支持嵌套过程) • 堆管理：垃圾回收 – 可达性、引用计数、基于跟踪的回收 9 南大编译许畅

代码生成 目标语言、指令寻址 目标代码中的地址 静态分配 栈分配 。 对中间代码进行局部优化 基本块和流图 基本块的优化 代码生成器 寄存器和地址描述符、代码生成算法、寄存器分配 10

代码生成 • 目标语言、指令寻址 • 目标代码中的地址 – 静态分配 – 栈分配 • 对中间代码进行局部优化 – 基本块和流图 – 基本块的优化 • 代码生成器 – 寄存器和地址描述符、代码生成算法、寄存器分配 10 南大编译许畅