编译原理第1章概论

编译原理任课教师：邵翀E_mail：教学计划时间：2017~2018第学1期周学时：2周数：18（上机9课时）考核方式：考试教材：吕映之,《编译原理》,清华大学参考书：《程序设计语言编译原理》本课程前后继课程高级程序设计语言汇编程序设计语言数据结构离散数学编译原理形式语言与自动机可计算性理论并行编译自然语言理解课程简介《编译原理》是计算机类专业的一门主干专业课程。设置本课程的目的是系统向学生讲述编译程序一般构造原理、基本设计方法和实现技术，学生通过本课程的学习，既掌握编译理论和方法方面的基本知识，而且也具备设计、实现、分析和移植编译程序的初步能力。特点：抽象;算法多难点：形式语言基本理论；自动机基本理论；语义分析；第一章概述编译程序是计算机系统中重要的系统软件，是高级语言的支撑基础。学习目标：编译程序的概念编译的各个阶段编译程序的结构编译程序生成方法编译原理是编译程序的构造原理和技术。1.1

翻译程序与编译程序一、程序设计语言1.计算机语言的分类计算机语言低级语言高级语言：如PASCAL，C等机器语言汇编语言(1)把高级语言程序或汇编语言程序转换成计算机所能理解的语言程序—机器语言程序。

完成转换的程序叫翻译程序。(2)运行所得的机器语言程序得到计算结果。2.高级语言或汇编语言的执行步骤：1.1翻译程序与编译程序1.翻译程序是这样一种程序,它能够把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序),而后者与前者在逻辑上是等价的。二、翻译程序源程序翻译程序目标程序1.1翻译程序与编译程序2.翻译程序通常有两种方式：编译和解释三.编译方式和编译程序1.1翻译程序与编译程序1.编译方式

编译方式是一种分阶段进行的方式。一般来说，首先进行“翻译”，把用高级语言或汇编语言程序翻译成与之等价的机器语言程序，然后对翻译出来的程序进行运行计算。前一阶段翻译工作由翻译程序完成，后一阶段的运行计算需要由运行程序来配合完成。所谓运行程序是指运行目标程序时必须配置的各种子程序全体，通常以库子程序的形式存在，如连接装配程序及连接库等。1.1翻译程序与编译程序2.编译程序（1）将用高级语言（如FORTRAN,PASCAL或C）书写的程序翻译成等价的某特定计算机系统的低级语言程序（汇编语言或机器语言），这种翻译程序称为编译程序。高级语言程序编译程序低级语言程序（2）如果将汇编语言书写的程序翻译成某特定计算机系统的机器语言程序，这种翻译程序称为汇编程序。1.解释方式在解释方式下，源程序的执行只有一个阶段——解释执行阶段。具体地说，完成解释工作的解释程序将按源程序中语句的动态顺序逐句地进行分析解释，并立即予以执行。与编译方式的主要区别:不产生目标程序。而是直接执行源程序本身。四、解释方式及解释程序1.1翻译程序与编译程序2解释程序是这样一个程序,它以某一语言写的源程序作为输入,但不产生目标程序,而是边解释边执行源程序本身。源程序运行结果解释程序边翻译边执行1.1翻译程序与编译程序编译程序vs.解释程序编译解释编译过程是一种语言的翻译过程，类似于外文的翻译过程。例如：一段英文翻译为中文时，通常经过以下步骤：

识别句子中的一个个单词；分析句子的语法结构；分析句子的含义；进行初步翻译；对译文进行修饰；写出最后的译文。词法分析语法分析语义分析中间代码生成中间代码优化目标代码生成1.2编译程序组成及逻辑结构1.2编译程序组成及逻辑结构编译程序的一般需完成五个方面任务:词法分析词法分析程序语法分析语法分析程序语义及中间代码产生语义分析（和中间代码生成）程序中间代码优化中间代码优化程序目标代码产生目标代码生成程序一、编译程序组成1、词法分析（1）任务:输入源程序,对构成源程序的字符串(从左到右)进行扫描和分解,根据语言的词法规则识别出一个个的最小语法单位(也称为单词符号或语法符号)。删除无用的空白字符及其他与输入介质相关的非实质性字符（空格、回车等）删除注释。进行词法检查,报告所发现的错误。1.2编译程序组成及逻辑结构例：计算圆柱体表面积

floatr,h,s;S=2*3.1416*r*(h+r);保留字:float标识符:r,h,s运算符:*，+常数：2,3,1416界符:();,=1.2编译程序组成及逻辑结构2、语法分析任务：在词法分析的基础上，根据语言的语法规则，把单词符号重构成各类语法范畴(语法单位)。分析时如发现有不符合语法规则的地方，语法分析程序便把这些出错的地方及出错性质打印输出；如无语法错误，则以另一种内部表示给出正确的语法结构。如“表达式”、“语句”、“程序段”和“程序”等2*3.1416*r*(h+r)S=2*3.1416*r*(h+r);1.2编译程序组成及逻辑结构3、语义分析（1）任务依据语言的语义规则对语法分析程序所识别出的各类语法成分进行静态语义检查，以保证源程序在语义上的正确性，并用另一种语言形式表示出来，或直接用目标语言表示出来。（2）语义的分类

