南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（课件讲稿，2023）第一章 引论（许畅）

第一章引论 许畅 南京大学计算机系 2023年春季 版权所有南京大学计算机科学与技术系许畅2023春季版

许畅 南京大学计算机系 2023年春季 第一章 引论 版权所有 南京大学计算机科学与技术系 许畅 2023春季版

课程内容 。1.引论（易) 。3.词法分析（难) 安排较紧 0 4.语法分析（难） ·5.语法制导的翻译技术（中） 。6.中间代码生成（难） ·7.运行时刻环境（易） 安排较松 ·8.代码生成（中) 。9.机器无关优化（中） 6

课程内容 • 1. 引论 (易) • 3. 词法分析 (难) • 4. 语法分析 (难) • 5. 语法制导的翻译技术 (中) • 6. 中间代码生成 (难) • 7. 运行时刻环境 (易) • 8. 代码生成 (中) • 9. 机器无关优化 (中) 6 安排较紧 安排较松

编译器的作用 编译器(compiler) 读入以某种语言（源语言）编写的程序 输出等价的用另一种语言（目标语言）编写的程序 通常目标程序是可执行的 源程序 编译器 解释器(interpreter) 目标程序 直接利用用户提供的输入，执行源程序中指定的操作 不生成目标程序，而是根据源程序的语义直接运行 Java语言的处理结合了编译和解释 7

编译器的作用 • 编译器 (compiler) – 读入以某种语言 (源语言) 编写的程序 – 输出等价的用另一种语言 (目标语言) 编写的程序 – 通常目标程序是可执行的 • 解释器 (interpreter) – 直接利用用户提供的输入，执行源程序中指定的操作 – 不生成目标程序，而是根据源程序的语义直接运行 – Java语言的处理结合了编译和解释 7

编译器的结构(1) 编译器可以分为分析部分和综合部分 分析(analysis))部分/前端(front end) 把源程序分解成组成要素，以及相应的语法结构 使用这个结构创建源程序的中间表示 同时收集和源程序相关的信息，存放到符号表 综合(synthesis))部分/后端(back end) 根据中间表示和符号表信息构造目标程序 ·前端部分是机器无关的，后端部分是机器相关的 8

编译器的结构 (1) • 编译器可以分为分析部分和综合部分 • 分析 (analysis) 部分 / 前端 (front end) – 把源程序分解成组成要素，以及相应的语法结构 – 使用这个结构创建源程序的中间表示 – 同时收集和源程序相关的信息，存放到符号表 • 综合 (synthesis) 部分 / 后端 (back end) – 根据中间表示和符号表信息构造目标程序 • 前端部分是机器无关的，后端部分是机器相关的 8

编译器的结构(2) 编译器可分成顺序执行的一组步骤(phase) 字符流 中间表示形式 词法分析器 机器无关代码优化器 符号流 中间表示形式 语法分析 代码生成器 语法树 目标机器语言 语义分析 机器相关代码优化器 符号表 语法树 目标机器语言 中间代码生成器 9

编译器的结构 (2) • 编译器可分成顺序执行的一组步骤 (phase) 9

词法分析 词法分析/扫描(lexical analysis/scanning) 读入源程序的字符流，输出为有意义的词素(lexeme) token-name由语法分析步骤使用 attribute-value指向相应的符号表条目，由语义分析/ 代码生成步骤使用 例子 position initial rate 60 10

词法分析 • 词法分析/扫描 (lexical analysis/scanning) – 读入源程序的字符流，输出为有意义的词素 (lexeme) – – token-name由语法分析步骤使用 – attribute-value指向相应的符号表条目，由语义分析/ 代码生成步骤使用 • 例子 – position = initial + rate * 60 – 10

语法分析 语法分析/解析(syntax analysis/parsing) 根据各个词法单元的第一个分量来创建树型的中间表 示形式，通常是语法树(syntax tree) 中间表示形式指出了词法单元流的语法结构 (id,1)(=〉(id,2)(+〉(id,3)(*)(60) 语法分析器 id,1- 60 11

语法分析 • 语法分析/解析 (syntax analysis/parsing) – 根据各个词法单元的第一个分量来创建树型的中间表 示形式，通常是语法树 (syntax tree) – 中间表示形式指出了词法单元流的语法结构 11

语义分析 。语义分析(semantic analysis) 使用语法树和符号表中的信息，检查源程序是否满足 语言定义的语义约束 同时收集类型信息，用于代码生成、类型检查、类型 转换 ay (d,2 (id,3) 60 语义分析器 (id,1) (id,2 (id,3) inttofloat 60 12

语义分析 • 语义分析 (semantic analysis) – 使用语法树和符号表中的信息，检查源程序是否满足 语言定义的语义约束 – 同时收集类型信息，用于代码生成、类型检查、类型 转换 12

中间代码生成 根据语义分析输出，生成类机器语言的中间表示 三地址代码(hree-address code) 每个指令最多包含三个运算分量 t1 inttofloat(60);t2=id3 t1;t3 =id2+t2; 很容易生成机器语言指令 (id,2) (id,3)} inttofloat 60 中间代码生成器 t1 inttofloat(60) t2 id3 t1 t3 id2 +t2 id1 =t3 13

中间代码生成 • 根据语义分析输出，生成类机器语言的中间表示 • 三地址代码 (three-address code) – 每个指令最多包含三个运算分量 – t1 = inttofloat(60); t2 = id3 * t1; t3 = id2 + t2; … – 很容易生成机器语言指令 13

中间代码优化 通过对中间代码的分析，改进中间代码的质量 更快、更短、能耗更低 t1 inttofloat(60) t2 id3 t1 t3 id2 t2 id1 t3 代码优化器 t1=id3*60.0 id1 id2 t1 14

中间代码优化 • 通过对中间代码的分析，改进中间代码的质量 – 更快、更短、能耗更低 14