编译原理讲义全.

2013-2014第二学期SunYat-SenUniversity2011级电子政务JollinZhu(11331448)编译原理[]2013-2014学年度第二学期----中山大学软件学院----软件工程2011级电子政务方向----编译原理课程讲义授课老师：娄定俊编辑：朱琳JolinZhu2011级电子政务编译原理1第一章引论*问题的提出:没有软件的计算机能执行的语言(指令)是非常低级的语言,即机器语言,例如:00010100001000000011011000000010而面向人的高级语言直观,书写方便,不易出错,例如:IFijTHENi:=j+1我们的问题是:如何使高级语言写的程序能在计算机上执行?编译(compiling):代表从面向人的源语言表示的算法到面向硬件的目标语言表示的算法的一个等价变换.§1.1翻译和解释一.解释器(Interpreter)对于一种程序设计语言PL,可以定义一种抽象机,PL的运算,数据结构和控制结构是这种机器的存储元素和指令.实现这种抽象机的软件称为解释器.解释器对源程序的输入直接执行源程序中说明的操作.(见书P2)二.编译器(compiler)编译器是将源语言程序通过翻译序列(SL,L1),(L1,L2),…,(Lk,TL)变成和源程序等价的目标语言程序的软件.其中SL称为源语言,TL称为目标语言,Li(i=1,2,…,k)称为中间语言.*把高级语言程序翻译成低级目标(机器)语言程序的软件即是编译程序.(见书P2)能够完成一种语言到另一种语言变换的软件称为翻译器.§1.2编译的阶段(Phases)一.编译阶段的划分(见书P5):二.各阶段的功能1.词法分析(LexicalAnalysis)词法分析读源程序的字符序列,识别一个个单词(lexeme),并把它们组成记号(token)流.记号流的每个记号代表逻辑上有内聚力的字符序列;例如:标识符,关键字,标点符号或算符.形成记号的字符序列叫做该记号的单词.例如:(见书P7)*注意:记号是单词在编译程序内部的表示.2.语法分析(Syntaxanalysis)语法分析把源程序的记号序列分组成语法短语,它识别记号序列的层次结构.源程序的语法短语常用分析树来表示.例如:(见上例)2011级电子政务编译原理23.语义分析(Semanticanalysis)语义分析阶段检查源程序的语义错误,并为以后的代码生成阶段收集类型信息.它使用语法分析阶段确定的层次结构来标识表达式的算符和运算对象及语句的语义.语义分析所作的检查包括:运算对象类型的相容性,名字是否定义,形参与实参的一致性等.例如:(见上例)4.中间代码生成(Intermediatecodegeneration)将源语言的记号流翻译成某种中间语言形式,这种中间语言程序是某种抽象机的程序.中间语言有两个性质:它容易产生和容易翻译成目标程序.例如:(见上例)5.代码优化(Codeoptimization)代码优化阶段试图改进中间代码,以便产生较快的机器代码.代码优化分为:1.独立于机器的代码优化;和2.依赖于机器的代码优化;例如:(见上例)6.代码生成(Codegeneration)代码生成阶段生成可以重定位的机器代码或汇编码.*在此阶段,为源程序所用的每个变量选择存储单元和分配寄存器,把中间代码翻译成等价的机器指令序列.例如:(见上例)7.符号表管理(Symbol-tablemanagement)记录源程序中使用的标识符和收集每个标识符(identifier)的各种属性(attribute).*这些属性提供标识符的存储分配,类型和作用域信息,如果是过程名标识符,还有参数个数和类型,参数传递方式和返回值类型.符号表管理阶段与上述各阶段交互作用.8.错误诊断和报告(Errordetectionandreport)每个阶段都可能碰到错误.在发现错误后,该阶段必须处理此错误,使得以后的编译可以继续进行,以便进一步察觉源程序的其它错误.§1.3阶段的分组一.前端和后端1.前端(Front-end):是只依赖于源语言,几乎独立于目标机器的阶段或阶段的一部分组成的.通常是:词法分析,语法分析,符号表建立,语义分析和中间代码生成.2.后端(back-end):是指编译器中依赖于目标机器的部分.它们一般独立于源语言而与中间代码有关.通常包括:代码优化,代码生成和出错处理,符号表操作.2011级电子政务编译原理3二.遍(pass)编译的几个阶段常用一遍来实现.一遍包括读一个输入文件和写一个输出文件.即扫描一遍被编译的程序.编译的分遍常常因实现的方便和需要而定.例如:把词法分析,语法分析,语义分析和中间代码生成组成一遍.三.减少遍数在实现编译程序时,我们希望尽量减少遍数,因为每遍都要花时间来读写中间文件.但有时由于某种需要必须分多遍扫描.§1.4编译程序的伙伴一.预处理器(preprocessor)预处理器完成以下任务:1.将同一个程序的保存在不同文件中的几个模块安装在一起.2.扩展宏定义3.语言功能扩充二.汇编器(Assembler)编译产生的目标代码可能是汇编码(assemblycode),需要汇编器将其翻译成可重定位的(relocatable)机器代码.三.连接编辑器(Linker)大的源程序常常分段编译,需要连接编辑器将分段编译后产生的代码连接在一起,成为可在机器内运行的程序.连接编辑器解决一个文件中的代码访问其它外部文件中存储地址的问题.四.装配器(Loader)装配器把所有可执行的目标文件中的代码一起装入内存执行.*阅读:教材1.1,1.2节第二章词法分析§2.1词法分析器(lexicalanalyzer)的作用一、作用词法分析阶段的主要任务是读输入字符流,产生用于语法分析的记号序列.*词法分析器作为语法分析器(parser)的一个子程序或联立程序来实现,当收到来自分析器的“取下一个记号”的命令时,词法分析器读输入字符,直到它能确认下一个记号为止.然后,词法分析器将该记号返回给语法分析器.词法分析器的几个其它任务:1.删去注释和无用空白;2.把错误信息和源程序联系起来;3.作预处理.二、分离词法分析的理由2011级电子政务编译原理4我们将词法分析阶段从语法分析阶段中分离出来的理由是:1.简化设计是重要的原因;2.编译器的效率会改进;3.编译的可移植性加强.三、记号﹑模式﹑单词1.记号(token)单词在编译程序内部的表示.很多字符串有同样的记号输出.2.模式(pattern)具有同一记号输出的字符串集合由叫做模式的规则来描述.*模式能匹配该集合的任一字符串.3.单词(lexeme)是源程序中具有逻辑含义的极小字符串.4.例子(见书P112)*我们把记号作为源语言文法的终结符.5.记号包括:关键字﹑算符﹑标识符﹑常数﹑文字串和标点符号,如括号﹑逗号和分号.五.记号的属性(attribute)由于一个记号代表不只一个单词,必须提供附加信息,区别对应同一记号的不同单词.另外,编译中后面的阶段需要用到这些单词的属性.1.记号的内部形式(类码,属性)通常类码标识不同的记号,属性为指向该标识符在符号表中条目的入口的指针.对常数来说,则是常数的值.2.例子:FORTRAN中E=M*C**2输出:(见书P113)§2.2输入缓冲区(Inputbuffering)*由于词法分析器是编译器中逐个读源程序字符的唯一阶段,编译的相当可观的时间消耗在词法分析阶段.所以加快词法分析是编译器设计需要关心的问题.一.缓冲区对*设两半缓冲区,每一半是4096字节,即磁盘的一块*两个指针*工作原理*向前扫描的情况例:FORTRAN语言中DO5I=1.25DO5I=1,25二.标记*缓冲区结束标记*文件尾标记2011级电子政务编译原理5*工作原理§2.3记号的说明一.串和语言1.字母表(alphabet):Σ非空﹑有穷集2.串(string):是字母表中符号的有穷序列.也叫句子或字.例如:Σ={a,b},串:s=abb,串长|s|=3空串:ε,|ε|=03.语言(language):字母表上串的集合例如:Σ={a,b},L={a,b,aab,abb,ba}空语言:φ,只含空串的语言:{ε}4.连接运算(concatenation):设x=ab,y=bb,则xy=abbbx,εx=xε=x指数(exponentiation):s0=ε,si+1=sis,其中s是任意串.二.语言的运算(Operationsonlanguages)设L﹑M为字母表Σ上的语言:1.L∪M={x|x∈L或x∈M}(union)LM={xy|x∈L且y∈M}(concatenation)指数:L0={ε},Li+1=LiL(exponentiation)L*=0iiL((Kleene)closure)L+=1iiL(positiveclosure)2.例子:设L={A,B,…,Z,a,b,…,z},D={0,1,2,…,9}例1:L∪D例2:LD例3:L4例4:L*例5:L(L∪D)*例6:D+*阅读:教材3.1,3.2,3.3.1,3.3.2节作业1:1.将下列程序的字符序列转换为记号序列,并给每个记号以合理的属性值.PASCAL2011级电子政务编译原理6Functionmax(i,j:integer):integer;/*returnmaximumofintegersiandj*/beginifijthenmax:=ielsemax:=jend;三.正规式(Regularexpression)正规式(正则式)代表一个语言.1.定义:给定字母表Σ,定义Σ上的正规式如下:(1)ε是正规式,表示{ε};(2)如果a∈Σ,那么a是正规式,表示{a};(3)假定r和s都是正规式,分别表示语言L(r)和L(s),那么a)(r)|(s)是正规式,表示L(r)∪L(s);b)(r)(s)是正规式,表示L(r)L(s);c)(r)*是正规式,表示(L(r))*;d)(r)是正规式,表示L(r).除此以外,其它的不是正规式.正规式表示的语言叫正规集(regularset).2.约定*优先级最高,左结合(leftassociative);连接(concatenation)优先级其次,左结合;|优先级最低,左结合;可以删除不必要的括号.例如:(a)|((b)*(c))可写成a|b*c3.例子:令∑={a,b}a|b表示{a,b}(a|b)(a|b)表示{aa,ab,ba,bb},也可用aa|ab|ba|bb表示.*同一语言的正规式表示不唯一.a*表示{ε,a,aa,aaa,…}(a|b)*表示{ε,a,b,aa,ab,ba,bb,aaa,aab,…}a|a*b表示{a,b,ab,aab,aaab,…}4.正规式的运算规则*两个正规式相等,当且仅当它们代表的语言相同.设r,s和t是任意正规式.1)r|s=s|r2)r|(s|t)=(r|s)|t3)(rs)t=r(st)4)r(s|t)=rs|rt(s|t)r=sr|tr2011级电子政务编译原理75)εr=r,rε=r6)r*=(r|ε)*7)r**=r*证明举例:证明(4):要证L(r(s|t))=L(rs|rt).L(r(s|t))=L(r)(L(s)∪L(t))={xy|x∈L(r)∧(y∈L(s)∨y∈L(t))}={xy|(x∈L(r)∧y∈L(s))∨(x∈L(r)∧y∈L(t))}={xy|x∈L(r)∧y∈L(s)}∪{xy|x∈L(r)∧y∈L(t)}=L(r)L(s)∪L(r)L(t)=L(rs|rt)证明(6):要证L(r*)=L((r|ε)*)x,设x∈L(r*)=0)(iirL.故x∈L(r)k由于L(r)L(r|ε)=L(r)∪L(ε)L(r)kL(r|ε)k,故x∈L(r|ε)k,从而x∈L((r|ε)*)=0)|(iirL.因而L(r*)L((r|ε)*).x,设x∈L((r|ε)*)=iiiiLrLrL))()(()|(00.故x∈(L