编译原理内容小结

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理内容小结,1,词法分析器,语法分析器,语义分析与中间代码生成器,代码优化,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,表格管理,出错处理,源程序,目标代码,2,主要内容,编译程序及作用,高级语言的语法描述,构造一个编译器,3,一、编译程序及作用,程序设计语言的定义,语法：组成程序中各个语法成分的一组规则,语义：程序中各个语言成分的含义,语用：语言符号及其使用者之间的关系,4,编译程序及作用,翻译程序,（,Translator）,将某个语言程序（源语言程序,Source Program,）,转换成等价的另一种语言描述的程序（目标程序,Object Program,）,的程序。,源程序,(*.,c/*.PAS),翻译程序,目标程序,(*.,OBJ/*.EXE),5,编译程序及作用,构造编译器,确定源语言,确定目标语言,选择编译方法,6,二、高级语言的语法描述,语言的分类,程序语言的语法描述,字符串,句子,文法分类,7,程序语言组成,语言形式化的内容提取,语言,(,language),：,满足一定条件的句子集合,句子,(,sentence),：满足一定规则的单词序列,单词,(,token),：满足一定规则的字符串,语言字和组合字的规则,8,程序语言组成,基本定义,字母表、符号串、句子、语言,设,是一个字母表，,L,*,，,L,称为字母表上的一个语言（,language），,x,L ，x,为,L,的一个句子,语言是由无穷个句子组成的，就无法用枚举法描述，需要用有穷的方法来描述无穷性质的语言，一般有以下两类等价的方法：,文法和自动机,9,文法的形式定义,文法,G,为一个四元组：,G = (V,T, V,N, S, P),V,T,：,终结符(,Terminal),集,V,N,：,非终结符(,Variable),集,V,T,V,N,=,S：,开始符号(,Start Symbol), S,V,N,P：,产生式,A, ,A(V,T,V,N,),+,，,且,A,中至少有一个,V,N,中的元素,，, (V,T,V,N,),*,10,文法的形式定义,例,G(E)：(V,T, V,N, S, P),V,T,： (, ), +, *, i,V,N,： E ,S： E,P：,E, E + E | E * E | ( E ) | i,11,文法的形式定义,句型,句子,语言,推导,句柄,语法树,二义性,文法的分类,12,三、编译器的构造,词法分析器,语法分析器,语义分析与中间代码生成器,代码优化,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,表格管理,出错处理,13,词法分析器,作用：,从左到右扫描源程序，并将该字符串转换成单词（,Token,）,串；同时：检查词法错误、进行标识符登记,正规式,有限自动机,正规文法,14,语法分析器,功能：检查由扫描器输出的单词符号序列是否符合该语言的文法，实现“组词成句”，构造分析树，指出语法错误。,自上而下分析,递归下降法,预测分析表法,自下而上分析,算符优先文法,LR,分析法,15,语义分析,功能：,分析由语法分析器给出的语法单位的语义,。,属性文法,在,CFG,的基础上，为每个文法符号配备若干相关的值，以代表与文法相关的信息,中间代码生成,中间语言形式,语句的翻译,16,代码优化,功能：,对代码进行等价变换以获取更高的执行效率（提高运行速度、节省存储空间）,。,优化的分类,与机器有关的优化：局部优化、循环优化、控制流优化,与机器无关的优化：与寄存器、指令、存储策略、体系结构、任务规划相关,17,代码生成,功能：,将中间代码转换成目标机上的机器指令代码或者汇编代码，完成最后的翻译，可以运行,。,生成的代码,绝对的机器代码,可重定位的代码,汇编代码,18,运行时存储空间组织,目标程序运行时的活动,运行存储的划分,静态存储分配,栈式动态存储分配,堆式动态存储分配,19,符号表,功能：,将中间代码转换成目标机上的机器指令代码或者汇编代码，完成最后的翻译，可以运行,。,组织方式,定长方式、变长方式,线性表、二叉树、散列表,20,Position:=initial+rate*60,词法分析器,语法分析器,id,1,:=id,2,+id,3,*60,语义分析器,代码优化器,T,1,:=inttoreal(60),T,2,= id,3,*T,1,T,3,= id,2,+T,2,id,1,= T,3,代码生成器,T,1,:=id,3,*60,id,1,= id,2,+T,1,MOVF id,3, R,2,MULF #60.0, R,2,MOVF id,2, R,1,ADDF R,2, R,1,MOVF R,1, id,1,1,position,2,initial,3,rate,4,符号表:,21,词法分析器,语法分析器,语义分析与中间代码生成器,代码优化,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,描述和识别单词,正规式,正规文法,DFA,和,NFA,自上而下：,LL,文法,自下而上：,LR,文法,描述和识别语法单位,中间代码表示形式,属性文法,根据属性文法进行翻译,中间代码程序的程序流图,局部优化,循环优化,生成高效的目标代码,22,