《绪论36414.ppt》由会员分享，可在线阅读，更多相关《绪论36414.ppt（34页珍藏版）》请在三一文库上搜索。
1、编译原理邹昌伟QQ: 463092317E-mail: google_,要解决的问题,如何形式化地描述一门语言. （例如个位数四则运算的表达式应如何形式化地描述？） 如何把形式化描述后的语言翻译成另一门语言(通常是把高级程序设计语言翻译为机器语言或中间语言）.,课 程 简 介,教材和参考书 陈意云、张昱，编译原理，高等教育出版社，2008 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools , 2nd edition, Addison-Wesley, 200
2、7,重点章节： 2， 3， 6 ，7 本课程的考试方法和成绩计算： 1、笔试，以简答题和问答题为主； 2、笔试成绩占70%，实验及平时为30%。 A+ A A- B+ B B- C+ C C- D- 几点要求： 1. 实验报告和作业请务必独立完成。不要抄与“被抄”，可上网找资料，但要加以消化，而不是简单的复制粘贴。 2. 作业实验报告请按时提交。,第一章 引 论,翻译器(translator)、编译器(compiler)、解释器(interpreter) 编译器从逻辑上可以分成若干阶段 每个阶段把源程序从一种表示变换成另一种表示 本章通过描述编译器的各个阶段来介绍编译这个课题,1. 1 编译器
3、概述,1. 1 编译器概述,1. 1 编译器概述,表达式的语法特征 任何一个标识符都是表达式 任何一个数都是表达式 如果e1和e2都是表达式，那么 e1 + e2 e1 * e2 (e1) 也都是表达式,initial + rate * 60的分析树, 语法树,1. 1 编译器概述,1. 1 编译器概述,1. 1 编译器概述,1. 1 编译器概述,1. 1 编译器概述,1. 1 编译器概述,解释器和编译器的区别,1. 1 编译器概述,解释器和编译器的区别,解释器不生成目标代码，而是直接执行源程序所指定的运算,1. 1 编译器概述,解释器和编译器的区别,解释器不生成目标代码，而是直接执行源程序所
4、指定的运算,解释器也需要对源程序进行词法,语法和语义分析,中间代码生成,1. 1 编译器概述,BASIC年代的解释器 功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行 在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器 Java年代的解释器 解释器的上述两个功能分在两个程序中 前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序 后一个叫做解释器，它对字节码程序进行解释执行,1. 1 编译器概述,阶段分组 前端 后端,1. 1 编译器概述,阶段分组 遍,1.2 编译器技术的应用,高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级
5、语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护 流行编程语言的大多数演变都是朝着提高抽象级别的方向 每一轮编程语言新特征的出现都刺激编译器优化的新研究,1.2 编译器技术的应用,高级语言的实现 每一轮编程语言新特征的出现都刺激编译器优 化的新研究 支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran 面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java 类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存 Jav
6、a设计来支持代码移植和代码移动,1.2 编译器技术的应用,针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效,1.2 编译器技术的应用,新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码 在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构
7、的特征 编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明,1.2 编译器技术的应用,程序翻译 二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码 数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令,1.2 编译器技术的应用,提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在 改进软件开发效率 类型检查 类型检查是一种捕捉程序中前后不一致的成熟而有效的技术 边界检查 数据流分析技术可用来定位缓冲区溢出 内存管理 自
8、动的内存管理删除内存泄漏等内存管理错误,四则运算表达式的编译,总体设计: （1）接收用户输入的一个整数四则运算的表达式： （2）编译为“栈机”上的“栈机码” （3）在“栈机”上运行 上述过程类似于Java的先编译后解释执行 (其中栈机相当于Java的虚拟机， 栈机码相当于Java编译后的中间代码) 四则运算表达式的翻译有多种方法: 基于运算符间优先级的方法 可参见数据结构 严尉敏 P52 (2)递归下降分析 可参见编译原理陈意云 P54 （由P54页可了解如何把文法转换成程序) (3)其他,四则运算表达式的编译,栈机指令集的参考定义: (1)入栈指令 push operand ; 其中oper
9、and为操作数 指令说明: 把操作数入栈 如 push 100。 (2) 出栈指令 pop; 指令说明: 把栈顶元素出栈，若栈机中栈为空，则报错。 (3) add sub mul div 分别作+ - * / 运算 指令说明: 把栈机的栈顶两个元素出栈，作相应运算后把结果再入栈,四则运算表达式的编译,例如用户输入的表达式如下 333+(200-100) /10*2+ 30; 编译器应将之编译为栈机上的汇编代码: PUSH 333 PUSH 200 PUSH 100 SUB PUSH 10 DIV PUSH 2 MUL ADD PUSH 30 ADD,四则运算表达式的编译,栈机再运行编译后的栈机
10、码，执行的结果如下: 200-100=100 100/10=10 10*2=20 333+20=353 353+30=383,四则运算表达式的编译,“表达式的递归定义”(其中 | 表示或者） 表达式 expr expr expr + term | expr - term | term 项 term term term * factor | term / factor | factor 因子 factor factor (expr) | num,四则运算表达式的编译,为了把上述文法转换为程序，我们作如下变换: 表达式 expr - term exprRest exprRest - + term
11、prt(ADD) exprRest | - term prt(SUB) exprRest | 项 term - factor termRest termRest - * factor prt(MUL) termRest | / factor prt(DIV) termRest | 因子 factor - (expr) | num prt(PUSH num) 其中形如prt(ADD)的部分表示相关的语义动作，此处即产生Add指令；而表示空串,四则运算表达式的编译,把上述“翻译模式”转换为相应的代码，以“因子”为例 /处理因子，其中lookahead中存放的是下一个待分析的记号(即编译原理中所谓的
12、token) private void factor() /处理因子 if(lookahead.isLeftP() /如果是左括号 match(TokenType.LeftP); /进行匹配 expr(); /处理表达式 match(TokenType.RightP); /匹配右括号 else if(lookahead.isNum() /如果是数 emit(“PUSH ”+lookahead.tokenValue); /产生代码 match(TokenType.NUM); /匹配”数” else /错误处理 error(Error); /如果要对项进行翻译,处理为语句 else ;,四则运算表
13、达式的编译,/ match方法 /其中lexer为词法分析器，用它来获取下一个记号 lexer.getToken() 注: 记号的概念333+(200-100) /10*2+ 30; 实际上是单词的概念，在计算机中表示为一个二元式 如上述333 表示为(num, 333) private void match(TokenType type) /如果记号lookahead的类型是type，则取下一个记号 if(lookahead.tokenType.equals(type) lookahead = lexer.getToken(); else error(“Error”); /否则报错 ,四则运算表达式的编译,词法分析器: 只需为语法分析器提供一个getToken()方法，以返回下一个待分析的记号 语法分析器： 此处由与表达式、项、因子对应的相应方法expr() term() factor()组成 这些方法如何书写，可参照factor()方法 要翻译表达式，调用以下语句即可: lookahead = lexer.getToken(); expr(); /expr()方法返回后，即完成了对表达式的翻译。,