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

《西安电子科技大学编译原理》由会员分享，可在线阅读，更多相关《西安电子科技大学编译原理（24页珍藏版）》请在金锄头文库上搜索。

1、编 译 原 理西安电子科技大学 软件工程研究所 刘 坚题外话 一、本课程讨论的领域和希望达到的目的 11 领域 程序设计语言的应用程序设计（PLA） 程序设计语言的翻译编译器的构造（PLT） 程序设计语言的设计语法、语义（PLD）12 CCC 2002 中国计算机科学与技术学科教程（China Computing Curricula 2002，CCC2002）提出的计算机科学与技术学科的知识体系，包括 了14个基本的知识领域。与本课程相关的：1程序设计基础（PF）：程序设计基本结构、算法与问题求解 、基本数据结构、递归、事件驱动程序设计。（PLA）2程序设计语言（PL）：程序设计语言概论、虚拟

2、机、语言翻译 简介、声明和类型、抽象机制、面向对象程序设计（以上是核心） ；函数程序设计、语言翻译系统、类型系统、程序设计语言的语义 、程序设计语言的设计（以上是选修）。（PLA、PLT、PLD） 2题外话（续1）13 目的 1了解PL的基本要素、工作原理、语言翻译的基本方法； 2用不同的PL进行程序设计，即自学计算机语言的能力； 3具备语言翻译的基本技能。 二、学习方法 21 本课程的特点理论与实践并重 理论学习要严谨、方法掌握要灵活 提高自学能力（push与pull）22 理论与技术的关系 适应飞速变化的技术的根本是注重基础理论学习 理论的演变是缓慢的、理论基础是相通的 相同的原理可以应用

3、于不同的技术例1 质能守恒、物质不灭、借贷 内存与外存速度的差异：虚存 虚盘3题外话（续2）23 勤动手、多实践、提高学习能力 1 学到的知识是死的，总有过时的时候。只有通过学习知识提高 学习能力，才是立于不败之地的保证。 2记笔记：好记性不如烂笔头，通过动手加深理解和记忆。 3做作业、做上机题：自己动手为主，参考“解答”为辅。 24 如何使用习题与上机题解答合理利用“解答”有助于课程的学习。“解答”既不完全正确 也不是最好的。 1习题解答：先做作业，后看解答。如不符，思考原因，找出最好 的答案。 2上机解答：先看题目要求，根据要求自己设计并实现。如有困 难，可部分参考解答。 3提倡学生独立思

4、考，对发现解答错误并给出正确解法、做出选 做题、做出上机题扩充部分者，给予加分奖励。（只给第一组，写 明姓名、日期。加分按人平分）4根据需要，可适当上一、两次习题课（学生预先提题目，若课 时紧张则不占正课时间）。 4题外话（续3 ）三、其他31 课代表与辅导 1课代表的职责：收缴作业；安排上机时间、联系上机事宜；反映 同学意见；监督辅导老师的工作。 2辅导时间：每周一次，课代表与同学商量后确定。 32 作业与上机作业 1第二、五章收缴一次，第三、四章收缴两次。有独立见解的可直 接交给主讲老师，包括，指出解答的错误并给出正确答案、选做题 答案等。（仅以第一个收到的为准，包括上届） 2验收上机题，

5、并收缴上机报告。报告内容根据个人对题目要求 的理解写。33 参考书目（重点） 1人民邮电出版社（影印本，编译原理 技术与工具）Aho等， Compilers - Principles, Techniques, and Tools，1986 2清华大学出版社，吕映芝等，“编译原理” 3清华大学出版社（影印版）Hopcroft等，Introduction to Automata Theory, Languages, and Computation(Second Edition)5第一章 引言 1.1 从面向机器的语言到面向人类的语言面向机器的语言：机器指令、汇编语言 面向人类的语言：通用程序设计语

6、言、非过程式语言，等等计算机语言举例例2 通用程序设计语言与汇编语言（包括机器指令） Pascal语句：x := a+b； 汇编指令：十六进制代码汇编指令 A10002 MOV AX, A 8B1E0202 MOV BX, B 01D8 ADD AX, BX A30402 MOV X, AX 6计算机语言举例（续）给出003号学生所选课程与成绩 ： Select 学号,姓名,课程名,成绩 from 学生,选课 where 学生.学号=“003” ;例4 LEX的正规式： a-za-z0-9* return id;YACC的产生式：E : E + E | E * E | id; 例3 SQL 学

7、生： 选课：学号姓名性别001 张梧男 002 李煦 男003 王沁 女004刘荔女学号课程代码课程名成绩0010104离散数学80 0010205数据结构90 0030104离散数学85 0030205数据结构95学号姓名课程名成绩003王沁离散数学85 003王沁数据结构957按范型划分的程序设计语言CCC2002PL：1过程式语言、面向对象语言：通用程序设计语言，包括 FORTRAN、Pascal、C/C+、Ada83/Ada95、Java等；2函数语言：面向特点领域的、递归特性，典型代表：Lisp；3说明性、非算法式语言：浓厚的数学特征，典型代表： LEX/YACC、SQL；4脚本式语