静态语义：指在编译阶段能检查出的语义。如确定类型、类型和运算符合法性检查、识别语法成分含义与相应的语义处理、及其他一些静态语义检查。动态语义：则指只有在目标码的运行阶段才能检查出的语义。1.2编译程序组成及逻辑结构4、中间代码生成（1）任务：按语言的语义规则把各类语法范畴翻译成中间语言代码。（2）中间代码的定义：所谓“中间代码”是一种含义明确、便于处理的记号系统,是位于源代码和目标代码之间的代码形式,它独立于具体的硬件。这种记号系统比较容易变换成现代计算机的机器指令。（3）中间代码的形式四元式,三元式,间接三元式,逆波兰式等。1.2编译程序组成及逻辑结构例：四元式的格式为:(算符,左操作数,右操作数,结果)（1）（*，2，3.1416，T1）（2）（*，T1，r，T2）（3）（+，h，r，T3）（4）（*，T2，T3，T4）（5）（=，T4，-，S）T1、T2、T3、T4是编译期间引进的临时工作变量赋值语句：S=2*3.1416*r*(h+r);语义分析时，首先检查赋值号左右两边表达式的类型是否匹配,然后再根据赋值语句的语义对它进行翻译。语义：2*3.1416

T1语义：T1*r

T2语义：h+r

T3语义：T2*T3

T4语义：T4

S1.2编译程序组成及逻辑结构5、代码优化(1)任务:对前段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和空间)目标代码。(2)分类：优化分为局部优化和全局优化。(3)优化所遵循的原则：程序的等价变换规则的原则。（1）（*，2，3.1416，T1）（2）（*，T1，r，T2）（3）（+，h，r，T3）（4）（*，T2，T3，T4）（5）（=，T4，_，S）（*，6.28，r，T2）1.2编译程序组成及逻辑结构6、目标代码生成(1)任务：把中间代码（或经过优化处理之后）变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。例如:(*,count,10.0,T1) (+,first,T1,sum)

生成汇编代码如下: MOVFcount,R2 MULF#10.0,R2 MOVFfirst,R1 ADDFR1,R2 MOVR1,sum1.2编译程序组成及逻辑结构绝对地址的机器指令代码：这种代码可以立即执行。汇编语言形式的目标程序：这种代码还需要汇编程序汇编之后才能运行。模块结构的机器指令(可重定位的指令代码)

这种代码在运行前必须借助于一个连接装配程序把各个目标模块连接在一起，装入内存中，使之成为一个可以运行的绝对地址的机器指令代码程序。(2)目标代码的形式1.2编译程序组成及逻辑结构1.所谓趟或遍是指一个编译程序在编译时刻把源程序或源程序的等价物(中间程序)从头到尾扫描一遍并完成规定加工处理工作的过程。2.根据编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以把编译程序分为单遍扫描的编译程序(只需扫描一遍)和多遍扫描的编译程序(需扫描多遍)。1.2编译程序组成及逻辑结构二、编译程序逻辑结构词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查程序源程序

单词符号中间代码中间代码中间代码语法单位目标代码3.典型的编译程序结构1.2编译程序组成及逻辑结构出错处理：编译过程中，发现源程序有错误（词法错误、语法错误、语义错误），编译程序应报告错误的性质和出错的地点，并将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分继续被编译下去。这些工作称为出错处理(errorhandling)。表格管理：编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作涉及到构造、查找或更新有关的表格，因此需要有表格管理工作。1.2编译程序组成及逻辑结构1.3编译程序的生成方法1.源语言和目标语言2.编译方法3.选择语言编制程序4.调试编译程序5.提交相关文档一、构造一个编译程序必须掌握的内容1.合理的方法是用另一种已存在编译器的语言来编写编译器。用语言B编译语言A的编译器语言A正运行的编译器语言B已存在的编译器2.编译程序生成工具二、编译程序生成方法1.3编译程序的生成方法(1)LEX:自动产生词法分析器词法规则说明LEX词法分析程序(C/C++程序)输入：词法（正规表达式）识别动作（Ｃ/C++程序段）输出：

yylex()函数1.3编译程序的生成方法语法规则说明YACC语法分析程序

输入： 语法规则（产生式） 语义动作(Ｃ/C++程序段)输出：

yyparse()函数(2)YACC:自动产生语法分析器1.3编译程序