编译原理与技术631资料讲解.ppt

编译原理与技术西安电子科技大学 软件工程研究所刘坚1教学内容与要求 内容 本课程的内容是建立在本科基础上的，尽量避免重复本科已有的内容 为了整个课程的一致性，而且由于学习方法的螺旋式特性，一些已学过的内容也会有所涉及，但会在原有基础上提高一步重点放在本科课程中没有涉及的领域 主要介绍如下内容，并在兼顾理论与实现两个方面上进行讨论编译程序编写工具-lex和yacc：学会使用lex和yacc进行程序设计；词/语法分析器核心算法：有限自动机的有效构造算法和LALR（1）分析器的构造算法；语法制导翻译：属性、L属性的自下而上计算；2教学内容与要求（续1）类型检查：类型理论的发展、类型与类型检查、多态处理、封装与继承的实现技术等，类型系统的形式化方法简介；动态语义：指称语义入门，原理及其应用；代码优化：局部与循环优化，全局数据流分析技术 要求 做适当作业，期末统一收缴一次，并进行一次作业讲解（在课程总复习中进行）作业要求独立做（不计分）；也可以不做，但不要抄；若合作做，则几个人合交一份做上机作业，实现一个Pascal子集编译程序的全过程：两个学生一组，可以采用任何类似的Lex/Yacc工具上机作业计分（15左右），重点考核上机报告和完成的软件。

期终考试：闭卷考试严格要求（按真实成绩给分）适当读参考文献选一个课代表 3参考文献（续） 程序设计语言原理与设计 R.W.SebestaConcepts of Programming Languages,机械工业出版社（影印版） Terrence W.Pratt, Marvin V.Zelkowitz Programming Languages - Design and Implementation, third edition, Prentice-Hall International, Inc. 1996 David A. Watt “Programming Language Syntax and Semantics，”Prentice Hall Inc. 1991 编译器构造Axel T.Schreiner, H.George Friedman, Jr. Introduction to Compiler Construction with UNIX, Prentice Hall，Englewood Cliffs,NJ07632，1985杨作梅译，(Jobn R.Levine, Tony Mason & Doug Brown著), lex与yacc，机械工业出版社，2003 how to use lex&yacc（互联网）5 第一章 概述1.1 要求与目的 紧密相关的三个领域程序设计语言的应用程序设计（PLA）程序设计语言的翻译编译器的构造（PLT）程序设计语言的设计语法、语义（PLD） CCC 2002中的基本要求 程序设计基础（PF）：程序设计基本结构、算法与问题求解、基本数据结构、递归、事件驱动程序设计。

PLA）程序设计语言（PL）：程序设计语言概论、虚拟机、语言翻译简介、声明和类型、抽象机制、面向对象程序设计（以上是核心）；函数程序设计、语言翻译系统、类型系统、程序设计语言的语义、程序设计语言的设计（以上是选修）PLA、PLT、PLD） 61.2 程序设计语言简述深刻理解程序设计语言的应用、翻译、设计等方面的基本原理与方法；学会用编译器编写工具（LEX/YACC）进行语言处理软件的设计；初步认识动态语义的形式化描述方法 1.2 程序设计语言简述 编译器处理的对象是程序设计语言，因此在对程序设计语言了解的基础上和它们与编译器的关系上，有必要在以下几个方面再进行一些简单讨论 目的71.2.1 程序设计语言的发展1. 从年代看50s：Fortran、LISP、COBOL、Algol 60/68.70s：C、Pascal、Prolog、Smalltalk、Modula 2.80s：C+、Ada83/Ada95、Java、Modula 3.2. 从抽象级别看过程抽象数据类型类（封装继承）3. 从工作方式看非结构化结构化顺序并行基于消息传递单平台跨平台 4. 从程序设计范型看过程式语言面向对象语言函数式语言非算法式语言（形式化）脚本式语言 81.2.2 影响程序设计语言发展的因素1. 应用需求的推动：软件越做越大，功能越来越强，要求语言的抽象程度越来越高2. 语言实现的限制（编译器是否好编写）：典型的例子如Algol68和Ada833. 语言与编译器之间的相互推动与制约：自由格式，保留字，多继承等。

1.2.3 程序设计语言“好”的标准（属性） 清晰、简单、与一致性：可读性、可编译性、可维护性 对应用需求的自然实现：设计思想自然过渡到语言描述 支持抽象：x, y : integer x+y a, b : array of . a+b?91.2.3 程序设计语言“好”的标准（续）形式化验证：在源程序中通过加入前置条件、后置条件，根据运算不变量进行数学推理，从而检验程序的逻辑正确性；或者直接采用动态语义的形式化描述进行程序验证（建立数学模型，通过数学计算得到结果，看是否符合预期结果）静态阅读：风格好的程序通过阅读可以检查出部分逻辑错误，但不是全部的错误实例测试：此方法是最常采用的、也是最成熟的方法所需考虑的首要问题是如何生成实例才能达到程序的完全覆盖，以及如何进行测试 可移植性：任何一段源程序，在A机上编译运行，与在B机上编译运行，得到同样的结果 使用代价小：程序运行代价、程序翻译代价（编译）、程序维护代价（整个程序的生命周期） 便于程序验证101.2.4 环境对语言的影响（对编译器的要求）1. 命令行（独立的）：编辑、编译、运行等均是独立进行的；2. 集成环境：编辑编译调试运行（要求编译器提供编译和调试信息，如编译阶段和运行阶段不同错误分别对源程序的对应等）。