8、言：仅是一种安排，没有复杂的逻辑关系，典型代 表：shell语言。PROGRAMMING LANGUAGES Design and Implementation(影印，清华 )(Terrence W.Pratt and Marvin V.Zelkowitz)1. Simple Procedural Languages：FORTRAN C 2. Block-Structured Procedural Languages：Pascal3. Object-Based Languages：Ada C+ Smalltalk4. Functional Languages：LISP ML5. Logic P

9、rogramming Languages：Prolog8其他面向特定应用领域的语言1互连网应用：HTML、XML 2计算机辅助设计：MATLAB 3集成电路设计：VHDL、Verilog 4虚拟现实：VRML 问题：如何将形形色色的语言翻译成可以在计算机上运行的0、1串91.2 语言之间的翻译 习惯称法：汇编语言机器指令：汇编（或交叉汇编）程序设计语言汇编语言或机器指令：编译（或解释）高级语言之间：转换（或预编译）逆向：反汇编、反编译101.3 编译器与解释器 语言翻译的两种基本形态 1.先翻译后执行 2. 边翻译边执行 例5 假设有源程序：read(x); write(“x=“, x); 1

10、11.3 编译器与解释器（续 ）特点： 1编译器：工作效率高，即时间快、空间省；交互性与动态特性 差、可移植性差。大多数PL采用此种方法翻译； 2解释器：工作效率低，即时间慢、空间费；交互性与动态特性 好、可移植性好。早期的Basic和现在的Java等。 基本功能：二者相同； 所采用的技术：从翻译的角度来讲，两种方式所涉及的原理 、方法、技术相似。121.4 编译器的工作原理与基本组成 1.4.1 通用程序设计语言的主要成份1从语言抽象的演变看： 过程抽象数据类型（ADT，程序包） 类 2共同特点：两大部分组成：声明操作完整定义 3以过程式语言为例：声明性语句：提供操作对象的性质，如数据类型、

11、值、作用域等； 操作性语句：确定操作的计算次序，完成实际操作。 过程头过程体过程定义 4编译器对两类语句的翻译：声明：生成相应的环境，一般是配置存储空间。操作：生成可执行的代码序列。 例6 一个Pascal过程 131.4.2 以阶段划分编译器 1自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰 2编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成 3编译器的阶段（逻辑模块划分 ）4中间代码的重要作用141.4.3 编译器各阶段的工作 例7 Pascal源程序语句如下 ：var x, y, z : real;x := y + z * 60;（源程序）var x

12、, y, z : real; x := y + z * 60; （记号流）var id1, id2, id3 : real; id1 := id2+id3*60; 151.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) 161.4.3 编译器各阶段的工作（续2） (1) (itr, 60, , T1) (2) (*,

13、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; 171.4.3 编译器各阶段的工作（续3）各阶段工作的归纳 词法分析：

14、识别单词，至少分以下几大类：关键字（保留 字）、标识符、字面量、特殊符号；语法分析：得到语言结构并以树的形式表示；语义分析：考察结构正确的句子是否语义合法，可修改树 结构；中间代码生成（可选）：生成一种既接近目标语言，又与 具体机器无关的表示，便于优化与代码生成；（到目前为止，编译器与解释器可以一致） 中间代码优化（可选）：局部优化、循环优化、全局优化 等；优化实际上是一个等价变换，变换前后的指令序列完成同样的 功能，但是，在占用的空间上和程序执行的时间上都更省、更有效 。目标代码生成：不同形式的目标代码汇编、可重定位、 内存形式（Load-and-Go）;符号表管理：合理组织符号，便于各阶段

15、查找、填写等；出错处理：错误的种类词法错、语法错、静态语义错、 动态语义错。181.4.4 编译器的分析/综合模式 1前端：语言结构的分析； 2后端：语言意义的分析与处理；3中间代码：前端与后端的分界；4编译器基础架构 （Infrastructure） ：源代码的中间表示 、一组前端、一组后 端；191.4.5 编译器扫描的遍数 1每个阶段将程序完整分析一遍的工作模式称为一遍扫描。早期编 译器的一遍定义为从外存读入内存再写到外存； 2确定扫描遍数的因素： (a) 软、硬件条件，如内存太小，或全局优化 (b) 语言结构，如规定标识符的先声明后引用 x := f(a, b, c); function f(a:integer; b:integer):integer; (c)编译技术，如拉链回填 goto lab1; lab1: 201.5 编译器的编写 1直接使用汇编语言和程序设计语言；2利用编译器编写工具：词/语法、语法制导翻译、代码生成 、数据流分析等； 3基于编译器基础架构的编译器构造系统（开放式编译器，如 GCC、SUIF等）。 GCC Home Page. http:/gcc.gnu.org. Gasta Homepage. http:/gasta.sourceforge.ne