《编译原理：第一章 引论》由会员分享，可在线阅读，更多相关《编译原理：第一章 引论（49页珍藏版）》请在金锄头文库上搜索。
1、编译原理,李宏芒 Email: ,本课程的地位,计算机专业的专业基础课. 软件技术的基础 计算机专业学生必修的一门主干课 研究生入学考试的课程之一,本课程的作用,编译原理介绍如何将高级程序设计语言变换成计算机硬件能识别的机器语言，以便计算机进行处理。 它的理论基础坚实，其形式化系统不仅应用于编译技术，而且大量应用于人工智能、多媒体技术及数据库等领域。,本课程的学习任务及考核,学习任务： 掌握编译的理论基础和形式化系统。 了解编译的全过程及具体实现方法。,考核： 平时：30% 笔试：70%,本课程的学习方法,认真听课，认真理解书中的基本概念、基本原理与基本算法，特别是算法的思想。 弄懂书中的例题
2、和习题。 在看书时或理解例题时，一定要画出相应的细节变化过程，通过画图和细节演算加深理解。 在理解的基础上记忆。 理论结合实践。,教材及参考书,教材： 程序设计与语言编译原理 （第三版），陈火旺主编，国防工业出版社。 参考书： 编译原理（第二版），张素琴、吕映芝、蒋维杜、戴桂兰，清华大学出版社。 编译原理及实践，（美）Kenneth C.Louden著，冯博琴，冯岚等译，机械工业出版社。 编译原理，（美）Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著，李建中 姜守旭译，机械工业出版社。 编译原理学习指导及习题解析，陈英 王贵珍主编， 清华大学出版社。,第一章
3、 引 论,编译理论与方法 计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家 程序设计语言、编译理论与方法约占1/3,本课程介绍程序设计语言编译程序构造的基本原理和基本实现技术.,1.1. 什么是编译程序,翻译程序把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序,1.1. 什么是编译程序,编译程序(compiler)把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。（如C语言、PASCAL语言等是编译程序） 诊断编译程序 优化编译程序 交叉编译程序 可变目标编译程序,1
4、.1. 什么是编译程序,解释程序把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。（如BASIC语言是解释程序）,国防科技大学计算机系602教研室,编译程序 vs. 解释程序,编译,解释,1.2. 编译过程,把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。,词法分析,语法分析,中间代码产生,优化,目标代码产生,编译程序的工作一般分为五个阶段: 词法分析 语法分析 中间代码产生 优化 目标代码产生,1.2. 编译过程,有一个C语言程序，对它进行编译 Void jisuan() int y,
5、c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b; ,举例说明,1. 词法分析,任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。 依循的原则：构词规则 描述工具：正规式和有限自动机 FOR I := 1 TO 100 DO保留字 标识符 等符 整常数 保留字 整常数 保留字,词法分析举例说明,基本字（保留字：组成命令的关键字，系统定义好的单词）：void，int，float 标识符 （用户定义的函数名、变量名等）：jisuan，a，b，c，d，x，y 整常数：50 运算符：*， +， = 界限符（分隔开两部分的符号）： ；，（ ）,词法分析
6、依照此法规则，识别正确的单词，并将其转换成统一规格（类号、内码），备用。 转换规则包括：对基本字、运算符、界限符的转换规则（有限的、可数的），对标识符的转换规则，对常数的转换规则等。,一个C语言程序，对它进行词法分析 Void jisuan() int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b; ,2. 语法分析,任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 描述工具：上下文无关文法 Z := X + 0.618 * Y 算术表达式，赋值语句,语法分析举例说明,赋值语句的语法规则： A V=E E T|E
7、+T T F|T*F F V|(E)|C V 标识符 C 常数,C语言程序 Void jisuan() int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b; 现在我们对x=a+b*50; 进行语法分析。,语法分析的方法为：推导（derive）和归约（reduce），推导是指从开始符号开始推出句子，包括最左推导、最右推导，归约是推导的逆过程。最左推导对应最右归约；最右推导对应最左归约,最右推导：将最右边的大写字母替换（大写字母代表非终结符）。,A V=EV=E+TV=E+T*FV=E+T*C V=E+T*50 V=E+F*50V=E+V*50 V=E+b*50
8、V=T+b*50 V=F+b*50 V=V+b*50 V=a+b*50 x=a+b*50,语法分析举例说明（续）,最左推导：,A V=E x=E x=E+Tx=T+T x=F+Tx=V+T x=a+Tx=a+T*F x=a+F*F x=a+V*F x=a+b*F x=a+b*C x=a+b*50,错误分析：使用最右推导分析语句 y=c+)d*(x+b,A V=EV=E+TV=E+FV=E+V V=E+b V=T+bV=T*F+b V=T*V+b V=T*x+b,赋值语句的语法规则： A V=E E T|E+T T F|T*F F V|(E)|C V 标识符 C 常数,无法推导出上述语句，故该语
9、句的语法是错误的。,3. 中间代码产生,任务:对各类不同语法范畴（语句、过程、表达式、函数等）按语言的语义进行初步翻译。 依循的原则：语义规则 中间代码:三元式，四元式，逆波兰式、树形结构等 Z:=X + 0.618 * Y 翻译成四元式为(1) * 0.618 Y T1(2) + X T1 T2(3) := T2 _ Z,4. 优化,任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。主要包括：公共子表达式提取、合并已知量、删除无用语句、循环优化等。 依循的原则：程序的等价变换规则,FOR K:=1 TO 100 DOBEGIN X:=I+1;M := I + 1
10、0 * K;N := J + 10 * K;END,可以改写为（C语言）：K=1；10 if (k=100)then X=I+1;M= I + 10 * K;N= J + 10 * K;K+;GOTO 10;,中间代码（一）,序号 OPR OPN1 OPN2 RESULT 注释 (1) := 1 K K:=1 (2) j 100 K (10) if (100K)goto (10) (3) + I 1 X X:=I+1 (4) * 10 K T1 T1:=10*K (5) + I T1 M M:=I+T1 (6) * 10 K T2 T2:=10*K (7) + J T2 N N:=J+T2 (
11、8) + K 1 K K:=K+1 (9) j (2) goto (2) (10),400次加法 200次乘法,转换后的等价代码（二）,序号 OPR OPN1 OPN2 RESULT 注释 (1) + I 1 X X:=I+1 (2) := I M M:=I (3) := J N N:=J (4) := 1 K K:=1 (5) j 100 K (10) if (100K) goto (10) (6) + M 10 M M:=M+10 (7) + N 10 N N:=N+10 (8) + K 1 K K:=K+1 (9) j (5) goto (5) (10),301次加法,5. 目标代码产生
12、,任务: 把中间代码变换成特定机器上的目标代码。 依赖于硬件系统结构和机器指令的含义 目标代码三种形式: 绝对指令代码: 可直接运行 可重新定位指令代码: 需要连接装配 汇编指令代码: 需要进行汇编,例: b=a+2MOV a, R1 ADD #2, R1 MOV R1, b0001 01 00 00000000 * 0011 01 10 00000010 0100 01 00 00000100 *L=000011110001 01 00 00001111 0011 01 10 00000010 0100 01 00 00010011,1.3. 编译程序结构,1、编译程序总框,词法分析器,语法
13、分析器,语义分析与中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,2. 表格和表格管理,常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。 格式:,名字,信息,例: PASCAL程序段：,PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,PROCE
14、DURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,注：词法分析时，先建好标号表，等到中间代
15、码生成时，再将相关信息填入。（维护管理）,PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VARK:INTEGER; BEGIN START:K:=M+1;M:=N+4;N:=K; END.,3. 出错处理,出错处理程序：发现源程序中的错误，把有关错误信息报告给用户 语法错误 语义错误,注：编译程序一般很难检测出逻辑错误!,4. 遍(pass),所谓“遍“， 就是对源程序或源程序的中间表示从头到尾扫描一次。 阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。,5. 编译前端与后端,编译前端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化 编译后端：与目标机有关，与目标机有关的优化，目标代码产生 优点：减少对内存容量的要求，程序逻辑结构清晰; 优化更充分，有利于移植。 不足: 编译程序运行的效率低,
