编译原理1、本课程的地位：计算机专业的专业基础课是软件技术的基础必修的主干课研究生入学考试课作用编译原理是介绍如何将高级语言变换成计算机硬件所能识别的机器语言以便计算机能处理它的理论基础坚实，其形式化系统不仅应用于编译技术，还大量应用于人工智能，多媒体技术、数据库等；学习任务：1、掌握编译的理论基础和形式化系统2、了解编译的全过程及其具体实现学习方法认真听讲、认真理解书中的基本概念、基本原理与基本算法弄懂书中的例题与习题在看书时或理解例题时，一定要画出相应的细节过程，通过画图来加深理解再理解的基础上记忆理论结合实践成绩考核平时30%（点名10%，作业%20）期末考试70%第一章引论3、编译的转换过程两个阶段转换：编译------运行三个阶段的转换：编译→汇编→运行区别是产生的目标代码不一样，三个阶段产生的是汇编的代码解释：以源程序作为输入，不产生目标代码，一边解释一边执行优点：直观易懂，结构简单，易于实现人机对话缺点：效率低1.2编译程序的概述1、编译程序的工作自然语言的翻译识别单词分析句子的语法结构根据句子的含义进行初步翻译对译文进行修饰写出最后的译文程序语言的翻译词法分析语法分析语义分析和中间代码的生成优化目标代码的生成中间代码的作用：？？词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词单词：高级语言中有实际意义的最小语法单位，它由字符构成。例：有一个ｃ语言程序，对它进行编译void_compute(){inty,c,d;floatx,a,b;x=a+b*10;y=c+)d*(x+b;}基本字：标识符：整常数：运算符：界限符：词法分析依照词法规则识别出正确的单词，转换成统一的规格，备用转换：对基本字、运算符、界限符的转换标识符的转换常数的转换转换完成后的格式（类号，内码）描述词法分析规则的有效工具：“正规式”和“有限自动机”语法分析任务：在词法分析的基础上，根据语言的语法规则，把单词符号组成各类的语法单位：短语、子句、语句、过程、程序等语法规则：又称文法，规定单词如何构成短语、语句、过程、程序语法规则的表示：BNF（巴斯克范式），A::=B|C，::=赋值为例：x=a+b*50赋值语句的语法规则A::=V=EE::=T|E+TT::=F|T*FF::=V|(E)|CV::=标识符C::=常数语法分析的方法推导(derive)和规约(reduce)推导：最左推导、最右推导推导的逆过程称为规约；最左规约与最右规约最左推导最右规约最右推导最左规约机器用语法树来做推导分析c语言语句y=c+)*(x+b的分析过程语法分析过程也可以用一棵倒置的树来表示，这棵树也叫做语法树eg：x=a+b*50的语法树再有y=c+)*(x+b语义分析与中间代码生成任务：对语法分析识别出的各类语法范畴，分析其含义，进行初步的翻译产生介于源代码和目标代码之间的一种代码分两个阶段工作：对每种语法范畴进行静态语义检查若语义正确，就进行中间代码的翻译中间代码的形式：四元式、三元式、逆波兰式例：将x=a+b*50变成中间代码用汇编语言来编写就很容易转成目标代码优化任务：对前面产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。原则：等价原则主要方面：公共子表达式的提取、合并已知量、删除无用语句、循环优化等公共子表达式例x=(a+b)*c+(a+b)*d合并已知量例…..c=a+b;{…….//没有改变a，b的值….}d=a+b;//合并已知a+bd在这里没有必要存在循环优化：改造成循环内都是必须的例将下面的语句转换成中间代码for(k=1;k<=100;k++){m=i+10*k;n=j+10*k;}中间代码执行过程：10ifk<=100then{m=i+10*k；n=j+10*k；k++；goto10}将i放在外面m=i；m=m+10；得到下面的中间代码中间代码k=1;m=I;n=j;10ifk<=100then相当于{m+=10；n+=10；k++；goto10}效率：200次加法第一个表中：200次加法200次乘法目标代码生成任务：把经过优化的中间代码转化成特定机器上的低级语言代码。目标代码的形成：绝对指令代码：可立即执行的目标代码汇编指令代码：汇编语言程序，需要通过汇编程序汇编之后才能运行。可重定位指令代码：先将各个目标模块连接起来，确定变量，常数等在主存中的位置，装入主存后才能成为可