世界十大稀奇古怪景点休闲娱乐.ppt

《世界十大稀奇古怪景点休闲娱乐.ppt》由会员分享，可在线阅读，更多相关《世界十大稀奇古怪景点休闲娱乐.ppt（53页珍藏版）》请在三一办公上搜索。

1、编译原理-引论,主讲：姜守旭辅导：李治军办公室：综合楼518电话：86415549Email：lizhijun_答疑地点：综合楼516答疑时间：,学时与参考教材,学时：48+16小时参考教材：1、Alfred Aho ect.编译原理，李建中等译，机械工业出版社，2003.8.(原版-邮电出版社)2、Kenneth C.Louden，编译原理及实践，冯博琴等译，机械工业出版社，2001.2.印刷3、金成植，编译程序构造原理和实现技术，高等教育出版社，2000.7.4、陈火旺等，程序设计语言编译原理，国防工业出版社，2003.8.印刷,学时与参考教材,5、何炎祥等，编译原理，华中理工大学出版社，

2、2000.10.6、蒋立源，编译原理，西北工业大学出版社，2000.7.7、肖军模，程序设计语言编译方法，大连理工大学出版社，2000.88、杜淑敏等，编译程序设计原理北京大学出版社，1990.11.9、蒋宗礼等，形式语言与自动机理论，清华大学出版社，2003.1.,主要内容,编译系统及其设计概述（总体结构、设计方法2）语言与文法（文法、推导、归约、分类、分析树4）词法分析（词法分析、正规式与正规文法、DFA的状态转移图6）语法分析（自顶向下：LL(1)、递归子程序；自底向上：算符优先、LR16）语义分析（属性文法、各种语句的语法制导翻译10）运行环境（存储分配、过程调用、符号表管理6）代码优

3、化（基本块的优化、控制流分析、循环优化、数据流分析2）代码生成（目标机器模型、基本块和流图、寄存器分配、基本块的DAG表示、从 DAG生成目标代码2）,教学目的编译原理是一门非常好的课程,Alfred V.Aho：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本书中的原理和技术都会反复用到涉及的是一个比较适当的抽象层面上的数据变换（既抽象，又实际）一些具体的表示和变换算法“自顶向下的方法”和“自底向上的方法”系统设计方法（思想、方法、实现全方位讨论）一个相当规模的系统的设计（含总体结构）计算机专业最为恰当、有效的知识载体之一,教学要求,掌握编译程序总体结构在系

4、统级上认识算法、系统的设计具有把握系统的能力学习有关的原理、实现方法和技术，了解计算学科的基本方法、思想掌握典型方法。“在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。”兼顾语言的描述方法、设计、应用形式化能形式化就能自动化进一步培养“计算机思维能力”软件系统的非物理性质,学习成果_以学生为中心,理解和掌握编译过程各个阶段的工作原理理解标准编译器各个组成部分的任务熟悉编译过程各阶段所要解决的问题及其采用的方法和技术应用一些标准的技术解决编译器构造过程中所产生的相关问题理解编译器在生成代码时如何充分利用特定处理器的特征,教、学方法,教学方法整体性从系统的角度启发式以学生为中心应

5、用驱动技术、方法的应用背景学习方法 源程序是源泉把每个阶段放到整个编译程序背景中学习认真做作业编程序,第1章 引论,1.1 计算机语言的发展1.2 翻译系统1.3 编译系统的功能分析1.4 编译程序总体结构1.5 编译程序的生成1.6 编译技术的应用,1.1 计算机语言的发展,机器语言(Machine Language)与汇编语言(Assemble Language)0、1代码与助记符：更接近于计算机硬件指令系统的工作高级语言(High Level Language)其表示方法更接近于待解问题的表示方法定义数据、描述运算、控制流程、传输数据如：C、FORTRAN、PASCAL、C+、JAVA、

