编译原理chapter1-1.ppt

1、编译原理,主讲：闫健恩 Email：yanjianen(),写在课程之前,木桶原理：一个木桶由许多块木板组成，如果组成木桶的这些木板长短不一，那么这个木桶的最大容量不取决于长的木板，而取决于最短的那块木板。 蝴蝶效应：1963年12月，洛伦兹（Lorenz）在华盛顿的美国科学促进会的一次讲演中提出：一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风。他的演讲和结论给人们留下了极其深刻的印象。 马太效应：“马太福音”第二十五章由这么几句话：“凡有的，还要加给他叫他多余；没有的，连他所有的也要夺过来。” 。1968年，美国科学史研究者罗伯特莫顿（Robert K. Merton）提出这

2、个术语用以概括一种社会心理现象：“相对于那些不知名的研究者，声名显赫的科学家通常得到更多的声望即使他们的成就是相似的，同样地，在同一个项目上，声誉通常给予那些已经出名的研究者，例如，一个奖项几乎总是授予最资深的研究者，即使所有工作都是一个研究生完成的。”,学时与参考教材,学时：48+18学时 参考教材： 1、Alfred Aho ect. 编译原理，赵建华等译，机械工业出版社，2009.10. 2、Kenneth C. Louden，编译原理及实践，冯博琴等译，机械工业出版社，2001.2. 3、金成植，编译程序构造原理和实现技术，高等教育出版社，2000.7. 4、陈火旺等，程序设计语言编译

3、原理，国防工业出版社，2003.8.印刷,学时与参考教材,5、何炎祥等，编译原理，华中理工大学出版社，2000.10. 6、蒋立源，编译原理，西北工业大学出版社，2000.7. 7、肖军模，程序设计语言编译方法，大连理工大学出版社，2000.8 8、蒋宗礼等，形式语言与自动机理论，清华大学出版社，2003.1.,主要内容,编译系统及其设计概述（总体结构、设计方法） 语言与文法（文法、推导、归约、分类、分析树） 词法分析（词法分析、正规式与正规文法、DFA的状态转移图） 语法分析（自顶向下：LL(1)、递归子程序；自底向上：LR） 语义分析（属性文法、各种语句的语法制导翻译） 运行环境（存储分配

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

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

6、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、SQL(数据定义、数据操作) 命令语言(Command Language) 控制系统的工作以功能

7、封装为特征 如UNIX上的shell,1.2 翻译系统,翻译程序(Translator) 将某一种语言描述的程序(源程序Source Program)翻译成等价的另一种语言描述的程序(目标程序Object Program)的程序。,翻译程序,源程序,目标程序,(*.C / *.PAS),(*.OBJ / *.EXE),1.2 翻译系统,解释程序(Interpreter) 口译与笔译（单句提交与整篇提交）,源程序,输入数据,计算结果,解释程序,1.2 翻译系统,编译程序(Compiler) 高级语言程序汇编/机器语言程序,源程序,目标程序,编译程序,1.2 编译系统,SP Compiler S-

8、Source O-Object OP P-Program Input RS RS-Run Sys. Output,编译系统(Compiling System) 编译系统=编译程序+运行系统,支撑环境、 运行库等,1.2 翻译系统,其它： 诊断编译程序（Diagnostic Compiler) 优化编译程序（Optimizing Compiler) 交叉编译程序（Cross Compiler) 可变目标编译程序（Retargetable Compiler) 并行编译程序（Parallelizing Compiler） 汇编程序(Assembler)、交叉汇编程序(Cross Assembler)

9、、反汇编程序（Disassembler),1.2 翻译系统汇总,ML MLP Assembler Disassembler AL ALP Translator Compiler Data HL HLP Interpreter Result,M-Machine L-Languge P-Program A-Assemble H-High Level,1.3 编译系统的功能分析,程序分析 词法、语法、语义 分析综合 语句的翻译、代码生成 标识符处理：左值与右值的绑定(binding) 变量： 存储单元 函数： 目标代码序列,1.4 编译程序总体结构,目标代码生成器,代码优化器,语义分析与中间代码生成

10、器,语法分析器,1. 词法分析,例： main( ) printf(“hello”); ,结果 IDN main ( ) IDN printf ( STR hello ) ; ,1、词法分析,词法分析由词法分析器完成(Lexical Analyzer)，词法分析器又叫做扫描器(Scanner) 词法分析器从左到右扫描源程序发现一个字符串，则将该字符串转换成单词(记号Token)串；同时要：查词法错误，进行标识符登记符号表管理。 输入：字符串 输出：(种别码，属性值)序对 属性值token的机内表示,2、语法分析,语法分析由语法分析器(Syntax Analyzer)完成，语法分析器又叫Pars

