编译课程复习 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 编译课程复习 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
字符流 引论(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 南大编译许畅