编译原理(第1章)素材.ppt

1、2020/7/25,编译原理,1,编译原理 Compiler Principles,授课教师：贺辉 619412,课程简介,教学方式：理论(40)+实验(14) 考核方式：期中考试(20%)+平时成绩(30%) +期末考试（40）+平时考核（10%） 课程学分：3 答 疑： 励耘楼A209 周一 5-6节 教材及参考书籍： 编译原理（本科教学版） 赵建华等（译），机械工业出版社 Compilers: Principles,Techniques, 编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具; 课程中包含了很多软件技术,程序设计语言编译程序构造的基本原理和实

2、现方法是软件的核心技术之一,这对于以后从事软件设计是很有帮助的.,2020/7/25,编译原理,4,为什么要学习编译原理,与课程有关的问题,先修课程： 编程语言、离散数学、汇编语言、数据结构 、形式语言与自动机 应用 编译器的设计 一般软件的设计 文本编辑器、信息检索系统、模式识别器 排版、绘图等 本课程的基本要求 通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。 修养“问题形式化描述计算机化” 的问题求解过程,2020/7/25,编译原理,5,实验要求,实验形式 分析、设计、编写、调试、测试程序 撰写实验报告 答辩 实验内容 程序

3、设计复习 2学时 编码完成扫描程序（词法分析）2学时 语法分析器的设计与实现 4学时 使用Lex自动生成一个编译器 6学时,2020/7/25,6,学习中应注意的问题,一定要预习，每人都请准备一个笔记本！ 认真听课，积极思考，积极发言，认真理解 重视习题：按时完成课堂作业及课堂的测试 在理解的基础上记忆，把编译的每个阶段放到整个编译程序背景中学习 理论结合实践，重视实验 要敢于犯错误 学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。 急功近利是学习的一大敌人！,2020/7/25,编译原理,7,寄语,要主动学习 不要苛求课程、老师和环境，他/她/它们

4、只是资源 目标确定后要善于利用各种资源 注重对自己能力的培养 学会做人,乐于助人,多为别人着想,可以获取友谊 朋友是资源，可以终生受益 学会安排自己的时间 时间就像海绵里的水，只要肯挤，总会有的。贵在恒。 学会利用各种资源提高自己 学校的、家庭的、社会的 上学期间利用资源的唯一目的就是提高自己 不要沉迷于网络聊天（微信 微博）与游戏,2020/7/25,8,各章节内容安排,第一章引论 第二章高级语言及其语法描述 第三章词法分析 第四章语法分析【自顶向下（递归下降语法分析、LL(1)）、自底向上（LR（1）】 第五章语义分析【语法制导的翻译】 第六章中间代码及目标代码生成,2020/7/25,编

5、译原理,9,程序设计语言,机器语言： 能够被计算机的硬件系统直接执行的指令程序。 由二进制(0、1序列)组成 难读、难写、易出错。 汇编语言：用记忆符表示指令的操作码。,面向机器语言（低级语言）,按机器指令的工作方式来思考问题,assume cs:code, ds:data data segment dw 1234h,5678h data ends code segment start:mov ax, data mov ds, ax mov ax, ds:0 mov bx, ds:2 mov cx, 0 add cx, ax add cx, bx mov cx, ds:4 mov ax, 4c

6、00h int 21h code ends end start,程序设计语言,高级语言（面向人类的语言）： 便于人类的理解和使用 语言的结构符合人的思维方式：如直接使用表达式进行计算. 具有高抽象度：如 类 等机制 强调逻辑过程，事情的前因后果，不仅是做什么，而且是怎么做？,int main int a,b,c; a=1234h; b=5678h; c=a+b; return 0; ,翻译程序,机器只能理解和执行机器语言高级语言需转换成机器语言才能执行如何转换？ 翻译 解释 翻译程序：是指能够把某种语言的程序（源语言程序）转换成另一种语言的程序（目标语言程序），而后者与前者在逻辑上是等价的。

7、编译程序：源语言程序为高级语言程序，目标语言程序是低级语言程序的翻译程序。 汇编程序：源语言程序为汇编语言程序，目标语言程序为机器语言程序的翻译程序。,如何执行一个源程序,先编译后执行-编译程序编译出目标程序，系统执行。,交叉编译程序：宿主机和目标机的指令系统不同,诊断编译程序：侧重于帮助程序开发和调试 优化编译程序：着重于提高目标代码的效率 ,运行编译程序的计算机,运行产生的目标代码的计算机,如何执行一个源程序,边解释边执行-解释程序边解释边执行源程序本身，不产生目标程序。,什么是编译程序,2020/7/25,编译原理,15,编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和

8、方法。,本章重点介绍编译程序的基本概念。,编译的过程,编译程序的结构,1.1 什么是编译程序,2020/7/25,编译原理,16,翻译程序是指这样一个程序,它把一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。世界上第一个编译程序FORTRAN是在20世纪50年代中期研制成功的。花费了18年的时间。,高级语言程序,机器语言程序,翻译程序,2020/7/25,编译原理,17,编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。,源程序,高级语言程序,编译程序,目标程序,汇编语言或者机器语言程序,(*.C /

9、*.PAS),(*.OBJ / *.EXE),2020/7/25,编译原理,18,采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。,第一种情况：,高级语言 程序,2020/7/25,编译原理,19,第二种情况：,高级语言 程序,1.2 编译程序的基本结构,2020/7/25,编译原理,20,例：将英文句子 “I wish you success ”翻译成中文句子的大致过程是：,词法分析,语法分析,语义分析,修饰工作,翻译成文,2020/7/25,编译原理,21,编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：,词法分析,语法分析,语义分析和

