《编译原理》第1章 绪论

编译原理编辑ppt自我介绍姓名：刘善梅QQ：30683530办公室：逸夫楼C427

邮箱：

lsmei@2编辑ppt课程介绍两门独立的课程：理论（48学时）

实验（16学时）考试成绩组成

理论：平时作业和考勤占20%，期末结业考试占80%；

实验：根据实验报告和程序源代码评分，实验报告占40%,程序源代码占60%。课程特点：难！3编辑ppt开课目的：

介绍设计与构造程序设计语言编译程序的原理与方法源程序编译程序目标程序连接可执行程序预备知识：形式语言与自动机、两门以上的高级程序设计语言汇编语言数据结构等How?4编辑ppt教学要求通过课程的学习和实验的完成，

应该清楚的理解一个编译程序是如何工作的；

如果在以后遇到了任何一个程序设计语言，应该知道如何实现这个语言的多数机制；

应具有一定的使用编译构造工具开发编译程序的经验；

会将所学的常用技术和算法应用于类似的软件的设计和实现中。5编辑ppt理论课内容简介：第一章：绪论第二章：编译基础(形式语言

、有穷自动机等）第三章：词法分析第四章：语法分析第五章：语法制导翻译和中间代码生成第七章：程序运行时的存贮分配问题第八章：代码优化第九章：目标代码生成第六章：符号表6编辑ppt实验课内容简介：第一次课：词法分析（4学时）第二次课：语法分析（4学时）第三次课：词义分析、代码生成（4学时）第四次课：小型C语言编译器设计（4学时）详细实验内容请见实验要求和实验指导书7编辑ppt教材：《编译原理》（第2版），张素琴、吕映芝、蒋维杜、戴桂兰，清华大学出版社2004参考书：教材及主要参考书Compilers:Principles,Technigues,andToolsAlfredV.Aho,RaviSethi,JeffreyD.Ullman,Addison-Wesley,1986.译著版：机械工业出版社，2003，李建中，姜守旭译。(龙书）

中文名：编译原理技术和工具ModernCompilerImplementationinJava

ModernCompilerImplementationinCAndrewW.Appel，人民邮电出版社影印，2005（虎书）中文名：现代编译原理

AdvancedCompilerDesignandImplementation

StevenS.Muchnick,1997.机械工业出版社影印，2003（鲸书）

中文名：高级编译器设计与实现8编辑ppt内地陈火旺（国防科大版）

陈意云（中国科技大学版）

王生原等（人民邮电版）

王生原等（清华大学第三版）主要参考书编辑ppt第一章绪论编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。编译器源程序目标程序错误信息Fortran、Pascal、Java、C…..另一种程序设计语言、汇编语言、机器语言1.1什么是编译程序10编辑ppt什么是编译程序

编译程序通常是从较高级语言的程序翻译至较低级语言的程序，如C代码汇编代码aCcompilerC++代码汇编代码aC++compilerC++代码C代码anotherC++compilerJava代码Bytecode代码aJavacompiler编辑ppt1.2编译过程概述编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。一段英文翻译成中文，需经下列步骤：识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析对译文进行修饰写出最后的译文编译程序词法分析代码优化语法分析语义分析及中间代码生成目标代码生成构成编译程序各个阶段Iamateacher.12编辑ppt编译器的各个阶段：编译器是分阶段执行的。每个阶段将源程序从一种表示转换成另一种表示源程序词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器编译的各个阶段13编辑ppt各分析阶段随着编译器各个阶段的进展，源程序的内部表示不断地发生变化。以a=b+c*d为例1。词法分析读入源程序完成的任务：识别出单词：a、=、b、+、c、*、d并用记号方式表示识别出的单词关键字、标识符、常数、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*记号表示逻辑上相关的字符序列，常用整数来表示上述单词表示为：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*),(25,d)14编辑ppt程序文本Ifx=ythenz:=1elsez:=2;经词法分析，变成一个个单词if,x,=,y,then,z,:=,1,else,z,:=,2,;语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符串是一个单词符号。又例，

编辑ppt从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出(拼)一个个的单词（符号）单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括—各类型的常数、保留字、标识符、运算符、界符等等。

词法分析—第一步识别单词编辑ppt

position:=initial+rate*60;

单词类型 单词值标识符1(id1) position算符(赋值) :=标识符2(id2) initial算符(加) +标识符3(id3) rate算符(乘) *整数 60分号 ；词法分析编辑ppt语法分析在词法分析的基础上，根据语言的语法规则，把单词符号串组成各类语法单位.具体的说，语法分析是在单词流的基础上建立一个层次结构-----建立语法树赋值语句标识符=表达式id1表达式标识符id2+表达式表达式*标识符id3表达式

整数6018编辑ppt语法分析举例id1:=id2+id3*60;（Pascal）语法规则<赋值语句>::=<标识符>“:=”<表达式><表达式>::=<表达式>“+”<表达式><表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”<表达式>::=<标识符><表达式>::=<整数><表达式>::=<实数>编辑ppt

赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*编辑pptid1:=id2+id3*60 :=+60*id1id2id3编辑ppt语义分析阶段语义分析利用语法分析阶段确定的层次结构来识别表达式和语句中的操作信息及类型信息=+ab*cdtemp1=c*dtemp2=b+temp1temp1temp2a=temp222编辑ppt语义分析

句子的结构理解了，扑捉它的“含义”如：杰克说杰瑞把他的作业落在了家里。“他的”是谁的？又：杰克说杰克把他的作业落在了家里。几个杰克？编辑ppt杰克把她的作业落在了家里。（杰克是男生）“杰克”和“她的”不一致。“杰克”和“他的”才匹配语义分析编辑ppt中间代码生成阶段本阶段将产生源程序的一个显式中间表示这种中间表示可以看成是某种抽象的程序，通常是与平台无关的其重要性质：1.易于产生

2.易于翻译成目标程序下面是用三地址码（四元式）表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)25编辑ppt

