编译原理(第1章).

编译原理1授课教师：贺辉619412课程简介教学方式：理论(40)+实验(14)考核方式：期中考试(20%)+平时成绩(30%)+期末考试（40）+平时考核（10%）课程学分：3答疑：励耘楼A209周一5-6节教材及参考书籍：《编译原理》（本科教学版）赵建华等（译），机械工业出版社《Compilers:Principles,Techniques,&Tools》(编译原理技术与工具)，Aho，A.V.，机械工业出版社《CompilerConstructionPrincipleandPratice》(编译原理及实践)，KennethC.Louden，机械工业出版社为什么要学习编译原理编译程序构造是计算机学科中一个非常成功的分支，也是最早获得成功的分支；编译原理蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法;编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具;课程中包含了很多软件技术,程序设计语言编译程序构造的基本原理和实现方法是软件的核心技术之一,这对于以后从事软件设计是很有帮助的.编译原理4为什么要学习编译原理与课程有关的问题先修课程：编程语言、离散数学、汇编语言、数据结构、形式语言与自动机应用编译器的设计一般软件的设计a)文本编辑器、信息检索系统、模式识别器b)排版、绘图等本课程的基本要求通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。修养“问题→形式化描述→计算机化”的问题求解过程编译原理5实验要求实验形式分析、设计、编写、调试、测试程序撰写实验报告答辩实验内容程序设计复习2学时编码完成扫描程序（词法分析）2学时语法分析器的设计与实现4学时使用Lex自动生成一个编译器6学时2019/12/176学习中应注意的问题一定要预习，每人都请准备一个笔记本！认真听课，积极思考，积极发言，认真理解重视习题：按时完成课堂作业及课堂的测试在理解的基础上记忆，把编译的每个阶段放到整个编译程序背景中学习理论结合实践，重视实验要敢于犯错误学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。急功近利是学习的一大敌人！编译原理7寄语要主动学习不要苛求课程、老师和环境，他/她/它们只是资源目标确定后要善于利用各种资源注重对自己能力的培养学会做人,乐于助人,多为别人着想,可以获取友谊朋友是资源，可以终生受益学会安排自己的时间时间就像海绵里的水，只要肯挤，总会有的。贵在恒。学会利用各种资源提高自己学校的、家庭的、社会的……上学期间利用资源的唯一目的就是提高自己不要沉迷于网络聊天（微信微博……）与游戏2019/12/178各章节内容安排第一章引论第二章高级语言及其语法描述第三章词法分析第四章语法分析【自顶向下（递归下降语法分析、LL(1)）、自底向上（LR（1））】第五章语义分析【语法制导的翻译】第六章中间代码及目标代码生成编译原理9程序设计语言机器语言：能够被计算机的硬件系统直接执行的指令程序。由二进制(0、1序列)组成难读、难写、易出错。汇编语言：用记忆符表示指令的操作码。面向机器语言（低级语言）按机器指令的工作方式来思考问题assumecs:code,ds:datadatasegmentdw1234h,5678hdataendscodesegmentstart:movax,datamovds,axmovax,ds:[0]movbx,ds:[2]movcx,0addcx,axaddcx,bxmovcx,ds:[4]movax,4c00hint21hcodeendsendstart程序设计语言高级语言（面向人类的语言）：便于人类的理解和使用语言的结构符合人的思维方式：如直接使用表达式进行计算.具有高抽象度：如类等机制强调逻辑过程，事情的前因后果，不仅是做什么，而且是怎么做？intmain{inta,b,c;a=1234h;b=5678h;c=a+b;return0;}翻译程序机器只能理解和执行机器语言．高级语言需转换成机器语言才能执行．如何转换？翻译解释翻译程序：是指能够把某种语言的程序（源语言程序）转换成另一种语言的程序（目标语言程序），而后者与前者在逻辑上是等价的。编译程序：源语言程序为高级语言程序，目标语言程序是低级语言程序的翻译程序。汇编程序：源语言程序为汇编语言程序，目标语言程序为机器语言程序的翻译程序。如何执行一个源程序先编译后执行-----编译程序编译出目标程序，系统执行。目标机宿主机编译程序运行系统目标程序P’输入数据计算结果源程序P交叉编译程序：宿主机和目标机的指令系统不同诊断编译程序：侧重于帮助程序开发和调试优化编译程序：着重于提高目标代码的效率．．．．运行编译程序的计算机运行产生的目标代码的计算机如何执行一个源程序边解释边执行-----解释程序边解释边执行源程序本身，不产生目标程序。解释程序源程序输入数据计算结果什么是编译程序编译原理15编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和方法。本章重点介绍编译程序的基本概念。编译的过程编译程序的结构1.1什么是编译程序编译原理16翻译程序是指这样一个程序,它把一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。世界上第一个编译程序FORTRAN是在20世纪50年代中期研制成功的。花费了18年的时间。高级语言程序机器语言程序翻译程序编译原理17编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。源程序高级语言程序编译程序目标程序汇编语言或者机器语言程序(*.C/*.PAS)(*.OBJ/*.EXE)编译原理18采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。第一种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段高级语言程序编译原理19第二种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段汇编程序汇编语言目标程序汇编阶段高级语言程序1.2编译程序的基本结构编译原理20例：将英文句子“Iwishyousuccess”翻译成中文句子的大致过程是：词法分析语法分析语义分析修饰工作翻译成文编译原理21编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：词法分析语法分析语义分析和中间代码生成代码优化目标代码生成编译原理22floatr，h，s；s=2*3.1416*r*(r＋h);例如计算圆柱体表面积的程序片断如下：A.词法分析编译原理23词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词(也称单词符号,简称符号)。编译原理24词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。floatr，h，s；s=2*3.1416*r*(h＋r);例如编译原理25上述源程序通过词法分析识别出如下单词符号：关键字float标识符r、h、s常数3.1416、2算符*、＋界符（、）、；、，、=floatr，h，s；s=2*3.1416*r*(h＋r);2019/12/1726练一练sum=(10+20)*(num+square);词法分析结果？结果(标识符，sum)(赋值号，=)(左括号，()(整常数，10)(加号，+)(整常数，20)(右括号，))(乘号，*)(左括号，()(标识符，num)(加号，+)(标识符，square)(右括号，))(分号，;)B.语法分析编译原理27语法分析的任务是在词法分析的基础上,根据语言的语法规则从单词符号串中识别出各种语法单位(如表达式、说明、语句等),并进行语法检查,即检查各种语法单位在语法结构上的正确性。编译原理28语言的语法规则规定了如何从单词符号形成语法单位，语法规则是语法单位的形成规则。floatr，h，s；s=2*3.1416*r*(h＋r);例如编译原理29单词符号串s=2*3.1416*r*(h＋r)中，“s”是变量，单词符号串“2*3.1416*r*(h＋r)”组合成表达式这样的语法单位,由变量=表达式构成赋值语句这样的语法单位。2019/12/1730语法分析sum=(10+20)*(num+square);赋值语句表达式=;(sum)*左部量表达式表达式表达式()表达式+表达式表达式+表达式表达式1020numsquare语法树C.语义分析和中间代码生成编译原理31语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式(比源语言更接近于目标语言的一种中间代码或直接用目标语言)来描述这种语义。例如：编译原理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)编译原理33再例如：中间代码生成：如：position：＝initial＋rate×60生成四元式序列：（inttoreal60－t1）（×id3t1t2）（＋id2t2t3）（：＝t3－id1）运算符运算对象1运算对象2结果id1id2id3t1，t2，t3是临时变量2019/12/1734练一练sum=(10+20)*(num+square);中间代码(intermediateCode)？四元式表示(三地址码)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3，，sum)三元式表示(+，10，20)(+，num，square)(*，⑴，⑵)(=，sum，⑶)语法树=sum*++1020numsquareD.代码优化编译原理35代码优化的任务是对前阶段产生的中间代码进行等价变换，以期获得更为高效即省时间和空间的目标代码。将s=2*3.1416*r*(h＋r)翻译成如下形式的四元式经局部优化后得：(1)(*,6.28,r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,s)编译原理36例如：position：＝initial＋rate×60id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)四元式经局部优化后得：（1）(*id360.0t1)（2）（+id2t1id1)E.目标代码生成编译原理37主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。(*id360.0t1)(+id2t1id1)MOVid3,R2MUL#60.0,R2MOVid2,R1ADDR2,R1MOVR1,id1编译原理38记号：token语法树：syntaxtree：symboltable注释树2019/12/1739编译程序总体结构目标代码生成器代码优化器语义分析与中间代码生成器语法分析器表格管理出错处理中间代码中间代码目标代码语法单位单词符号词法分析器源程序表格与表格管理作用：登记源程序的各类信息和编译各阶段的进展情况。最重要的是符号表，它用来登记源程序中出现的每一个名字以及名字的各种属性（类型、作用域、分配存储信息等）如：Const1常量值：35Var1变量类型：实层次：2出错处理错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。编译程序应设法发现源程序的错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处理程序）完成的。错误的类型：语法错误：指源程序中不合语法（或词法）规则的错误。如：非法字符。语义错误：指不合语义规则的错误，如：说明错误、作用域错误、类型不一致等。有些在语义分析时检测出来