10、中间代码生成,代码优化,目标代码生成,2020/7/25,编译原理,22,float r，h，s； s = 2*3.1416 * r *(rh);,例如 计算圆柱体表面积的程序 片断如下：,a. 词法分析,2020/7/25,编译原理,23,词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词( 也称单词符号, 简称符号 )。,2020/7/25,编译原理,24,词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。,float r，h，s； s = 2*3.1416*r*(hr);,例如,2020/7/25,编译原

11、理,25,上述源程序通过词法分析识别出如下单词符号： 关键字 float 标识符 r、h、s 常数 3.1416、2 算符 * 、 界符 （、 ）、 ；、 ，、=,float r，h，s； s = 2*3.1416*r*(hr);,2020/7/25,26,练一练,sum=(10+20)*(num+square); 词法分析结果？,结果 (标识符，sum) (赋值号，=) (左括号， ( ) (整常数，10) (加号，+ ) (整常数，20) (右括号， ) ) (乘号，* ) (左括号， ( ) (标识符，num) (加号，+ ) (标识符，square) (右括号， ) ) (分号，; )

12、,b. 语法分析,2020/7/25,编译原理,27,语法分析的任务是在词法分析的基 础上, 根据语言的语法规则从单词符 号串中识别出各种语法单位 ( 如表 达式、说明、语句等 ) ,并进行语法 检查,即检查各种语法单位在语法结 构上的正确性。,2020/7/25,编译原理,28,语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。,float r，h，s； s = 2*3.1416*r*(hr);,例如,2020/7/25,编译原理,29,单词符号串 s=2*3.1416 * r *(hr)中，“s” 是，单词符号串 “2 * 3.1416 * r *(hr)” 组

13、合成这样的语法单位 , 由=构成这样的语法单位。,2020/7/25,30,语法分析,sum=(10+20)*(num+square);,语法树,c. 语义分析和中间代码生成,2020/7/25,编译原理,31,语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式 (比源语言更接近于目标语言的一种中间代码或直接用目标语言 ) 来描述这种语义。,例如：,2020/7/25,编译原理,32,将s = 2*3.1416 * r *(hr)翻译成如下形式的四元式中间代码：,(1) ( *, 2, 3.1416, T1 ),(2) ( *, T1, r, T2 ),(

14、3) ( +, h, r, T3 ),(4) ( *, T2, T3, T4 ),(5) ( =, T4, _, s ),2020/7/25,编译原理,33,再例如：中间代码生成：,如：position：initialrate60 生成四元式序列： （inttoreal 60 t1 ） （ id3 t1 t2） （ id2 t2 t3） （： t3 id1）,运算符,运算对象1,运算对象2,结果,id1,id2,id3,t1，t2，t3是临时变量,2020/7/25,34,练一练,sum=(10+20)*(num+square); 中间代码(intermediate Code)？,四元式表示

15、(三地址码) (+，10，20，T1) (+，num，square，T2) (*， T1， T2， T3) (=， T3 ， ， sum),三元式表示 (+，10，20) (+，num，square) (*，) (=， sum，),语法树,d. 代码优化,2020/7/25,编译原理,35,代码优化的任务是对前阶段产生的中间代码进行等价变换，以期获得更为高效即省时间和空间的目标代码。将s = 2*3.1416 * r *(hr)翻译成如下形式的四元式经局部优化后得：,(1) ( *, 6.28, r, T2 ),(2) ( +, h, r, T3 ),(3) ( *, T2, T3, T4 )

16、,(4) ( =, T4, _, s ),2020/7/25,编译原理,36,例如： position：initialrate60 id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) (* id3 t1 t2 ) (3) (+ id2 t2 t3 ) (4) (:= t3 - id1) 四元式经局部优化后得：,（1） ( *id3 60.0 t1) （2）（ + id2 t1 id1),e.目标代码生成,2020/7/25,编译原理,37,主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关

17、。,(*id360.0 t1) (+id2t1 id1),MOVid3,R2 MUL #60.0,R2 MOVid2,R1 ADDR2,R1 MOVR1,id1,2020/7/25,编译原理,38,记号：token,语法树：syntax tree,：symbol table,注释树,2020/7/25,39,编译程序总体结构,目标代码生成器,代码优化器,语义分析与中间代码生成器,语法分析器,目标代码,表格与表格管理,作用： 登记源程序的各类信息和编译各阶段的进展情况。 最重要的是符号表，它用来登记源程序中出现的每一个名字以及名字的各种属性（类型、作用域、分配存储信息等）,如：Const1常量

18、值：35 Var1变量 类型：实 层次：2,出错处理,错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。 编译程序应设法发现源程序的错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处理程序）完成的。 错误的类型： 语法错误：指源程序中不合语法（或词法）规则的错误。如：非法字符。 语义错误：指不合语义规则的错误，如：说明错误、作用域错误、类型不一致等。有些在语义分析时检测出来，有些要在运行的时候才能检测出来,遍(Pass),遍： 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 即可将几个不同阶段合为一遍，也可以把各个阶段的工作分成若干遍。 分遍的原则： 目标质量高低，机器内存大小，源语言简繁等。,编译前端与后端,从概念上划分： 编译程序可分为编译前端和编译后端。 编译前端：指与源语言有关但与目标机无关的编译程序部分。包括词法分析、语法分析、语义分析、中间代码产生和部分优化。 编译后端：指与目标机有关的编译