编译原理素材.pptx

《编译原理素材.pptx》由会员分享，可在线阅读，更多相关《编译原理素材.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程简介教学方式：理论(40)+实验(14)考核方式：期中考试(20%)+平时成绩(30%)+期末考试（40）+平时考核（10%）课程学分：3答 疑：励耘楼A209 周一 5-6节教材及参考书籍：编译原理（本科教学版）赵建华等（译），机械工业出版社Compilers:Principles,Techniques,&Tools(编译原理 技术与工具)，Aho，A.V.，机械工业出版社 Compiler Construction Principle and Pratice(编译原理及实践)，Kenneth C.Louden，机械工业出版社第1页/共46页为什么要学习编译原理编译程序构造是计算机学科中

2、一个非常成功的分支，也是最早获得成功的分支；编译原理蕴涵着计算机学科中解决问题的思路、抽象问题和解决问题的方法;编译原理课程的学习有利于加深对程序语言的理解,可以帮助你更加快速的掌握新的语言工具;课程中包含了很多软件技术,程序设计语言编译程序构造的基本原理和实现方法是软件的核心技术之一,这对于以后从事软件设计是很有帮助的.第2页/共46页2023/2/183为什么要学习编译原理为什么要学习编译原理第3页/共46页与课程有关的问题u先修课程：u编程语言、离散数学、汇编语言、数据结构、形式语言与自动机u应用p编译器的设计p一般软件的设计a)文本编辑器、信息检索系统、模式识别器b)排版、绘图等p本课

3、程的基本要求通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。修养“问题形式化描述计算机化”的问题求解过程 2023/2/184第4页/共46页实验要求实验形式分析、设计、编写、调试、测试程序撰写实验报告答辩实验内容程序设计复习 2学时编码完成扫描程序（词法分析）2学时语法分析器的设计与实现 4学时使用Lex自动生成一个编译器 6学时2023/2/185第5页/共46页学习中应注意的问题l一定要预习，每人都请准备一个笔记本！l认真听课，积极思考，积极发言，认真理解l重视习题：按时完成课堂作业及课堂的测试l在理解的基础上记忆，把编译的每

4、个阶段放到整个编译程序背景中学习l理论结合实践，重视实验要敢于犯错误学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。急功近利是学习的一大敌人！2023/2/186第6页/共46页寄语要主动学习不要苛求课程、老师和环境，他/她/它们只是资源目标确定后要善于利用各种资源注重对自己能力的培养学会做人,乐于助人,多为别人着想,可以获取友谊朋友是资源，可以终生受益学会安排自己的时间时间就像海绵里的水，只要肯挤，总会有的。贵在恒。学会利用各种资源提高自己学校的、家庭的、社会的上学期间利用资源的唯一目的就是提高自己不要沉迷于网络聊天（微信 微博）与游戏2023/2

5、/187第7页/共46页各章节内容安排第一章引论第二章高级语言及其语法描述第三章词法分析第四章语法分析【自顶向下（递归下降语法分析、LL(1)）、自底向上（LR（1）】第五章语义分析【语法制导的翻译】第六章中间代码及目标代码生成2023/2/188第8页/共46页程序设计语言机器语言：能够被计算机的硬件系统直接执行的指令程序。由二进制(0、1序列)组成难读、难写、易出错。汇编语言：用记忆符表示指令的操作码。面面向向机机器器语语言言（低低级级语语言言）按机器指令的工作方式来思考问题assume cs:code,ds:datadata segmentdw 1234h,5678hdata endsc

6、ode segmentstart:mov ax,datamov ds,ax mov ax,ds:0mov bx,ds:2mov cx,0add cx,axadd cx,bxmov cx,ds:4mov ax,4c00hint 21h code endsend start 第9页/共46页程序设计语言高级语言（面向人类的语言）：便于人类的理解和使用语言的结构符合人的思维方式：如直接使用表达式进行计算.具有高抽象度：如 类 等机制强调逻辑过程，事情的前因后果，不仅是做什么，而且是怎么做？int mainint a,b,c;a=1234h;b=5678h;c=a+b;return 0;第10页/共4