id1:=id2+id3*60(1) (inttoreal, 60, ,t1 )(2) (* , id3, t1, t2 )(3) (+ , id2, t2, t3 )(4) (:= , t3, ,id1 )编辑ppt代码优化阶段对代码进行变换以使得编译产生的目标代码更高效（执行速度更快）。对上面中间代码进行优化处理后，产生如下的代码：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp227编辑ppt如下程序

语法分析结果j=2*i+1;

if(j>=n)

j=2*i+3;

returna[j];

t1=2*i

t2=t1+1

j=t2

t3=j<n

ift3gotoL0

t4=2*i

t5=t4+3

j=t5

L0: t6=a[j]

returnt6编辑ppt

t1=2*i

t2=t1+1

j=t2

t3=j<n

ift3gotoL0

t4=2*i

t5=t4+3

j=t5

L0: t6=a[j]

returnt6 t1=2*i

j=t1+1

t3=j<n

ift3gotoL0

j=t1+3

L0: t6=a[j]

returnt6代码优化编辑ppt代码优化

id1:=id2+id3*60(1) (inttoreal 60 - t1 )(2) (* id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1 )

变换（1）(* id3 60.0 t1 )(2）（+ id2 t1 id1 )编辑ppt代码生成阶段生成目标机机器代码或汇编代码(* , id3 60.0 t1 )(+ , id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addf R2,R1movf R1,id131编辑pptExample:ainR0,iinR1,ninR2t1=2*i

j=t1+1

t3=j<n

ift3gotoL0

j=t1+3

L0: t6=a[j]

returnt6 sllR1,1,R1

addR1,1,J

cmpJ,R2

blt.LL3

addR1,3,J

.LL3:ld[R0+J],

Rt

retr代码生成编辑ppt记录源程序中使用的标识符收集每个标识符的各种属性信息普通变量：类型、作用域、分配存储信息函数或过程：参数个数、类型、传递方法

返回值类型符号表管理(登录，查找）1.3符号表编辑ppt符号表管理inta,b;floate,fcharch1,ch2;为什么要先说明?

定义了变量的类型，也就规定了变量在内存中的存放形式，在其上所能进行的运算解决符号地址到存贮地址上的映射34编辑ppt

编译器的一个基本功能是记录源程序中使用的标识符并将它们记载到符号表中。符号表是一个数据结构。每个标识符在符号表中都有一条记录名字记号类型种属……addrid1(25)id2(25)ba例：inta,b;int简变04

并收集与每个标识符相关的各种属性信息，int简变35编辑ppt在编译的各个阶段都会发现源程序中的错误，1.4错误检测与报告为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式进行错误处理。error36编辑ppt小结：编译器的各个阶段源程序词法分析器错误处理器符号管理表语法分析器语义分析器中间代码生成器代码优化器代码生成器37编辑ppt编译的前端和后端

前端包括词法分析、语法分析、语义分析，以及相关的错误处理和符号表的建立

前端依赖于源程序并在很大程度上独立于目标机器。38编辑ppt

后端主要包括代码优化、代码生成和相关错误处理。

后端依赖于目标机器。

后端处理对象是由前端产生的结果，即中间代码

前端生成与平台无关的字节码

后端是由与平台有关的解释器对所生成的字节码文件进行解释执行Java语言的编译采用的是前端后端方式。39编辑ppt编译程序的组织

编译程序的遍（Passes/Phases）

对一种代码形式从头到尾扫描一遍将一个代码空间变换到另一个代码空间

代码空间=代码+符号表+其他有用信息

编译程序的组织取决于各遍的组织

单遍编译程序，多遍编译程序多个遍之间有逻辑上的先后关系多个遍的实现可采用顺序结构或并发结构（后者不常用）编辑ppt编译程序的组织

例：一个以语法、语义分析程序为中心的单遍编译程序组织sourceprogramtargetprogram语法、语义分析程序词法分析程序代码生成程序编辑ppt编译程序的伙伴程序

解释程序（Interpreter）

不产生目标程序文件不区别翻译阶段和执行阶段翻译源程序的每条语句后直接执行

程序执行期间一直有解释程序守候常用于实现虚拟机

比较编译程序和解释程序源程序编译程序目标程序输入目标程序输出解释程序输出输入源程序编辑ppt