编译原理ch1.ppt

2020 1 13 华东师大信息学院计算机科学技术系 1 编译原理 华东师大计算机科学技术系杨宗源2013年 PrinciplesofCompiler 2020 1 13 华东师大信息学院计算机科学技术系 2 课程目的 学习方法和基本要求 性质专业基础课程 是计算机科学技术的基础前导课程离散数学 程序设计语言 数据结构 操作系统目的编译程序是计算机系统的基本系统软件 本课程主要介绍设计 实现编译程序时所涉及的基本原理 基本方法和基本技术 通过本课程的学习和上机实践使学生掌握构造高级程序设计语言编译程序的基本原理 结构 设计与实现技术 培养学生了解和掌握编译原理的基本原理及典型技术并具备相当的应用能力 2020 1 13 华东师大信息学院计算机科学技术系 3 课程目的 学习方法和基本要求 知识形式语言与形式语言处理 自动机理论 形式描述方法 程序自动生成方法 数据流和控制分析方法方法 系统性 前后的连接 融会贯通 避免孤立化 实践性 可实现的系统软件 理论与实践相结合 多样性 实现技术多样 表示形式多样 基本性 举一反三 在掌握多种方法 算法和表示形式的同时正确把握基本性 2020 1 13 华东师大信息学院计算机科学技术系 4 课程目的 学习方法和基本要求 本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知 分析 设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型 2020 1 13 华东师大信息学院计算机科学技术系 5 课程目的 学习方法和基本要求 主要特点抽象和形式化 理论证明和构造性前半部分 词法 语法分析 实现技术 形式化后半部分 语义分析 代码优化 生成 希望 2020 1 13 华东师大信息学院计算机科学技术系 6 教材及主要参考书目 教材刘铭等 编译原理 电子工业出版社 第3版 参考书目侯文永 张冬茉 编译原理 电子工业出版社2002年杨宗源 编译原理习题精选 分析与解答 清华大学出版社2003徐国定杨宗源 编译程序构造 华东师范大学出版社1989 10KennethC Loudon CompilerConstruction PrinciplesandPractice PwsPublishingCompany1997AlfredV AhoRaviSethiJeffreyD Ullman CompilersPrinciples Techniques andTools Addison Wesley Reading Mass 1986CharlesN FischerRichardJ LeBlanc Jr CraftingACompiler TheBenjamin CummingsPublishingCompany1988DickGrune HenriEBal CerielJHJacobs KoenGLangendoen ModernCompilerDesign JohnWiley Sons Ltd 2000网站 2020 1 13 华东师大信息学院计算机科学技术系 7 第一章编译概述 1 1语言处理与编译程序1 1 1程序设计语言的引入是解决人机对话鸿沟的一个里程碑 2020 1 13 华东师大信息学院计算机科学技术系 8 语言处理与编译程序 1 1 2程序设计语言分类程序设计语言是遵守一定规范的 描述 计算 Computing 过程的形式语言 一般可以划分 低级语言低级语言是面向机器的语言 它是为特定的计算机系统设计的语言 如 机器指令 汇编语言是低级语言 高级语言高级语言是与具体计算机无关的 通用 语言 它更接近于人类的自然语言和数学表示 如 FORTRAN Pascal C JAVA等等高级语言 其他语言如 控制命令语言 查询语言 脚本语言等 2020 1 13 华东师大信息学院计算机科学技术系 9 语言处理与编译程序 1 1 3语言处理程序翻译程序 Translator 翻译程序是一种语言处理程序 它将输入的用程序设计语言 源语言 书写的程序 源程序 转换为等价的用另一种语言书写 目标语言 的程序 目标程序 若源语言是汇编语言 目标语言是机器语言 称这种翻译程序为汇编程序 若源语言是高级语言 目标语言是低级语言 称这种翻译程序为编译程序 若源语言是高级语言 目标语言是另一种高级语言 称这种翻译程序为转换程序 2020 1 13 华东师大信息学院计算机科学技术系 10 语言处理与编译程序 解释程序 Interpreter 解释程序是一种语言处理程序 它对源程序逐个语句地进行分析 并根据每个语句的含义执行语句指定的功能 编译程序 翻译程序 与解释程序主要的不同是 编译程序将先生成目标程序 再执行目标程序 而解释程序不生成目标程序 边翻译 边执行 形象地说 这类似于自然语言中的 笔译 与 口译 翻译与解释相结合的方法是一种不错的方法 即先将源程序翻译为中间语言表示的代码 然后再解释执行 例如 JAVA语言的源程序翻译为一种称为Bytecode的中间代码 再通过JAVA虚拟机解释执行 2020 1 13 华东师大信息学院计算机科学技术系 11 语言处理与编译程序 编译程序的一个实例FACOMM 340的C语言编译器 2020 1 13 华东师大信息学院计算机科学技术系 12 语言处理与编译程序 相关说明CV CPP与语言 机器相关 ASM LINK与机器相关 而CSA CSG组成了编译程序的主体 称CSA为编译器的前端独立于目标语言 称CSG为编译器的后端面向目标语言 遍在编译过程中 扫描一遍源程序 输入文件 经处理形成一个输出文件 称为一遍 合理地决定 遍数 可提高效率 时 空 LINK程序linker 连接程序 多个不同的目标文件一个可执行文件loader 装配程序 相对地址绝对地址 2020 1 13 华东师大信息学院计算机科学技术系 13 语言处理与编译程序 编译器所在的集成环境编辑器 Editor 调试器 Debugger 描述器 Profiler 项目管理器 ProjectManager 等 2020 1 13 华东师大信息学院计算机科学技术系 14 编译程序概貌 1 2编译过程和编译程序的基本结构抽象地看 2020 1 13 华东师大信息学院计算机科学技术系 15 这是一个逻辑模型 独立于具体的语言和机器 2020 1 13 华东师大信息学院计算机科学技术系 16 以赋值语句pos init rate 60为例了解编译的全过程词法分析 LexicalAnalysis 功能 a 扫描源程序的字符串 识别出意义独立的最小的词法单位 单词 Token b 删除注解 空格 回车及与输入介质有关的符号 c 报告词法错误 如上述赋值语句经过词法分析后输出为如下单词 ID pos OP ID init OP ID rate OP CONST 60 2020 1 13 华东师大信息学院计算机科学技术系 17 语法分析 SyntaxAnalysis 功能 对输入的单词串 按程序设计语言的语法规则 检查源程序句法正确性 例如某语言关于赋值语句的语法规则是 赋值语句是 ID EXPID CONST是EXP若EXP1和EXP2是EXP 则EXP1 EXP2 EXP1 EXP2 EXP1 是EXP 可以通过自顶向下或自底向上的句法分析方法 建立分析树 又称句法树 推导树 进行句法分析 2020 1 13 华东师大信息学院计算机科学技术系 18 对此例 分析树为 2020 1 13 华东师大信息学院计算机科学技术系 19 语义分析 SemanticAnalysis 功能 检查语义的正确性 完成语义解释及必要的转换 例如 此例中各变量的数据类型是float 由于rate与60的类型不同就应该进行转换 即将60转换为60 0 中间代码生成 IntermediateCodeGeneration 功能 将单词串转换为等价的中间代码串 常见的中间代码有 四元组 三元组 逆波兰 后缀 表示等 上例中的赋值语句可翻译为 四元组形式 float 60 t1 ID rate t1 t2 ID init t2 t3 t3 ID pos 其中t1 t2 t3是临时变量 ID x是x在符号表中的位置 2020 1 13 华东师大信息学院计算机科学技术系 20 代码优化 CodeOptimization 功能 以提高目标代码运行的时 空间效率为目的的对中间代码进行等价变换 常见的方法有 删除无用赋值和多余运算 常量合并 运算强度削弱 代码外提 复写传播等等 此例中的中间代码通过优化可为 ID rate 60 0 t1 ID init t1 t2 t2 ID pos 代码生成 CodeGeneration 功能 将中间代码串转换为汇编代码或机器指令 2020 1 13 华东师大信息学院计算机科学技术系 21 代码生成 此例中优化后的中间代码可生成如下的汇编代码 LOADR0 drate R3 LOADR1 d60 0 R3 MULTR0 R1LOADR0 dinit R3 ADDR0 R1STORER1 dpos R3 其中 R3是基地址寄存器dx是x的位移相对于R3的内容 2020 1 13 华东师大信息学院计算机科学技术系 22 出错处理 ErrorHandle 功能 显示出错的位置 性质 限制出错的影响 为尽可能多地发现错误做些恢复工作 符号表管理 Symbol TableManagement 功能 管理源程序中各种数据对象及其各种属性 提供包括生成 查询 更新等各种功能 2020 1 13 华东师大信息学院计算机科学技术系 23 编译程序的生成方法 1 3编译程序的生成方法1 3 1手工生成完全由人采用低级语言开发编译程序 工作量很大 1 3 2自动生成利用自动生成工具开发编译程序 如 L