7、6页翻译程序机器只能理解和执行机器语言高级语言需转换成机器语言才能执行如何转换？翻译解释翻译程序：是指能够把某种语言的程序（源语言程序）转换成另一种语言的程序（目标语言程序），而后者与前者在逻辑上是等价的。编译程序：源语言程序为高级语言程序，目标语言程序是低级语言程序的翻译程序。汇编程序：源语言程序为汇编语言程序，目标语言程序为机器语言程序的翻译程序。第11页/共46页如何执行一个源程序先编译后执行-编译程序编译出目标程序，系统执行。目标机宿主机编译程序运行系统目标程序目标程序P输入数据输入数据计算结果计算结果源程序源程序P交叉编译程序：交叉编译程序：宿主机和目标机的指令系统不同宿主机和目标机

8、的指令系统不同诊断编译程序：侧重于帮助程序开发和调试优化编译程序：着重于提高目标代码的效率运行编译程序的计算机运行产生的目标代码的计算机第12页/共46页如何执行一个源程序边解释边执行-解释程序边解释边执行源程序本身，不产生目标程序。解释程序源程序源程序输入数据输入数据计算结果计算结果第13页/共46页什么是编译程序2023/2/1814 编译原理这门课程主要介绍设计和构造编译程序的基本原理和常用的技术和方法。本章重点介绍编译程序的基本概念。n编译的过程编译的过程n编译程序的结构编译程序的结构第14页/共46页1.1 什么是编译程序2023/2/1815 翻译程序翻译程序是指这样一个程序,它把

