编译原理复习陆筱霞

《编译原理复习陆筱霞》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理复习课陆筱霞公共邮箱：zzti_soft@126.com密码：soft_zzti第一章引论源语言程序目标语言程序翻译程序翻译一.什么是编译程序翻译程序把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序高级语言程序机器语言程序结果编译程序翻译运行一.什么是编译程序编译程序(compiler)把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序诊断编译程序优化编译程序交叉编译程序可变目标编译程序一.什么是编译程序解释程序把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身源程序结果解释程

2、序解释执行二.编译过程编译程序的工作一般分为五个阶段:词法分析语法分析中间代码产生优化目标代码产生1.词法分析任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FORI:=1TO100DO保留字标识符等符整常数保留字整常数保留字2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则描述工具：上下文无关文法Z:=X+0.618*Y算术表达式，赋值语句3.中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。依循的原则：语义规则中间代码:三元式，四元式，树

3、形结构等Z:=X+0.618*Y翻译成四元式为(1)*0.618YT1(2)+XT1T2(3):=T2_Z4.优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则5.目标代码产生任务:把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行可重新定位指令代码:需要连接装配汇编指令代码:需要进行汇编三.编译程序结构编译程序总框四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器2.表格和表格管

4、理常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。格式:名字信息3.出错处理出错处理程序：发现源程序中的错误，把有关错误信息报告给用户语法错误语义错误4.遍(pass)所谓"遍"，就是对源程序或源程序的中间表示从头到尾扫描一次。阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。5.编译前端与后端编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化编译后端：与目标机有关，与目标机有关的优化，目标代码产生优点：减少对内存容量的要求，程序逻辑结构清晰;优化更充分，有利于移植。不足:编译程序运行的效率低源语言中间语言

5、目标语言前端后端第二章高级语言及其语法描述一.语法程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。规则的一部分称为词法规则，另一部分称为语法规则（或产生式规则）。语法词法规则：单词符号的形成规则。单词符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错

6、误、二义性和不完整性形式描述：操作语义(PL/1)指称语义(ADA)代数语义(PASCAL)2.3程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}即是空集，表示一个不含任何元素的集合。∑*的子集U和V的连接（积）定义为UV＝{

7、U&V}设：U＝{a,aa}V＝{b,bb}那么：UV={ab,abb,aab,aab

8、b}V自身的n次积记为Vn=VV…V规定V0={}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*，称V+是V的正规闭包。闭包V*中每个符号串都是由V中的符号串经有限次连接而成的。2.3.1上下文无关文法文法：描述语言的语法结构的形式规则上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PV