编译原理(第1章)

2023/2/1编译原理1编译原理

CompilerPrinciples授课教师：贺辉619412课程简介教学方式：理论(40)+实验(14)考核方式：期中考试(20%)+平时成绩(30%)+期末考试（40）+平时考核（10%）课程学分：3答疑：励耘楼A209周一5-6节教材及参考书籍：《编译原理》（本科教学版）赵建华等（译），机械工业出版社《Compilers:Principles,Techniques,&Tools》(编译原理技术与工具)，Aho，A.V.，机械工业出版社《CompilerConstructionPrincipleandPratice》(编译原理及实践)，KennethC.Louden，机械工业出版社为什么要学习编译原理编译程序构造是计算机学科中一个非常成功的分支，也是最早获得成功的分支；编译原理蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法;编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具;课程中包含了很多软件技术,程序设计语言编译程序构造的基本原理和实现方法是软件的核心技术之一,这对于以后从事软件设计是很有帮助的.2023/2/1编译原理4为什么要学习编译原理与课程有关的问题先修课程：编程语言、离散数学、汇编语言、数据结构、形式语言与自动机应用编译器的设计一般软件的设计文本编辑器、信息检索系统、模式识别器排版、绘图等本课程的基本要求通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。修养“问题→形式化描述→计算机化”的问题求解过程2023/2/1编译原理5实验要求实验形式分析、设计、编写、调试、测试程序撰写实验报告答辩实验内容程序设计复习2学时编码完成扫描程序（词法分析）2学时语法分析器的设计与实现4学时使用Lex自动生成一个编译器6学时2023/2/16学习中应注意的问题一定要预习，每人都请准备一个笔记本！认真听课，积极思考，积极发言，认真理解重视习题：按时完成课堂作业及课堂的测试在理解的基础上记忆，把编译的每个阶段放到整个编译程序背景中学习理论结合实践，重视实验要敢于犯错误学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。急功近利是学习的一大敌人！2023/2/1编译原理7寄语要主动学习不要苛求课程、老师和环境，他/她/它们只是资源目标确定后要善于利用各种资源注重对自己能力的培养学会做人,乐于助人,多为别人着想,可以获取友谊朋友是资源，可以终生受益学会安排自己的时间时间就像海绵里的水，只要肯挤，总会有的。贵在恒。学会利用各种资源提高自己学校的、家庭的、社会的……上学期间利用资源的唯一目的就是提高自己不要沉迷于网络聊天（微信微博……）与游戏2023/2/18各章节内容安排第一章引论第二章高级语言及其语法描述第三章词法分析第四章语法分析【自顶向下（递归下降语法分析、LL(1)）、自底向上（LR（1））】第五章语义分析【语法制导的翻译】第六章中间代码及目标代码生成2023/2/1编译原理9程序设计语言机器语言：能够被计算机的硬件系统直接执行的指令程序。由二进制(0、1序列)组成难读、难写、易出错。汇编语言：用记忆符表示指令的操作码。面向机器语言（低级语言）按机器指令的工作方式来思考问题assumecs:code,ds:datadatasegment dw1234h,5678hdataendscodesegmentstart: movax,data movds,ax movax,ds:[0] movbx,ds:[2] movcx,0 addcx,ax addcx,bx movcx,ds:[4] movax,4c00h int21h codeendsendstart程序设计语言高级语言（面向人类的语言）：便于人类的理解和使用语言的结构符合人的思维方式：如直接使用表达式进行计算.具有高抽象度：如类等机制强调逻辑过程，事情的前因后果，不仅是做什么，而且是怎么做？intmain{ inta,b,c; a=1234h; b=5678h; c=a+b; return0;}翻译程序机器只能理解和执行机器语言．高级语言需转换成机器语言才能执行．如何转换？翻译解释

翻译程序：是指能够把某种语言的程序（源语言程序）转换成另一种语言的程序（目标语言程序），而后者与前者在逻辑上是等价的。编译程序：源语言程序为高级语言程序，目标语言程序是低级语言程序的翻译程序。汇编程序：源语言程序为汇编语言程序，目标语言程序为机器语言程序的翻译程序。如何执行一个源程序先编译后执行-----编译程序编译出目标程序，系统执行。目标机宿主机编译程序运行系统目标程序P’输入数据计算结果源程序P交叉编译程序：宿主机和目标机的指令系统不同诊断编译程序：侧重于帮助程序开发和调试优化编译程序：着重于提高目标代码的效率．．．．运行编译程序的计算机运行产生的目标代码的计算机如何执行一个源程序边解释边执行-----解释程序边解释边执行源程序本身，不产生目标程序。解释程序源程序输入数据计算结果什么是编译程序2023/2/1编译原理15

