计算机程序编译原理第1章引论.ppt
编译原理Compiler Principles,刘玉葆中山大学计算机科学系,课程要求,教学方式：理论(59)+实践(13)考核方式：考试(70%)+作业和实验(30%)先修课程:离散数学数据结构汇编语言程序设计语言参考书籍：吕映芝等，编译原理，清华大学出版社 陈火旺等，程序设计语言编译原理，国防工业出版社 李建中等译，编译原理，机械工业出版社（美Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman，Compilers:Principles,Techniques,and Tools）,第1章引论,什么是编译程序编译程序的工作过程 编译程序的结构编译程序的组织方式编译程序的自展、移植和自动化 编译程序的编写系统 并行编译程序 本章小结,翻译程序,程序设计语言1、低级语言：机器语言、汇编语言特点：用机器语言编写程序难写、难读、难修改、编写程序的效率低下2、高级语言：FORTRAN1、C语言等特点：独立与机器、接近自然语言、编写程序难写、难读、难修改、编写程序的效率高翻译程序计算机不能直接执行由用高级语言编写的程序，而只能执行机器语言程序，因此，用高级语言编写的程序必须由一个翻译程序翻译成机器语言程序。翻译的方式：（1）编译方式；（2）解释方式,编译方式,先将源程序翻译成汇编语言或机器语言程序（目标程序），然后再执行它。,解释方式,和编译方式不同，解释方式并不事先生成目标程序然后再执行，而是对源程序边解释边执行。,编译程序的工作过程,词法分析，扫描源程序，分解和识别出每个单词，并把单词表示成相应的机内表示。语法分析，把单词符号串分解成各类语法单位，如表达式、语句等。语义分析，对源程序进行语义检查，保证标识符和常数的正确使用，为代码生成收集信息。中间代码生成，根据语义规则，将源程序表示成某种中间代码的形式，如三元式，四元式等。中间代码优化，调整和改变中间代码中某些操作的次序，最终生成更加高效的目标代码。目标代码生成，将中间代码转换成等价的目标代码。,词法分析,例.某源程序片断如下：begin var sum,first,count:real;sum:=first+count*10end.,保留字begin保留字var标识符sum(id1)逗号,标识符first(id2)逗号,标识符count(id3)冒号:保留字real分号;标识符sum赋值号:=标识符first加号+标识符count乘号*整数10保留字end界符.,id1:=id2+id3*10,语法分析,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*10 的语法树,id1sum,id2first,id3count,10,:=,id1,+,id2,*,id3,10,（形式2）,（形式1）,语义分析,id1:=id2+id3*10 的语法树,:=,id1,+,id2,*,id3,10,中间代码生成以及优化,源程序 sum:=first+count*10生成的中间代码可以是：(inttoreal10-t1)(*id3t1t2)(+id2t2t3)(:=t3-id1),四元式：（运算符，运算对象1，运算对象2，结果）,优化后的代码(*id310.0t1)(+id2t1id1),目标代码生成,(*id310.0t1)(+id2t1id1),sum:=first+count*10,MOVFid3,R2MULF#10.0,R2MOVFid2,R1ADDFR1,R2MOVR1,id1,编译程序的结构,表格处理程序,出错处理程序,源程序,语法分析程序,语义分析成程序,中间代码生成程序,中间代码优化程序,目标代码生成程序,词法分析程序,目标程序,编译程序的组织方式,1、前端和后端前端，主要依赖源程序，通常包括词法分析、语法分析、语义分析、中间代码生成和中间代码优化。后端，主要依赖硬件系统和机器指令系统，包括目标代码生成。2、分遍遍：对源程序或中间代码程序，从头至尾扫描一次并完成所规定的工作称为一遍。分遍的优点：多遍功能独立，相互联系简单，逻辑结构清晰。缺点：增加了编译程序的长度和编译时间。,编译程序的自展、移植与自动化,1、高级语言的自编译性 高级语言的自编译性，是指可以用这个语言来编写自己的编译程序。2、编译程序的自展技术具有自编译性的语言可以按照自展技术来构造其编译程序。将源语言L分解成核心部分L0与扩充部分L1,L2,Ln，使得对核心部分L0的一次或多次扩充得到源语言L3、编译程序的移植编译程序可以通过移植得到。4、编译程序的自动化Lex：词法分析生成器Yacc：语法分析生成器,编译程序编写系统,将有助于减轻编写翻译程序（包括编译程序、汇编程序、解释程序）工作的任何软件系统或工具包，统称为翻译程序编写系统（Translator Writing System,TWS）。TWS的目的在于简化编译程序的实现。因此，TWS通常包含了编译程序所必须执行的各种基本操作，如建立、查找符号表，生成目标代码，出错处理等操作。TWS可分为三类。（1）自动产生编译程序；（2）面向语法的符号加工程序；（3）可扩充语言组成的集合。,并行编译程序,串行编译程序：适合于SISD结构计算机的编译程序。并行编译程序：适合于SISD和MIMD结构计算机，并具有并行处理功能的编译程序。并行编译程序主要实现对并行语言的翻译。SISD 单指令流单数据流，传统的单处理机属于SISD计算机。MIMD 多指令流多数据流，包括了大多数多处理机及多计算机系统。我国的YH-II型计算机是这种类型的计算机。,小结,编译程序功能编译程序工作过程编译程序结构编译程序组织方式编译程序的自编性，自展性以及自动化编译程序的编写系统研究前沿：并行编译习题一：1.4.1.5.,