6、SQL(数据定义、数据操作)命令语言(Command Language)控制系统的工作以功能封装为特征如UNIX上的shell,高级语言的分类,强制式（命令式）语言(Imperative Language)通过指明一系列可执行的运算及运算的次序来描述计算过程的语言；FORTRAN(段结构)、BASIC、Pascal(嵌套结构)、C程序的层次性和抽象性不高申述式语言（Declarative Language）着重描述要处理什么，而非如何处理的非命令式语言函数(应用)式语言(Functional Language)基本运算单位是函数，如LISP、ML逻辑式(基于规则)语言(Logical Lang

7、uage)基本运算单位是谓词，如Prolog，Yacc面向对象语言(Object-Oriented Language)以对象为核心，如Smalltalk、C+、Java、Ada(程序包)具有识认性（对象）、类别性（类）、多态性和继承性,1.2 翻译系统,翻译程序(Translator)将某一种语言描述的程序(源程序Source Program)翻译成等价的另一种语言描述的程序(目标程序Object Program)的程序。,翻译程序,源程序,目标程序,(*.C/*.PAS),(*.OBJ/*.EXE),1.2 翻译系统,解释程序(Interpreter)口译与笔译（单句提交与整篇提交）,源程序

8、,输入数据,计算结果,解释程序,1.2 翻译系统,编译程序(Compiler)高级语言程序汇编/机器语言程序,源程序,目标程序,编译程序,1.2 编译系统,SPCompilerS-SourceO-ObjectOPP-ProgramInputRSRS-Run Sys.Output,编译系统(Compiling System)编译系统=编译程序+运行系统,支撑环境、运行库等,1.2 翻译系统,其它：诊断编译程序（Diagnostic Compiler)优化编译程序（Optimizing Compiler)交叉编译程序（Cross Compiler)可变目标编译程序（Retargetable Com

9、piler)并行编译程序（Parallelizing Compiler）汇编程序(Assembler)、交叉汇编程序(Cross Assembler)、反汇编程序（Disassembler),1.2 翻译系统汇总,MLMLPAssemblerDisassemblerAL ALPTranslator Compiler DataHLHLPInterpreterResult,M-MachineL-LangugeP-ProgramA-AssembleH-High Level,1.3 编译系统的功能分析,程序分析词法、语法、语义分析综合语句的翻译、代码生成标识符处理：左值与右值的绑定(binding)变

10、量：存储单元函数：目标代码序列,1.4 编译程序总体结构,目标代码生成器,代码优化器,语义分析与中间代码生成器,语法分析器,1.词法分析,例：main()printf(“hello”);,结果IDNmain()IDNprintf(STRhello);,1、词法分析,词法分析由词法分析器完成(Lexical Analyzer)，词法分析器又叫做扫描器(Scanner)词法分析器从左到右扫描源程序一个字符串，并将该字符串转换成单词(记号Token)串；同时要：查词法错误，进行标识符登记符号表管理。输入：字符串 输出：(种别码，属性值)序对属性值token的机内表示,2、语法分析,语法分析由语法分析

11、器(Syntax Analyzer)完成，语法分析器又叫Parser。功能：Parser实现“组词成句”将词组成各类语法成分：表达式、因子、项，语句，子程序构造分析树指出语法错误指导翻译输入：Token序列输出：语法成分,2.语法分析,res=fact*(term1+term2);,3.语义分析,功能：分析由语法分析器识别出的语法单位的语义获取标识符的属性：类型、作用域等语义检查：运算的合法性、取值范围等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址,4.中间代码生成,中间代码(intermediate Code)例:id1+id2*id3,后缀表示(逆波兰Anti-Polis

12、h Notation)id1id2id3*+前缀表示(波兰Polish Notation)+id1*id2id3,四元式表示(三地址码)1(*,id1,id2,T1)2(+,id3,T1,T2),三元式表示1(*,id2,id3)2(+,id1,(1),波兰表示问题Lukasiewicz 1929年发明,中缀表示(Infix notation):(a+b)*(-c+d)+e/f波兰表示（Polish/Prefix/Parenthesis-free/Lukasiewicz notation）也就是前缀表示+*+a b+c d/ef 逆波兰表示(Reverse Polish/Suffix/Post

13、fix notation)也就是后缀表示a b+c d+*ef/+运算顺序从左向右,4.中间代码生成,中间代码的特点简单规范与机器无关易于优化与转换,三地址码的另一种表示形式T1=id2*id3T2=id1*T1,其它类型的语句例：printf(“hello”)x:=s（赋值）param x（参数）call f（函数调用）注释s 是 hello 的地址f 是函数 printf 的地址,对中间代码的优化处理:对代码进行等价变换以求提高执行效率提高运行速度和节省存储空间与机器无关的优化与机器有关的优化,5.代码优化,与机器无关的优化,局部优化常量合并：常数运算在编译期间完成，如8+9*4公共子表达

14、式的提取:基本块内循环优化强度削减用较快的操作代替较慢的操作代码外提将循环不变计算移出循环,与机器有关的优化,寄存器的利用将常用量放入寄存器，以减少访问内存的次数体系结构MIMD、SIMD、SPMD、向量机、流水机存储策略根据算法访存的要求安排：Cache、并行存储体系减少访问冲突任务划分按运行的算法及体系结构，划分子任务(MPMD),6.目标代码生成（Code Generator）,将中间代码转换成目标机上的机器指令代码或汇编代码确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）制定从中间代码到目标代码的翻译策略或算法目标代码的形式具有绝对地址的机器指令汇编语言形式的目标程序模

15、块结构的机器指令（需要链接程序）,7、表格管理,管理各种符号表（常数、标号、变量、过程、结构），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术,8、错误处理,进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化）词法：拼写语法：语句结构、表达式结构语义：类型不匹配,模块分类,分析：词法分析、语法分析、语义分析综合：中间代码生成、代码优化、目标代码生成辅助：符号表管理、出错处理8项功能对应8个模块,编译程序总体结构,例 一个语句的翻译,9 编译的遍（P

16、ass）,根据系统资源的状况、运行目标的要求等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。如：首遍构造语法树，二遍处理中间表示，增加信息等。遍可以和阶段相对应，也可无关单遍代码不太有效,10、编译的前端与后端,前端与源语言有关、与目标机无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机有关的部分与机器有关的代码优化、目标代码生成,1.5 编译程序的生成,设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。如何实现编译器？直接用可运行的代码编制太费力！自举-使用语言提供的功能来编译该语

17、言自身。“第一个编译器是怎样被编译的？”,形图（P470）,表示语言翻译的 形图,源语言,实现语言,目标语言,1）交叉编译(Cross Compiling)/移植,问题一：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？条件：机有 语言的编译程序目的：实现机的语言的编译,1.(人)用语言编制B机的编译程序P0(CB)(机的C编译P1)编译P0，得到在A机上可运行的P2(CB),3.(机的P2)编译P0，得到在B机上可运行的P3(CB),P2,2)本机编译器利用,问题二：A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？能利用交叉编译技术么？用C编写NEW的编译，

18、并用C编译器编译它,问题三：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个子集的编译程序(P0人)用汇编程序处理该程序,得到(P2:可直接运行)用子集编制语言的编译程序(P3人)用P2编译P3，得到P4,3)编译程序的自展技术,4.用P2编译P3，得到P4,语言,机器语言,机器语言,P4,子集,机器语言,机器语言,P2,获得一个工具,语言,子集,机器语言,P3,3.用子集编制 语言的编译程序(P3人),4)利用编译程序自动生成器,词法分析器的自动生成程序,词法规则说明,词法分析程序,(C程序),输入：词法（正规表达式）识别动作（程序段）输出：yylex()函数,语法分

19、析器的自动生成程序,语法规则说明,语法分析程序,(C程序),输入：语法规则（产生式）语义动作（程序段）输出：yyparse()函数,1.6 编译技术的应用,把复杂数据看作一条语句数据格式的分析利用词法分析、语法分析方法数据处理的框架基于语法制导的语义处理框架编译技术可以用于各种复杂数据的分析处理,1.6 编译技术的应用,语法制导的结构化编辑器 程序格式化工具 软件测试工具 程序理解工具 高级语言的翻译工具,例1-1,DOS 命令 date 的输出格式例：9-2-1993、09-03-1993、9-03-93语法date month-day-year词法month DIGIT DIGIT|DIG

20、ITday DIGIT DIGIT|DIGITyear DIGIT DIGIT|DIGII DIGIT DIGIT DIGIT,例1-1（续）,语义year(年)、month(月)、day(日)语义约束条件0 month.value 130 day.value 32，31，300 year.value 10000,小结,计算机语言的发展翻译系统及其功能编译的总体结构编译的各个阶段编译的生成及应用相关概念,习题,1.试分析一个简短的 C 程序，找出几个属于语法、词法、语义的语言现象。2.试分析例 1-1 的 date 输出数据的处理中，应该做哪些词法分析、语法分析、语义处理。3.理解交叉编译和自展技术,