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