9、一种语言(称作源语言)所写的程序(源程序)翻译成等价的另一种语言(称作目标语言)的程序(目标程序)。世界上世界上第一个编译程序第一个编译程序FORTRANFORTRAN是在是在2020世纪世纪5050年代中期研制成功的。花费了年代中期研制成功的。花费了1818年的年的时间。时间。高级语言程序机器语言程序翻译程序第15页/共46页2023/2/1816 编译程序编译程序是一种翻译程序，它将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。源程序高级语言程序编译程序目标程序汇编语言或者机器语言程序(*.C/*.PAS)(*.OBJ/*.EXE)第16页/共46页2023/2/1817

10、采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。第一种情况：第一种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编 译 阶 段运 行 阶 段高级语言 程序第17页/共46页2023/2/1818第二种情况第二种情况：源程序编译程序机器语言目标程序初始数据运行系统结果编 译 阶 段运行阶段汇编程序汇编语言目标程序汇 编 阶 段高级语言 程序第18页/共46页1.2 编译程序的基本结构 2023/2/1819例例：将英文句子“I wish you success”翻译成中文句子的大致过程是：q 词法分析q 语法分析q 语义分析q 修饰工作q 翻译成文 第19页/共46页20

11、23/2/1820 编译程序是将一种语言形式翻译成另一种语言形式，因此，其工作过程一般可划分为如下五个阶段：q 词法分析 q 语法分析 q 语义分析和中间代码生成 q 代码优化 q 目标代码生成第20页/共46页2023/2/1821 float r，h，s；s=2*3.1416*r*(rh);例如 计算圆柱体表面积的程序 片断如下：第21页/共46页a.词法分析2023/2/1822 词法分析阶段的任务是对构成源程序的字字符符串串从左到右进行扫描和分解，根据语言的词词法法规规则则，识别出一个一个具有独立意义的单单词词(也称单词符号单词符号,简称符号)。第22页/共46页2023/2/1823

12、 词法规则词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。float r，h，s；s=2*3.1416*r*(hr);例如第23页/共46页2023/2/1824 上述源程序通过词法分析识别出如下单词符号：关键字 float 标识符 r、h、s 常数 3.1416、2 算符 *、界符 （、）、；、，、=float r，h，s；s=2*3.1416*r*(hr);第24页/共46页2023/2/1825练一练sum=(10+20)*(num+square);词法分析结果？结果(标识符，sum)(赋值号，=)(左括号，()(整常数，10)(加号，+)(整常数，20)(右括号，)

13、(乘号，*)(左括号，()(标识符，num)(加号，+)(标识符，square)(右括号，)(分号，;)第25页/共46页 b.语法分析2023/2/1826 语法分析的任务是在词法分析的基 础上,根据语言的语法规则语法规则从单词符单词符 号串号串中识别出各种语法单位语法单位 (如表 达式、说明、语句等),并进行语法语法 检查检查,即检查各种语法单位在语法结 构上的正确性。第26页/共46页2023/2/1827 语言的语法规则语法规则规定了如何从单词符号形成语法单位，语法规则语法规则是语法单位的形成规则。float r，h，s；s=2*3.1416*r*(hr);例如第27页/共46页202

14、3/2/1828 单词符号串 s=2*3.1416*r*(hr)中，“s”是，单词符号串 “2*3.1416*r*(hr)”组合成这样的语法单位,由=构成这样的语法单位。第28页/共46页2023/2/1829语法分析sum=(10+20)*(num+square);语法树第29页/共46页 c.语义分析和中间代码生成2023/2/1830 语义分析语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义，并用另一种语言形式(比源语言更接近于目标语言的一种中间代码或直接用目标语言)来描述这种语义。第30页/共46页 例如：2023/2/1831 将s=2*3.1416*r*(hr)

15、翻译成如下形式的四元式四元式中间代码：(1)(*,2,3.1416,T1)(2)(*,T1,r,T2)(3)(+,h,r,T3)(4)(*,T2,T3,T4)(5)(=,T4,_,s)第31页/共46页2023/2/1832再例如：中间代码生成：如：如：positionposition：initialinitialrate60rate60 生成生成四元式序列四元式序列：（inttoreal 60 inttoreal 60 t1 t1）（id3 t1 t2 id3 t1 t2）（id2 t2 t3id2 t2 t3）（：（：t3 t3 id1id1）运算符运算对象1运算对象2结果id1id2id

16、3t1，t2，t3是临时变量第32页/共46页2023/2/1833练一练sum=(10+20)*(num+square);中间代码(intermediate Code)？四元式表示四元式表示四元式表示四元式表示(三地址码)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3，sum)三元式表示三元式表示三元式表示三元式表示(+，10，20)(+，num，square)(*，)(=，sum，)语法树语法树语法树语法树第33页/共46页 d.代码优化2023/2/1834 代码优化的任务是对前阶段产生的中间代码进行等价变换，以期获得更为高效即 省 时 间

17、和 空 间 的 目 标 代 码。将s=2*3.1416*r*(hr)翻译成如下形式的四元式经局部优化后得：(1)(*,6.28,r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,_,s)第34页/共46页2023/2/1835例如：position：initialrate60id1:=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)第35页/共46页 e.e.目标代码生成

18、2023/2/1836主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。(*id3 60.0 t1)(+id2 t1 id1)MOVid3,R2MUL#60.0,R2 MOVid2,R1ADDR2,R1MOVR1,id1第36页/共46页2023/2/1837记号：记号：token语法树：语法树：syntax tree：symbol table注释树注释树第37页/共46页2023/2/1838编译程序总体结构目标代码生成器目标代码生成器代码优化器代码优化器语义分析与中间代码生成器语义分析与中间代码生成器语法分析器语法分析器表表 格格

19、 管管 理理出出 错错 处处 理理中间代码中间代码中间代码中间代码目标代码目标代码语法单位语法单位单词符号单词符号词法分析器词法分析器源程序源程序第38页/共46页表格与表格管理作用：登记源程序的各类信息和编译各阶段的进展情况。最重要的是符号表，它用来登记源程序中出现的每一个名字以及名字的各种属性（类型、作用域、分配存储信息等）如：Const1常量 值：35Var1变量 类型：实 层次：2第39页/共46页出错处理错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。编译程序应设法发现源程序的错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处理程序）完成的。错误的类型：语

20、法错误：指源程序中不合语法（或词法）规则的错误。如：非法字符。语义错误：指不合语义规则的错误，如：说明错误、作用域错误、类型不一致等。有些在语义分析时检测出来，有些要在运行的时候才能检测出来第40页/共46页遍(Pass)遍：对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。即可将几个不同阶段合为一遍，也可以把各个阶段的工作分成若干遍。分遍的原则：目标质量高低，机器内存大小，源语言简繁等。第41页/共46页编译前端与后端从概念上划分：编译程序可分为编译前端和编译后端。编译前端：指与源语言有关但与目标机无关的编译程序部分。包括词法分析、语法分析

21、、语义分析、中间代码产生和部分优化。编译后端：指与目标机有关的编译程序部分。包括与代目标机有关的代码优化和目标代码生成等。一般后端只依赖于中间语言。第42页/共46页课后作业q 什么是编译程序2023/2/1843q 编译过程的五个阶段q 编译程序的结构框图复习程序设计语言基础，教材复习程序设计语言基础，教材P.15-23P.15-23第43页/共46页人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。第44页/共46页第45页/共46页2023/2/18编译原理46感谢您的观看。第46页/共46页