11、er。 功能： Parser实现“组词成句” 将词组成各类语法成分：表达式、因子、项，语句，子程序 构造分析树 指出语法错误 指导翻译 输入：Token序列 输出：语法成分,2. 语法分析,res=fact*(term1+term2);,*,；,赋值语句,表达式,=,）,（,fact,表达式,res,表达式,表达式,表达式,表达式,+,term1,term2,3. 语义分析,功能：分析由语法分析器识别出的语法单位的语义 获取标识符的属性：类型、作用域等 语义检查：运算的合法性、取值范围等 子程序的静态绑定：代码的相对地址 变量的静态绑定：数据的相对地址,4. 中间代码生成,中间代码(inter

12、mediate Code) 例:id1+id2*id3,后缀表示(逆波兰Anti- Polish Notation) id1id2id3 * + 前缀表示(波兰Polish Notation) + id1*id2id3,四元式表示 (三地址码) 1 (*,id1,id2,T1) 2 (+,id3 ,T1 ,T2),三元式表示 1 (* ,id2,id3) 2 (+,id1,(1),4. 中间代码生成,中间代码的特点 简单规范 与机器无关 易于优化与转换,三地址码的另一种表示形式 T1=id2*id3 T2=id1*T1,其它类型的语句 例：printf(“hello”) x := s （赋值）

13、 param x （参数） call f （函数调用） 注释 s 是 hello 的地址 f 是函数 printf 的地址,对中间代码的优化处理:对代码进行等价变换以求提高执行效率提高运行速度和节省存储空间 与机器无关的优化 与机器有关的优化,5. 代码优化,与机器无关的优化,局部优化 常量合并：常数运算在编译期间完成，如8+9*4 公共子表达式的提取:基本块内 循环优化 强度削减 用较快的操作代替较慢的操作 代码外提 将循环不变计算移出循环,与机器有关的优化,寄存器的利用 将常用量放入寄存器，以减少访问内存的次数 体系结构 MIMD、SIMD、SPMD、向量机、流水机 存储策略 根据算法访存

14、的要求安排：Cache、并行存储体系减少访问冲突 任务划分 按运行的算法及体系结构，划分子任务(MPMD),6. 目标代码生成（Code Generator）,将中间代码转换成目标机上的机器指令代码或汇编代码 确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组） 制定从中间代码到目标代码的翻译策略或算法 目标代码的形式 具有绝对地址的机器指令 汇编语言形式的目标程序 模块结构的机器指令（需要链接程序）,7、表格管理,管理各种符号表（常数、标号、变量、过程、结构），查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。 辅助语法检查、语义检查 完成静态

15、绑定、管理编译过程 Hash表、链表等各种查、填表技术,8、错误处理,进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化） 词法：拼写 语法：语句结构、表达式结构 语义：类型不匹配,编译系统,模块分类,分析：词法分析、语法分析、语义分析、中间代码生成 综合：代码优化、目标代码生成 辅助：符号表管理、出错处理 8项功能对应8个模块,例 一个语句的翻译,9 编译的遍（Pass）,根据系统资源的状况、运行目标的要求等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。 如：首遍构造语法树，二遍处理中间表示，增加信息等。 遍可以和阶段相对应，也可无关 单

16、遍代码不太有效,10、编译的前端与后端,前端 与源语言有关、与目标机无关的部分 词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化 后端 与目标机有关的部分 与机器有关的代码优化、目标代码生成,1.5 编译程序的生成,设计目标 目标程序小，执行速度快。 编译程序小，执行速度快。 诊断能力强，可靠性强。 可移植性，可扩充性。 如何实现编译器？ 直接用可运行的代码编制太费力！ 自举-使用语言提供的功能来编译该语言自身。“第一个编译器是怎样被编译的？”,问题：直接在一个机上实现C语言编译器，还有别的技术么？ 解决： 用汇编语言实现一个子集的编译程序(P0人) 用汇编程序处理该程序,得到

17、(P2:可直接运行) 用子集编制语言的编译程序(P3人) 用P2编译P3，得到P4,1) 编译程序的自展技术,2) 利用编译程序自动生成器,词法分析器的自动生成程序,词法规则说明,词法分析程序,(C程序),输入： 词法（正规表达式） 识别动作（程序段） 输出： yylex( ) 函数,语法分析器的自动生成程序,语法规则说明,语法分析程序,(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 | DIGIT day DIGIT DIGIT | DIGIT year