西安电子科技大学编译原理.ppt

编 译 原 理,西安电子科技大学 软件工程研究所 刘 坚,2,题外话,一、本课程讨论的领域和希望达到的目的 11 领域 程序设计语言的应用程序设计（PLA） 程序设计语言的翻译编译器的构造（PLT） 程序设计语言的设计语法、语义（PLD）,12 CCC 2002 中国计算机科学与技术学科教程（China Computing Curricula 2002，CCC2002）提出的计算机科学与技术学科的知识体系，包括了14个基本的知识领域。与本课程相关的： 1程序设计基础（PF）：程序设计基本结构、算法与问题求解、基本数据结构、递归、事件驱动程序设计。（PLA） 2程序设计语言（PL）：程序设计语言概论、虚拟机、语言翻译简介、声明和类型、抽象机制、面向对象程序设计（以上是核心）；函数程序设计、语言翻译系统、类型系统、程序设计语言的语义、程序设计语言的设计（以上是选修）。（PLA、PLT、PLD）,3,题外话（续1）,13 目的 1了解PL的基本要素、工作原理、语言翻译的基本方法； 2用不同的PL进行程序设计，即自学计算机语言的能力； 3具备语言翻译的基本技能。,二、学习方法 21 本课程的特点 理论与实践并重 理论学习要严谨、方法掌握要灵活 提高自学能力（push与pull）,22 理论与技术的关系 适应飞速变化的技术的根本是注重基础理论学习 理论的演变是缓慢的、理论基础是相通的 相同的原理可以应用于不同的技术,例1 质能守恒、物质不灭、借贷 内存与外存速度的差异：虚存 虚盘,4,题外话（续2）,23 勤动手、多实践、提高学习能力 1 学到的知识是死的，总有过时的时候。只有通过学习知识提高学习能力，才是立于不败之地的保证。 2记笔记：好记性不如烂笔头，通过动手加深理解和记忆。 3做作业、做上机题：自己动手为主，参考“解答”为辅。,24 如何使用习题与上机题解答 合理利用“解答”有助于课程的学习。“解答”既不完全正确也不是最好的。 1习题解答：先做作业，后看解答。如不符，思考原因，找出最好的答案。 2上机解答：先看题目要求，根据要求自己设计并实现。如有困难，可部分参考解答。 3提倡学生独立思考，对发现解答错误并给出正确解法、做出选做题、做出上机题扩充部分者，给予加分奖励。（只给第一组，写明姓名、日期。加分按人平分） 4根据需要，可适当上一、两次习题课（学生预先提题目，若课时紧张则不占正课时间）。,5,题外话（续3）,三、其他 31 课代表与辅导 1课代表的职责：收缴作业；安排上机时间、联系上机事宜；反映同学意见；监督辅导老师的工作。 2辅导时间：每周一次，课代表与同学商量后确定。,32 作业与上机作业 1第二、五章收缴一次，第三、四章收缴两次。有独立见解的可直接交给主讲老师，包括，指出解答的错误并给出正确答案、选做题答案等。（仅以第一个收到的为准，包括上届） 2验收上机题，并收缴上机报告。报告内容根据个人对题目要求的理解写。,33 参考书目（重点） 1人民邮电出版社（影印本，编译原理 技术与工具）Aho等，Compilers - Principles, Techniques, and Tools，1986 2清华大学出版社，吕映芝等，“编译原理” 3清华大学出版社（影印版）Hopcroft等，Introduction to Automata Theory, Languages, and Computation(Second Edition),6,第一章 引言,1.1 从面向机器的语言到面向人类的语言 面向机器的语言：机器指令、汇编语言 面向人类的语言：通用程序设计语言、非过程式语言，等等, 计算机语言举例 例2 通用程序设计语言与汇编语言（包括机器指令） Pascal语句：x := a+b； 汇编指令：十六进制代码汇编指令 A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX,7, 计算机语言举例（续）,给出003号学生所选课程与成绩： Select 学号,姓名,课程名,成绩 from 学生,选课 where 学生.学号=“003” ;,例4 LEX的正规式： a-za-z0-9* return id; YACC的产生式：E : E + E | E * E | id;,例3 SQL 学生： 选课：,8, 按范型划分的程序设计语言,CCC2002PL： 1过程式语言、面向对象语言：通用程序设计语言，包括FORTRAN、Pascal、C/C+、Ada83/Ada95、Java等； 2函数语言：面向特点领域的、递归特性，典型代表：Lisp； 3说明性、非算法式语言：浓厚的数学特征，典型代表：LEX/YACC、SQL； 4脚本式语言：仅是一种安排，没有复杂的逻辑关系，典型代表：shell语言。,PROGRAMMING LANGUAGES Design and Implementation(影印，清华) (Terrence W.Pratt and Marvin V.Zelkowitz) 1. Simple Procedural Languages：FORTRAN C 2. Block-Structured Procedural Languages：Pascal 3. Object-Based Languages：Ada C+ Smalltalk 4. Functional Languages：LISP ML 5. Logic Programming Languages：Prolog,9, 其他面向特定应用领域的语言,1互连网应用：HTML、XML 2计算机辅助设计：MATLAB 3集成电路设计：VHDL、Verilog 4虚拟现实：VRML ,问题： 如何将形形色色的语言翻译成可以在计算机上运行的0、1串,10,1.2 语言之间的翻译,习惯称法： 汇编语言机器指令：汇编（或交叉汇编） 程序设计语言汇编语言或机器指令：编译（或解释） 高级语言之间：转换（或预编译） 逆向：反汇编、反编译,11,1.3 编译器与解释器,语言翻译的两种基本形态 1.先翻译后执行 2. 边翻译边执行,例5 假设有源程序：read(x); write(x=, x);,12,1.3 编译器与解释器（续）,特点： 1编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译； 2解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。 基本功能：二者相同； 所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。,13,1.4 编译器的工作原理与基本组成1.4.1 通用程序设计语言的主要成份,1从语言抽象的演变看： 过程抽象数据类型（ADT，程序包） 类 2共同特点：两大部分组成：声明操作完整定义 3以过程式语言为例：,声明性语句：提供操作对象的性质，如数据类型、值、作用域等； 操作性语句：确定操作的计算次序，完成实际操作。 过程头过程体过程定义,4编译器对两类语句的翻译： 声明：生成相应的环境，一般是配置存储空间。 操作：生成可执行的代码序列。 例6 一个Pascal过程,14,1.4.2 以阶段划分编译器,1自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰,2编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成 3编译器的阶段（逻辑模块划分）,4中间代码的重要作用,15,1.4.3 编译器各阶段的工作,例7 Pascal源程序语句如下： var x, y, z : real; x := y + z * 60;,（源程序）var x, y, z : real; x := y + z * 60;,（记号流）var id1, id2, id3 : real; id1 := id2+id3*60;,16,1.4.3 编译器各阶段的工作（续1）,中间代码的形式与作用： (序号)(op， arg1, arg2, result) result := arg1 op arg2,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),17,1.4.3 编译器各阶段的工作（续2）,(1) (itr, 60, , T1) (2) (*, id3, T1, T2) (3) (+, id2, T2, T3) (4) (:=, T3, , id1),(1) (*, id3, 60.0, T1) (2) (+, id2, T1, id1),MOVF id3, R2 MULF#60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1,R2 := id3 R2 := R2 * 60.0 R1 := id2 R1 := R1 + R2 id1 := R1 id1 := id2 + id3 * 60.0 x := y + z * 60;,18,1.4.3 编译器各阶段的工作（续3）,各阶段工作的归纳, 词法分析：识别单词，至少分以下几大类：关键字（保留字）、标识符、字面量、特殊符号； 语法分析：得到语言结构并以树的形式表示； 语义分析：考察结构正确的句子是否语义合法，可修改树结构； 中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成； （到目前为止，编译器与解释器可以一致）, 中间代码优化（可选）：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。 目标代码生成：不同形式的目标代码汇编、可重定位、内存形式（Load-and-Go）; 符号表管理：合理组织符号，便于各阶段查找、填写等； 出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。,19,1.4.4 编译器的分析/综合模式,1前端：语言结构的分析； 2后端：语言意义的分析与处理； 3中间代码：前端与后端的分界；,4编译器基础架构（Infrastructure） ：源代码的中间表示、一组前端、一组后端；,20,1.4.5 编译器扫描的遍数,1每个阶段将程序完整分析一遍的工作模式称为一遍扫描。早期编译器的一遍定义为从外存读入内存再写到外存； 2确定扫描遍数的因素： (a) 软、硬件条件，如内存太小，或全局优化 (b) 语言结构，如规定标识符的先声明后引用, x := f(a, b, c); function f(a:integer; b:integer): integer;,(c)编译技术，如拉链回填, goto lab1; lab1: ,21,1.5 编译器的编写,1直接使用汇编语言和程序设计语言； 2利用编译器编写工具：词/语法、语法制导翻译、代码生成、数据流分析等； 3基于编译器基础架构的编译器构造系统（开放式编译器，如GCC、SUIF等）。,GCC Home Page. http:/gcc.gnu.org. Gasta Homepage. SUIF Compiler System Home Page. http:/suif.stanford.edu,22,1.6 本章小结,1语言与语言的翻译 2编译器的基本组成（工作） 3编译器的分析/综合模式，编译器基础架构 4扫描遍数 5编译器的编写,其它 作业：教材中除标记*的全做；根据课程进度做；第二、五章交一次，第三、四章交两次； 课代表：收缴作业、联系上机、反映同学意见，等 答疑：每周一次，课代表与辅导教师商讨确定； 上机作业：交上机报告，作业由辅导教师验收。,23,第一章 结束,24,例6 有一Pascal的过程如下所示,(1) procedure sample(y: integer);过程头 (2) var x : integer;过程体（开始） (3) begin x := y; (4) if x100 then x := 0 (5) end;过程体（结束）,(1)是过程头，它是一个声明性的语句，为使用者提供调用信息，包括过程名、参数、返回值（如果有的话）等。（接口） (2)至(5)是过程体，它是一个语句序列。语句序列中既包括声明性语句也包括操作性语句。（实现） (2)是声明性语句，而(3)至(5)是操作性语句。 对于编译器来讲，它对声明性语句的处理一般是生成相应的环境（存储空间），而对操作性语句则是生成此环境中的可执行代码序列。 为了便于编译器的处理，操作性语句中使用的每个操作对象，均应在使用前声明，即符合先声明后引用的原则。,返回,