编译原理01讲述.ppt

编 译 原 理 西安电子科技大学 软件工程研究所 张立勇 1 题外话 一、本课程讨论的领域和希望达到的目的 1．2 CCC 2002 中国计算机科学与技术学科教程（China Computing Curricula 2002，CCC2002）提出的计算机科学与技术学科的知识体系，包括 了14个基本的知识领域与本课程相关的： 1．程序设计基础（PF）：程序设计基本结构、算法与问题求解 、基本数据结构、递归、事件驱动程序设计PLA） 2．程序设计语言（PL）：程序设计语言概论、虚拟机、语言翻 译简介、声明和类型、抽象机制、面向对象程序设计（以上是核心 ）；函数程序设计、语言翻译系统、类型系统、程序设计语言的语 义、程序设计语言的设计（以上是选修）PLA、PLT、PLD） 1．1 领域 程序设计语言的应用－程序设计（PLA） 程序设计语言的翻译－编译器的构造（PLT） 程序设计语言的设计－语法、语义（PLD） 2 题外话（续1） 1．3 目的 1．了解PL的基本要素、工作原理、语言翻译的基本方法； 2．用不同的PL进行程序设计，即自学计算机语言的能力； 3．具备语言翻译的基本技能 二、学习方法 2．1 本课程的特点 •理论与实践并重 •理论学习要严谨、方法掌握要灵活 •提高自学能力（push与pull） 2．2 理论与技术的关系 •适应飞速变化的技术的根本是注重基础理论学习 •理论的演变是缓慢的、理论基础是相通的 •相同的原理可以应用于不同的技术 3 题外话（续2） 2．3 勤动手、多实践、提高学习能力 •学到的知识是死的，总有过时的时候。

只有通过学习知识 提高学习能力，才是立于不败之地的保证 •记笔记：好记性不如烂笔头，通过动手加深理解和记忆 •做作业、做上机题：自己动手为主，参考“解答”为辅 2．4 如何使用习题与上机题解答 •合理利用“解答”有助于课程学习解答”既不完全正 确也不是最好的 •习题解答：先做作业，后看解答如不符，思考原因，找 出最好答案 •上机解答：先看题目要求，根据要求自己设计并实现如 有困难，部分参考解答 •提倡学生独立思考，对发现解答错误并给出正确解法、做 出选做题和上机题扩充部分者，给予加分奖励只给第 一组，写明姓名、日期加分按人平分） •根据需要上习题课 4 题外话（续3） 三、其他 3．1 课代表与 •课代表的职责：收缴作业；安排上机时间、联系上机事宜； 反映同学意见；监督老师的工作 •时间：每周一次，课代表与同学商量后确定 3．2 作业与上机作业 •第二、五章收缴一次，第三、四章收缴两次有独立见解的 可直接交给主讲老师，包括指出解答的错误并给出正确答案 、选做题答案等仅以第一个收到的为准，包括上届） •验收上机题，并收缴上机报告报告内容根据个人对题目要 求的理解写 5 题外话（续4） 中文： •清华大学出版社，吕映芝等，“编译原理” •国防工业出版社，陈火旺等，“程序设计语言编译原理”（ 第三版） •西北工业大学出版社，蒋立源等，“编译原理” 3．3 参考书目 英文： •人民邮电出版社， Aho等， “编译原理 技术与工具”（影印 版） •高等教育出版社，Andrew W.Appel，“现代编译程序实现－ Java语言”（影印版） •机械工业出版社，Steven S.Muchnick，“高级编译器设计 与实现” （影印版） •清华大学出版社，Hopcroft等，“自动机理论、语言和计算 机导论”（影印版） 6 第一章 引言 1.1 从面向机器的语言到面向人类的语言 面向机器的语言：机器指令、汇编语言 面向人类的语言：通用程序设计语言、非过程式语言，等等 例1 :通用程序设计语言与汇编语言（包括机器指令） Pascal语句：x := a+b； C++语句： x = a+b； 汇编指令：十六进制代码汇编指令 A10002 MOV AX, [A] 8B1E0202 MOV BX, [B] 01D8 ADD AX, BX A30402 MOV [X], AX 计算机语言举例 7 计算机语言举例（续1） 给出003号学生所选课程与成绩: Select 学号,姓名,课程名,成绩 from 学生,选课 where 学生.学号=“003” ; 例2 SQL 学生： 选课： 学号姓名性别 001 张梧男 002 李煦 男 003 王沁 女 004刘荔女 学号课程代码课程名成绩 0010104离散数学80 0010205数据结构90 0030104离散数学85 0030205数据结构95 学号姓名课程名成绩 003王沁离散数学85 003王沁数据结构95 8 计算机语言举例（续2） 例3： LEX的正规式：char(char|digit)* return id Yacc的产生式：E : E '+' E | E '*' E | id 例4：Unix的shell命令 SHELL=/bin/sh # include env_precomp.mk CPDIR = /u/pbsrc/chp ORAHOME = /oracle/app/oracle/product/734 . 9 按范型划分的程序设计语言 CCC2002－PL： 1. Simple Procedural Languages：FORTRAN C 2. Block-Structured Procedural Languages：Pascal 3. Object-Based Languages：Ada C++ Smalltalk 4. Functional Languages：LISP ML Haskell OCaml 5. Logic Programming Languages：Prolog 清华大学出版社， Terrence W.Pratt等，“PROGRAMMING LANGUAGES Design and Implementation“(影印版) 1.过程式语言、面向对象语言：通用程序设计语言，包括 FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等； 2. 函数语言：面向特点领域的、递归特性，典型代表：Lisp； 3. 说明性、非算法式语言：浓厚的数学特征，典型代表： LEX/YACC、SQL； 4. 脚本式语言：仅是一种安排，没有复杂的逻辑关系，典型代 表：shell语言。