编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和方法。本章重点介绍编译程序的基本概念。编译的过程编译程序的结构1.1什么是编译程序2023/2/1编译原理16

翻译程序是指这样一个程序,它把一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。世界上第一个编译程序FORTRAN是在20世纪50年代中期研制成功的。花费了18年的时间。

高级语言程序机器语言程序翻译程序2023/2/1编译原理17

编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。

源程序高级语言程序编译程序目标程序汇编语言或者机器语言程序(*.C/*.PAS)(*.OBJ/*.EXE)2023/2/1编译原理18

采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。第一种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段高级语言程序2023/2/1编译原理19第二种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段汇编程序汇编语言目标程序汇编阶段高级语言程序1.2编译程序的基本结构2023/2/1编译原理20例：将英文句子“Iwishyousuccess”翻译成中文句子的大致过程是：

词法分析

语法分析

语义分析

修饰工作

翻译成文

2023/2/1编译原理21

编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：

词法分析

语法分析

语义分析和中间代码生成

代码优化

目标代码生成2023/2/1编译原理22floatr，h，s；

s=2*3.1416*r*(r＋h);例如

计算圆柱体表面积的程序片断如下：A.词法分析2023/2/1编译原理23

词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词(也称单词符号,简称符号)。2023/2/1编译原理24

词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。

floatr，h，s；

s=2*3.1416*r*(h＋r);例如2023/2/1编译原理25

上述源程序通过词法分析识别出如下单词符号：

关键字

float

标识符

r、h、s

常数

3.1416、2

算符

*、＋

界符

（、）、；、，、=

floatr，h，s；

s=2*3.1416*r*(h＋r);2023/2/126练一练sum=(10+20)*(num+square);词法分析结果？

结果(标识符，sum)(赋值号，=)(左括号，()(整常数，10)(加号，+)(整常数，20)(右括号，))(乘号，*)(左括号，()(标识符，num)(加号，+)(标识符，square)(右括号，))(分号，;)

B.语法分析2023/2/1编译原理27

语法分析的任务是在词法分析的基础上,根据语言的语法规则从单词符号串中识别出各种语法单位(如表达式、说明、语句等),并进行语法检查,即检查各种语法单位在语法结构上的正确性。

2023/2/1编译原理28

语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。floatr，h，s；

s=2*3.1416*r*(h＋r);例如2023/2/1编译原理29

单词符号串s=2*3.1416*r*(h＋r)中，“s”是<变量>，单词符号串“2*3.1416*r*(h＋r)”组合成<表达式>这样的语法单位,由<变量>=<表达式>构成<赋值语句>这样的语法单位。2023/2/130语法分析sum=(10+20)*(num+square);语法树

C.语义分析和中间代码生成2023/2/1编译原理31

语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式(比源语言更接近于目标语言的一种中间代码或直接用目标语言)来描述这种语义。

例如：2023/2/1编译原理32

将s

=2*3.1416*r*(h＋r)翻译成如下形式的四元式中间代码：(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)2023/2/1编译原理33再例如：中间代码生成：

如：position：＝initial＋rate×60

生成四元式序列：（inttoreal60－t1）（×id3t1t2）（＋id2t2t3）（：＝t3－id1）运算符运算对象1运算对象2结果id1id2id3t1，t2，t3是临时变量2023/2/134练一练sum=(10+20)*(num+square);中间代码(intermediateCode)？四元式表示(三地址码)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3，，sum)三元式表示(+，10，20)(+，num，square)(*，⑴，⑵)(=，sum，⑶)语法树D.代码优化2023/2/1编译原理35

代码优化的任务是对前阶段产生的中间代码进行等价变换，以期获得更为高效即省时间和空间的目标代码。将s=2*3.1416*r*(h＋r)翻译成如下形式的四元式经局部优化后得：(1)(*,6.28,

r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,s)2023/2/1编译原理36例如：

position：＝initial＋rate×60id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)四元式经局部优化后得：（1）(* id3 60.0t1 )（2）（+ id2 t1 id1)E.目标代码生成

2023/2/1编译原理37主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。(* id3 60.0t1)(+ id2 t1 id1)MOV id3,R2MUL#60.0,R2 MOV id2,R1ADD R2,R1MOV R1,id12023/2/1编译原理38记号：token语法树：syntaxtree：symboltable注释树2023/2/139编译程序总体结构目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序表格与表格管理作用：