编译原理内容小结

编译原理内容小结1词法分析器语法分析器语义分析与中间代码生成器代码优化目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码表 格 管 理出 错 处 理源程序目标代码2主要内容编译程序及作用高级语言的语法描述构造一个编译器3一、编译程序及作用程序设计语言的定义语法：组成程序中各个语法成分的一组规则语义：程序中各个语言成分的含义语用：语言符号及其使用者之间的关系4编译程序及作用翻译程序（Translator）

将某个语言程序（源语言程序—SourceProgram）转换成等价的另一种语言描述的程序（目标程序—ObjectProgram）的程序。源程序(*.c/*.PAS)翻译程序目标程序(*.OBJ/*.EXE)5编译程序及作用构造编译器确定源语言确定目标语言选择编译方法6二、高级语言的语法描述语言的分类程序语言的语法描述字符串句子文法分类 7程序语言组成语言——形式化的内容提取语言(language)：满足一定条件的句子集合句子(sentence)：满足一定规则的单词序列单词(token)：满足一定规则的字符串语言字和组合字的规则8程序语言组成基本定义字母表、符号串、句子、语言设是一个字母表，

L

*，L称为字母表上的一个语言（language），

xL，x为L的一个句子语言是由无穷个句子组成的，就无法用枚举法描述，需要用有穷的方法来描述无穷性质的语言，一般有以下两类等价的方法：文法和自动机9文法的形式定义文法G为一个四元组：G=(VT,VN,S,P)VT：终结符(Terminal)集VN：非终结符(Variable)集,VT

VN=

S：开始符号(StartSymbol),S

VNP：产生式A

,A(VTVN)+，且A中至少有一个VN中的元素，(VTVN)*10文法的形式定义例G(E)：(VT,VN,S,P)VT：{(,),+,*,i}VN：{E}S：EP：EE+E|E*E|(E)|i11文法的形式定义句型句子语言推导句柄语法树二义性文法的分类12三、编译器的构造词法分析器语法分析器语义分析与中间代码生成器代码优化目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码表 格 管 理出 错 处 理13词法分析器作用：从左到右扫描源程序，并将该字符串转换成单词（Token）串；同时：检查词法错误、进行标识符登记正规式有限自动机正规文法14语法分析器功能：检查由扫描器输出的单词符号序列是否符合该语言的文法，实现“组词成句”，构造分析树，指出语法错误。自上而下分析递归下降法预测分析表法自下而上分析算符优先文法LR分析法15语义分析功能：分析由语法分析器给出的语法单位的语义。属性文法在CFG的基础上，为每个文法符号配备若干相关的值，以代表与文法相关的信息中间代码生成中间语言形式语句的翻译16代码优化功能：对代码进行等价变换以获取更高的执行效率（提高运行速度、节省存储空间）

。优化的分类与机器有关的优化：局部优化、循环优化、控制流优化与机器无关的优化：与寄存器、指令、存储策略、体系结构、任务规划相关17代码生成功能：将中间代码转换成目标机上的机器指令代码或者汇编代码，完成最后的翻译，可以运行。生成的代码绝对的机器代码可重定位的代码汇编代码18运行时存储空间组织目标程序运行时的活动运行存储的划分静态存储分配栈式动态存储分配堆式动态存储分配19符号表功能：将中间代码转换成目标机上的机器指令代码或者汇编代码，完成最后的翻译，可以运行。组织方式定长方式、变长方式线性表、二叉树、散列表20Position:=initial+rate*60词法分析器语法分析器id1:=id2+id3*60语义分析器代码优化器T1:=inttoreal(60)T2=id3*T1T3=id2+T2id1=T3代码生成器T1:=id3*60id1=id2+T1MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id11position…2initial…3rate…4……符号表:21词法分析器语法分析器语义分析与中间代码生成器代码优化目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码描述和识别单词正规式

正规文法DFA