10 其他面向特定应用领域的语言 1．互连网应用：HTML、XML 2．计算机辅助设计：MATLAB 3．集成电路设计：VHDL、Verilog 4．虚拟现实与人机交互：VRML …… 问题： 如何将形形色色的语言翻译成可以在计算机上运行的0、1串 11 1.2 语言之间的翻译 习惯称法： 汇编语言－机器指令：汇编（或交叉汇编） 程序设计语言－汇编语言或机器指令：编译（或解释） 高级语言之间：转换（或预编译） 逆向：反汇编、反编译 12 1.3 编译器与解释器 语言翻译的两种基本形态 1.先翻译后执行 2. 边翻译边执行 例5 假设有源程序：read(x); write(“x=“, x); 13 1.3 编译器与解释器（续） 1.特点： •编译器：工作效率高，即时间快、空间省；交互性与动 态特性差、可移植性差大多数PL采用此方法翻译； •解释器：工作效率低，即时间慢、空间费；交互性与动 态特性好、可移植性好早期的Basic和Java等； 2. 基本功能：二者相同； 3. 所采用的技术：从翻译的角度来讲，两种方式所涉及的原 理、方法、技术相似 14 1.4 编译器的工作原理与基本组成 1.4.1 通用程序设计语言的主要成份 1．从语言抽象的演变看： 过程→抽象数据类型（ADT，程序包）→ 类 2．共同特点：两大部分组成：声明＋操作＝完整定义 3．以过程式语言为例： 声明性语句：提供操作对象的性质，如数据类型、值、作用域等； 操作性语句：确定操作的计算次序，完成实际操作。

过程头＋过程体＝过程定义 4．编译器对两类语句的翻译： 声明：生成相应的环境，一般是配置存储空间 操作：生成可执行的代码序列 例6 一个Pascal过程 15 1.4.2 以阶段划分编译器 1．自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰 2．编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成 3．编译器的阶段（逻辑模块划分） 4．中间代码的重要作用 16 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; （语法树） 17 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) 18 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; 19 1.4.3 编译器各阶段的工作（续3） 各阶段工作的归纳 1. 词法分析：识别单词，至少分以下几大类：关键字（保留字） 、标识符、字面量、特殊符号； 2. 语法分析：得到语言结构并以树的形式表示； 3. 语义分析：考察结构正确的句子是否语义合法，修改树结构； 4. 中间代码生成（可选）：生成一种既接近目标语言，又与具体 机器无关的表示，便于优化与代码生成； •（到目前为止，编译器与解释器可以一致） 5. 中间代码优化（可选）:局部优化、循环优化、全局优化等；优 化实际上是一个等价变换，变换前后的指令序列完成同样的功 能，但在占用的空间上和程序执行的时间上都更省、更有效。

6. 目标代码生成：不同形式的目标代码－汇编、可重定位、内存 形式（Load-and-Go）; 7. 符号表管理：合理组织符号，便于各阶段查找、填写等； 8. 出错处理：错误的种类－词法错、语法错、静态语义错、动态 语义错 20 1.4.4 编译器的分析/综合模式 • 前端：语言结构和意义的分析； • 后端：语言意义处理； • 中间代码：前端与后端的分界； 21 1.4.4 编译器的分析/综合模式（续1） 4．编译器基础架构（Infrastructure） ：源代码的中间表 示、一组前端、一组后端； 22 第－次课 结束 23 1.4.2 以阶段划分编译器 1．自然语言的翻译过程： 识别单词 识别句子结构 理解意思 译成中文并修饰 2．编译器的工作过程： 词法分析 语法分析 语义分析 目标代码生成 3．编译器的阶段（逻辑模块划分） 4．中间代码的重要作用 24 1.4.3 编译器各阶段的工作 例7 Pascal源程序语句如下： var x, y, z : real; x := y + z * 60; （源程序）var x, y, z : real; x := y + z * 。