编译原理课件CHAPTER 1(Introduction to Compiling).ppt

2020 1 25 1 PrincipleofCompiler 编译原理 2020 1 25 2 课程主要内容 编译器 compiler 构造的原理 技术和实践 编译的基本理论 形式文法与形式语言编译器实现技术编程实现一个小型语言的编译器 课程介绍 2020 1 25 3 前导课程 高级语言程序设计 离散数学 数据结构和汇编语言 C PASCAL FORTRAN ALGOL图论各种数据结构及实现汇编语言代码格式 课程介绍 2020 1 25 4 教材 Compiler Principles Techniques andTools 教材与参考书 该书由三位世界著名的计算机科学家联合编写 是编译领域无可替代的经典著作 被誉为 龙书 书中深入讨论了编译器设计的重要主题 在介绍编译器一般原理的同时 特别注重编译原理和技术的实际应用 并在最后给出了几个编译器的实例 此外 本书的每一章都提供了大量的习题和参考文献 本书一直被国外著名大学特别是美国的著名大学当作编译原理与技术课程的教材 2020 1 25 5 参考书 陈火旺等 编译原理 电子工业出版社 2000 杜淑敏等 编译程序设计原理 北京大学出版社 1990 11 教材与参考书 2020 1 25 6 Chapter1IntroductiontoCompiling 编译器概念 ConceptionofCompiler 编译的阶段 PhasesofCompiler 编译器的结构 FrameworkofCompiler 编译器的实现 ImplementationofCompiler 编译器的伙伴 CousinsofCompiler 2020 1 25 7 1 1编译器概念 编译程序是现代计算机系统的基本组成部分 操作系统 编译系统 裸机 计算机系统 2020 1 25 8 1 1编译器概念 从功能上看 一个编译程序就是一个语言翻译程序 它把一种语言 称作源语言 sourcelanguage 书写的程序翻译成另一种语言 称作目标语言 targetlanguage 书写的等价的程序 2020 1 25 9 1 1编译器概念 ACompiler 2020 1 25 10 1 1编译器概念 源语言和目标语言是多种多样的一般来说 源语言是面向人的高级语言 目标语言是面向机器的低级语言 机器语言 编译器执行的是一个等价变换 程序功能一样 执行结果一样要考虑时间与空间效率 2020 1 25 11 1 2编译的阶段 编译的分析 综合模型 Analysis SynthesisModelofCompilation 分析 分析源程序 计算其基本属性 生成源程序的中间表示 intermediaterepresentation 综合 将源程序的中间表示转换为目标代码 2020 1 25 12 1 2编译的阶段 编译的逻辑过程词法分析 LexicalAnalysis 语法分析 SyntaxAnalysis 语义分析 SemanticAnalysis 中间代码生成 IntermediateCodeGeneration 代码优化 CodeOptimization 目标代码生成 CodeGeneration 2020 1 25 13 1 2编译的阶段 词法分析 LexicalAnalysis 功能 从左至右读源程序 字符流 识别单词符号 又称记号token 源程序字符序列 单词符号序列词法分析又称线性分析或扫描 LinearAnalysis Scanning 2020 1 25 14 例 position initial rate 60 单词类型单词值标识符1 id1 position算符 赋值 标识符2 id2 initial算符 加 标识符3 id3 rate算符 乘 整数60 2020 1 25 15 1 2编译的阶段 语法分析 SyntaxAnalysis 功能 层次分析 HierarchicalAnalysis 依据 源程序的语法规则 例 P6 7 单词符号序列 分析树 ParseTree 或语法树 SyntaxTree 语法分析又称解析 Parsing 2020 1 25 16 例 position initial rate 60 ParseTree 2020 1 25 17 例 position initial rate 60 语法树是分析树的压缩表示 2020 1 25 18 1 2编译的阶段 语义分析 SemanticAnalysis 功能 语义检查 即验证语法结构合法的程序是否在语义上正确 程序的各个组成部分组合在一起是否有意义 收集代码生成阶段需要的语义信息类型检查与类型转换分析树 带语义 注释 的树 2020 1 25 19 例 position initial rate 60 60 position initial rate inttoreal 2020 1 25 20 1 2编译的阶段 中间代码生成 IntermediateCodeGeneration 功能 生成源程序的中间表示 三地址代码 threeaddress code 带语义 注释 的树 中间代码 2020 1 25 21 例 position initial rate 60 中间代码 1 inttoreal 60 t1 2 id3t1t2 3 id2t2t3 4 t3 id1 2020 1 25 22 1 2编译的阶段 代码优化 CodeOptimization 功能 对中间代码进行优化 提高时间与空间效率 2020 1 25 23 例 position initial rate 60 代码优化 1 inttoreal 60 t1 2 id3t1t2 3 id2t2t3 4 t3 id1 1 id360 0t1 2 id2t1id1 2020 1 25 24 1 2编译的阶段 代码生成 CodeGeneration 功能 生成目标代码机器代码 machinecode 可重定位的机器代码 relocatablemachinecode 汇编语言代码 assemblycode 2020 1 25 25 例 position initial rate 60 id360 0t1 id2t1id1 movfid3 R2mulf 60 0 R2movfid2 R1addfR2 R1movfR1 id1 目标代码生成 2020 1 25 26 1 2编译的阶段 符号表管理 Symbal TableManagement 功能 管理分析过程中得到的源程序中的标识符的各种信息记录源程序中使用的标识符 identifier 收集每个标识符的各种属性 attribute 信息 包括类型 type 作用域 scope 存储分配 storageallocated 信息 2020 1 25 27 1 2编译的阶段 出错处理 ErrorDetectionandReporting 功能 检查错误的位置检查错误的性质 词法 语法 语义 错误恢复 2020 1 25 28 1 2编译的阶段 一个例子语句的完整编译过程见P13 2020 1 25 29 1 3编译器的结构 编译器结构 2020 1 25 30 1 3编译器的结构 前端 Frontend 与后端 Backend 把编译程序分成前端和后端两部分前端 只依赖于源程序 独立于目标机器生成中间代码后端 依赖于目标机器 与源程序无关 只与中间语言有关从中间代码生成目标代码 2020 1 25 31 1 3编译器的结构 好处 提高开发编译器的效率取一个编译器的前端 重写它的后端以产生同一源语言在另一机器上的编译器不同的前端使用同一个后端 从而得到一个机器上的几个编译器 采用同一中间语言 2020 1 25 32 1 3编译器的结构 遍 Pass 对源程序或源程序中间表示的一次扫描 每一遍读入一个文件 执行一个或几个阶段的编译操作 并输出源程序的一个中间表示 2020 1 25 33 1 3编译器的结构 每一遍的输入是上一遍的输出 第一遍的输入是源程序正文 最后一遍的输出是目标代码遍数多 编译器结构清晰 但时间效率不高遍数少 编译速度快 但对机器的内存要求高 2020 1 25 34 1 4编译器的实现 世界上第一个编译程序是用什么语言书写的 用高级语言书写 没有编译器 如何编译 因此世界上第一个编译器只能是用机器语言开发的 2020 1 25 35 1 4编译器的实现 1 开发高级语言的编译器 自展技术直接用目标机器上的机器语言书写源语言的编译程序工作量太大用目标机器上的机器语言书写源语言的一个子集的编译程序 然后再用这个子集作为书写语言 实现源语言的编译程序 这就是自展技术 2020 1 25 36 1 4编译器的实现 2 用已有高级语言实现其它高级语言的编译程序 用语言L的编译器编译用L书写的另一高级语言的编译器例如 用C写PASCAL语言的编译器 然后编译 2020 1 25 37 1 4编译器的实现 编译器的构造工具词法分析器自动生成程序 LEX 2020 1 25 38 1 4编译器的实现 编译器的构造工具语法分析器自动生成程序 YACC 2020 1 25 39 1 5编译器的伙伴 一个语言处理系统P5Fig 1 3 2020 1 25 40 1 5编译器的伙伴 预处