作为其他集成环境的一部分，如together-J、rose等3. 批处理环境（一般是CPU/存储器密集型）：大型信息处理系统：日终处理、数据更新等4. 交互式环境（I/O密集型）：游戏、实时事务处理（如查询、交易等）5. 嵌入式环境（实时响应关键型）：控制系统（如生产线）军事武器（如飞机、火炮、舰船等）广泛的民用领域，如、数码相机等6. 分布式环境：如分布式系统、网络系统与Internet等 语言环境包括开发环境（1，2）与运行环境（36）111.2.4 环境对语言的影响（续） 运行环境的复杂性 多种环境的混合，如计算机集成制造系统：信息管理、生产控制、精密加工等；又如大型信息、金融系统：批处理、交互查询，以及网络与Internet等121.3 编译与解释 编译与解释是翻译语言的两种基本方法解释器与编译器的主要区别在于程序运行时的控制权在解释器而不在目标程序1.3.1 各自的特点编译器：生成目标代码，运行速度快、空间占用少，效率高；动态特性和可移植性差(典型应用：批处理环境和嵌入式环境)解释器：动态特性、可移植性好，但是效率低（典型应用：交互式环境、分布式环境）1.3.2 解释的动态交互特性可以胜任编译器无法胜任的工作Java虚拟机：编译器生成字节代码，虚拟机解释字节代码。

其它语言的编译器若能生成Java的字节代码，结果如何？）嵌入式SQL中查询语句的动态生成：解决了系统运行时才能确定数据的查询和处理编译与解释共存13数据库查询问题例1.1有一个数据库f_table，存放各帐户的如下信息： account_no：0000001-9999999 name： xxxxxxxxxx term： 3，6，9，12，24，36，60 amount： 100.009999999.99 open_date： 19860101当前值 state_flag：normal，closed，lost，.现有语句： EXEC SQL SELECT name, amount FROM f_table WHERE conditions问题：当某个查询涉及m个表，每个表中平均有k个字段，每个字段平均有n个取值，最坏查询条件有多少个？如何写查询语句？ 考察f_table，它有6个字段，每个字段分别取若干值，因此，从此表中查询时的查询条件(conditions)应该是6个字段中各值的集合元素个数的乘积14动态查询语句 对于任何一个应用系统，不可能枚举所有情况，并分别写出这些查询语句唯一可行的方法是：运行时根据用户输入的查询字段和限制条件，拼接成一条类似下述的语句： EXEC SQL SELECT f1, f2, . FROM t1,t2,. WHERE conditions;并把上述语句存放在一个字符串sql_stmt中。

而系统提供下述机制： EXEC SQL PREARE s FROM :sql_stmt; EXEC SQL EXECUTE s .; DBMS的处理方法是：在运行系统中嵌入一段解释程序，它首先对sql_stmt进行分析（检查是否语法语义正确），形成串s的中间表示，然后执行s，从而实现动态查询若sql_stmt=“EXEC SQL SELECT name, amount FROM f_table WHERE term12”则最后结果是查出所有存期大于一年的人的姓名和帐号151.4 程序设计语言的语法与语义 编译器的设计与实现，首先是对所要进行编译的语言进行描述，只有精确地描述语言，才能有效地实现语言 完整的程序设计语言，包括两部分描述：语法（syntax）和语义（semantics）描述1.4.1 语法 程序设计语言的语法可以用上下文无关文法（Context-free Grammar，CFG）描述，它是一种很好的描述方法，而且已有很成熟的技术构造十分有效的上下文无关文法的分析器，因此可以利用工具自动生成这类语法分析器 由于程序设计语言的语法是决定程序基本特性（如可读性、可维护性、可编译性等）的基础，因此程序设计语言语法设计的好坏就成为程序设计语言好坏的重要因素之一。

随着程序设计语言的发展，语法的设计也形成了一些公认的准则,下述是一些典型的例子161.4.1 语法（续） 自由书写格式：FORTRAN、LEX/YACC都不是自由书写格式 设立保留字：PL/1中：IF THEN THEN THEN=ELSE; ELSE ELSE=THEN 符合科学的、或历史形成的习惯性描述：C/C+中：a=b和a=b其他语言：a:=b和a=b 避免超前扫描：FORTRAN：DO 5 I = 1.25 (1) DO 5 I = 1, 25 (2)对于DO5I = 1.25;要超前扫描到.时才确定是赋值句对于DO 5 I = 1,25;要超前扫描到,时才确定是循环语句 减少可能的书写错误：C的注释：/* this is a comment */C+的注释：/ this is a comment 大小写不敏感：Pascal、Ada等大小写不敏感，而C是敏感的171.4.2 语义 语义用于确定语言的意义，一般被分为两类：静态语义（static semantics）和动态语义（run-time semantics） 静态语义 静态语义主要是为了解决上下文无关文法不能应付的问题，它实际上是一组上下文限制（Contextual Restrictions，有些文献中就是把静态语义称为上下文限制），用来确定语法上正确的程序是否实际上也是有意义的。

静态语义主要用于检查：被引用的标识符是否被说明;运算符和操作数是否类型兼容，操作数之间是否类型兼容等；过程调用时参数的个数及类型是否与过程定义时的相容，等等181.4.2 语义（续） 动态语义 动态语义用来规定程序做什么，也就是如何动作 原理上讲，无论是语法还是语义，均应进行形式化的描述但是由于种种原因，语言的文本往往是对文法进行形式化描述，而对语义进行非形式化的描述，带来的问题是不能精确描述语义191.4.3 为什么要精确定义语义 对。