《编译原理与技术》PPT课件.ppt

1 编译原理与技术 西安电子科技大学软件工程研究所刘坚 2 教学内容与要求 内容本课程的内容是建立在本科基础上的 尽量避免重复本科已有的内容 为了整个课程的一致性 而且由于学习方法的螺旋式特性 一些已学过的内容也会有所涉及 但会在原有基础上提高一步 重点放在本科课程中没有涉及的领域 主要介绍如下内容 并在兼顾理论与实现两个方面上进行讨论 编译程序编写工具 lex和yacc 学会使用lex和yacc进行程序设计 词 语法分析器核心算法 有限自动机的有效构造算法和LALR 1 分析器的构造算法 语法制导翻译 属性 L属性的自下而上计算 3 教学内容与要求 续1 类型检查 类型理论的发展 类型与类型检查 多态处理 封装与继承的实现技术等 类型系统的形式化方法简介 动态语义 指称语义入门 原理及其应用 代码优化 局部与循环优化 全局数据流分析技术 要求 做适当作业 期末统一收缴一次 并进行一次作业讲解 在课程总复习中进行 作业要求独立做 不计分 也可以不做 但不要抄 若合作做 则几个人合交一份 做上机作业 实现一个Pascal子集编译程序的全过程 两个学生一组 可以采用任何类似的Lex Yacc工具 上机作业计分 15 左右 重点考核上机报告和完成的软件 期终考试 闭卷考试 严格要求 按真实成绩给分 适当读参考文献 选一个课代表 4 参考文献 A V Aho J D Ullman TheTheory of Parsing Translation andCompiling VolumeI Parsing Prentice HallInc 1972A V Aho J D Ullman TheTheoryofParsing Translation andCompiling Volume Compiling Prentice HallInc 1973人民邮电出版社 Aho等 编译原理技术与工具 影印版 主要参考书 可作教材 上机作业题目 高等教育出版社 AndrewW Appel 现代编译程序实现 Java语言 影印版 机械工业出版社 StevenS Muchnick 高级编译器设计与实现 影印版 编译的相关理论与技术 5 参考文献 续 程序设计语言原理与设计 R W Sebesta ConceptsofProgrammingLanguages 机械工业出版社 影印版 TerrenceW Pratt MarvinV Zelkowitz ProgrammingLanguages DesignandImplementation thirdedition Prentice HallInternational Inc 1996DavidA Watt ProgrammingLanguageSyntaxandSemantics PrenticeHallInc 1991 编译器构造AxelT Schreiner H GeorgeFriedman Jr IntroductiontoCompilerConstructionwithUNIX PrenticeHall EnglewoodCliffs NJ07632 1985杨作梅译 JobnR Levine TonyMason DougBrown著 lex与yacc 机械工业出版社 2003 howtouselex yacc 互联网 6 第一章概述1 1要求与目的 紧密相关的三个领域程序设计语言的应用 程序设计 PLA 程序设计语言的翻译 编译器的构造 PLT 程序设计语言的设计 语法 语义 PLD CCC2002中的基本要求程序设计基础 PF 程序设计基本结构 算法与问题求解 基本数据结构 递归 事件驱动程序设计 PLA 程序设计语言 PL 程序设计语言概论 虚拟机 语言翻译简介 声明和类型 抽象机制 面向对象程序设计 以上是核心 函数程序设计 语言翻译系统 类型系统 程序设计语言的语义 程序设计语言的设计 以上是选修 PLA PLT PLD 7 1 2程序设计语言简述 深刻理解程序设计语言的应用 翻译 设计等方面的基本原理与方法 学会用编译器编写工具 LEX YACC 进行语言处理软件的设计 初步认识动态语义的形式化描述方法 1 2程序设计语言简述 编译器处理的对象是程序设计语言 因此在对程序设计语言了解的基础上和它们与编译器的关系上 有必要在以下几个方面再进行一些简单讨论 目的 8 1 2 1程序设计语言的发展 从年代看50s Fortran LISP COBOL Algol60 68 70s C Pascal Prolog Smalltalk Modula2 80s C Ada83 Ada95 Java Modula3 从抽象级别看过程 抽象数据类型 类 封装 继承 从工作方式看非结构化 结构化顺序 并行 基于消息传递单平台 跨平台从程序设计范型看过程式语言面向对象语言函数式语言非算法式语言 形式化 脚本式语言 9 1 2 2影响程序设计语言发展的因素 应用需求的推动 软件越做越大 功能越来越强 要求语言的抽象程度越来越高语言实现的限制 编译器是否好编写 典型的例子如Algol68和Ada83语言与编译器之间的相互推动与制约 自由格式 保留字 多继承等 1 2 3程序设计语言 好 的标准 属性 清晰 简单 与一致性 可读性 可编译性 可维护性对应用需求的自然实现 设计思想 自然过渡到语言描述支持抽象 x y integer x ya b arrayof a b 10 1 2 3程序设计语言 好 的标准 续 形式化验证 在源程序中通过加入前置条件 后置条件 根据运算不变量进行数学推理 从而检验程序的逻辑正确性 或者直接采用动态语义的形式化描述进行程序验证 建立数学模型 通过数学计算得到结果 看是否符合预期结果 静态阅读 风格好的程序通过阅读可以检查出部分逻辑错误 但不是全部的错误 实例测试 此方法是最常采用的 也是最成熟的方法 所需考虑的首要问题是如何生成实例才能达到程序的完全覆盖 以及如何进行测试 可移植性 任何一段源程序 在A机上编译运行 与在B机上编译运行 得到同样的结果 使用代价小 程序运行代价 程序翻译代价 编译 程序维护代价 整个程序的生命周期 便于程序验证 11 1 2 4环境对语言的影响 对编译器的要求 命令行 独立的 编辑 编译 运行等均是独立进行的 集成环境 编辑 编译 调试 运行 要求编译器提供编译和调试信息 如编译阶段和运行阶段不同错误分别对源程序的对应等 作为其他集成环境的一部分 如together J rose等 批处理环境 一般是CPU 存储器密集型 大型信息处理系统 日终处理 数据更新等 交互式环境 I O密集型 游戏 实时事务处理 如查询 交易等 嵌入式环境 实时响应关键型 控制系统 如生产线 军事武器 如飞机 火炮 舰船等 广泛的民用领域 如手机 数码相机等 分布式环境 如分布式系统 网络系统与Internet等 语言环境包括开发环境 1 2 与运行环境 3 6 12 1 2 4环境对语言的影响 续 运行环境的复杂性 多种环境的混合 如计算机集成制造系统 信息管理 生产控制 精密加工等 又如大型信息 金融系统 批处理 交互查询 以及网络与Internet等 13 1 3编译与解释 编译与解释是翻译语言的两种基本方法 解释器与编译器的主要区别在于程序运行时的控制权在解释器而不在目标程序 1 3 1各自的特点编译器 生成目标代码 运行速度快 空间占用少 效率高 动态特性和可移植性差 典型应用 批处理环境和嵌入式环境 解释器 动态特性 可移植性好 但是效率低 典型应用 交互式环境 分布式环境 1 3 2解释的动态交互特性可以胜任编译器无法胜任的工作Java虚拟机 编译器生成字节代码 虚拟机解释字节代码 其它语言的编译器若能生成Java的字节代码 结果如何 嵌入式SQL中查询语句的动态生成 解决了系统运行时才能确定数据的查询和处理 编译与解释共存 14 数据库查询问题 例1 1有一个数据库f table 存放各帐户的如下信息 account no 0000001 9999999name xxxxxxxxxxterm 3 6 9 12 24 36 60amount 100 00 9999999 99open date 19860101 当前值state flag normal closed lost 现有语句 EXECSQLSELECTname amountFROMf tableWHEREconditions 问题 当某个查询涉及m个表 每个表中平均有k个字段 每个字段平均有n个取值 最坏查询条件有多少个 如何写查询语句 考察f table 它有6个字段 每个字段分别取若干值 因此 从此表中查询时的查询条件 conditions 应该是6个字段中各值的集合元素个数的乘积 15 动态查询语句 对于任何一个应用系统 不可能枚举所有情况 并分别写出这些查询语句 唯一可行的方法是 运行时根据用户输入的查询字段和限制条件 拼接成一条类似下述的语句 EXECSQLSELECTf1 f2 FROMt1 t2 WHEREconditions 并把上述语句存放在一个字符串sql stmt中 而系统提供下述机制 EXECSQLPREAREsFROM sql stmt EXECSQLEXECUTEs DBMS的处理方法是 在运行系统中嵌入一段解释程序 它首先对sql stmt进行分析 检查是否语法语义正确 形成串s的中间表示 然后执行s 从而实现动态查询 若sql stmt EXECSQLSELECTname amountFROMf tableWHEREterm 12 则最后结果是查出所有存期大于一年的人的姓名和帐号 16 1 4程序设计语言的语法与语义 编译器的设计与实现 首先是对所要进行编译的语言进行描述 只有精确地描述语言 才能有效地实现语言 完整的程序设计语言 包括两部分描述 语法 syntax 和语义 semantics 描述 1 4 1语法程序设计语言的语法可以用上下文无关文法 Context freeGrammar CFG 描述 它是一种很好的描述方法 而且已有很成熟的技术构造十分有效的上下文无关文法的分析器 因此可以利用工具自动生成这类语法分析器 由于程序设计语言的语法是决定程序基本特性 如可读性 可维护性 可编译性等 的基础 因此程序设计语言语法设计的好坏就成为程序设计语言好坏的重要因素之一 随着程序设计语言的发展 语法的设计也形成了一些公认的准则 下述是一些典型的例子 17 1 4 1语法 续 自由书写格式 FORTRAN LEX YACC都不是自由书写格式 设立保留字 PL 1中 IFTHENTHENTHEN ELSE ELSEELSE THEN符合科学的 或历史形成的习惯性描述 C C 中 a b和a b其他语言 a b和a b避免超前扫描 FORTRAN DO5I 1 25 1 DO5I 1 25 2 对于DO5I 1 25 要超前扫描到 时才确定是赋值句 对于DO5I 1 25 要超前扫描到 时才确定是循环语句 减少可能的书写错误 C的注释 thisisacomment C 的注释 thisisacomment大小写不敏感 Pascal Ada等大小写不敏感 而C是敏感的 18 1 4 2语义 语义用于确定语言的意义 一般被分为两类 静态语义 staticsemantics 和动态语义 run timesemantics 静态语义静态语义主要是为了解决上下文无关文法不能应付的问题 它实际上是一组上下文限制 ContextualRestrictions 有些文献中就是把静态语义称为上下文限制 用来确定语法上正确的程序是否实际上也是有意义的 静态语义主要用于检查 被引用的标识符是否被说明 运算符和操作数是否类型兼容 操作数之间是否类型兼容等 过程调用时参数的个数及类型是否与过程定义时的相容 等等 19 1 4 2语义 续 动态语义动态语义用来规定程序做什么 也就是如何动作 原理上讲 无论是语法还是语义 均应进行形式化的描述 但是由于种种原因 语言的文本往往是对文法进行形式化描述 而对语义进行非形式化的描述 带来的问题是不能精确描述语义 20 1 4 3为什么要精确定义语义 对于一个语言的定义 一定要严格 准确 否则就不可能写出精确反映该语言实际意义的编译程序 例1 2对于语句 L gotoL 一般语言定义中只是简单说goto语句的作用是把控制转向其所指的标号所在位置 如果这样看 上述语句就是合法的 但是很明显 一旦程序执行起来就会陷入死循环 永不停机 在这种情况下 上述语句应该是非法的 在实际处理上 有的编译程序禁止这样的goto语句 而有的编译程序却不与理睬 例1 3对于Pascal语句 i0 and kdivi 10 该语句的语法完全正确 但是当语句被执行时 情况就不同了 考虑i 0的情况下 若编译时对条件语句采用的是短路计算 语句就可以正确执行 若不采用短路计算 则会出现致命错误 0作为除数 但在原始的Pascal定义中 对是否采用短路计算并没有明确规定 因此有的编译程序采用短路计算 而有的不采用 21 2005年2月25日 第一次课 22 1 4 3为什么要精确定义语义 续 从某种意义上讲 编译器本身实际上起着定义语言的作用 即对于某种语言 编译器选择如何接受和翻译该语言 这就使得一段程序在一个机器上可以正确运行 在另一个机器上就不可以 而这恰恰违背了通用程序设计语言的初衷 23 1 4 4语义的形式化描述 语义的形式化描述至少在下述三个方面起重要作用 精确描述语义程序的正确性验证程序自动生成 静态语义静态语义形式化描述最常采用的是属性文法 attributegrammars 它实际上是为产生式中的符号扩充属性 因此 也可以认为属性文法是对上下文无关文法的扩充 二者结合起来 完整地定义出合法的程序 由于属性文法对静态语义的描述并不是独立的 需要与文法捆绑在一起 因此被认为是半形式化的描述 静态语义的形式化描述 特别是类型系统的形式化描述 是当前的一个研究热点 下边来看两个属性文法的例子 24 静态语义 续 例1 4对于产生式E E1 E2 我们可以为E添加属性E type 类型 E val 值 等 然后 可以对属性进行下述计算 ifE1 type integerandE2 type integerthenE type integer gen E1 val E2 val E