第 1 讲 绪论

1、1编译原理：编译原理指的是编译程序的构造原理和技术。 第一讲 绪 论2第一节 什么叫编译程序 一、程序设计语言1.计算机语言的分类计算机语言低级语言高级语言：如PASCAL，C等 机器语言汇编语言唯一能被计算机执行的3(1)把高级语言程序或汇编语言程序转换成计算机所能理解的语言程序机器语言程序 。 转换的办法：转换的办法：翻译或解释。(2)运行所得的机器语言程序得到计算结果 。2.执行高级语言或汇编语言的步骤：41.1. 翻译程序翻译程序 能够把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序),而后者与前者在逻辑上是等价的。 二、翻译程序5(1)(1)定义定义 源语言程

2、序是诸如PASCAL、C这样的高级语言，而目标语言是诸如汇编语言或机器语言之类的低级语言，这样的一个翻译程序称为编译程序。 汇编程序汇编程序是用于特定计算机上的汇编语言的翻译程序。2.编译程序6 交叉编译程序交叉编译程序: 源程序的编译和目标程序的执行不一定在 同一种计算机上完成。当源程序由另一种计算 机的编译程序进行编译时,我们将此编译程序称 为交叉编译程序。 诊断编译程序诊断编译程序: 专门用于帮助程序开发和调试程序的编译 程序。 优化编译程序优化编译程序: 着重于提高目标代码效率的编译程序。(2)(2)分类分类7源程序P计算机A目标程序P计算机B运行结果S编译程序C运行程序原始数据D编译

3、阶段运行阶段计算机按编译方式执行高级语言程序的步骤8定义定义: : 一个源程序的解释程序是这样一个程序,它以该语言写的源程序作为输入,但不产生目标程序,而是边解释边执行源程序本身。 与编译程序的主要区别: 不产生目标程序不产生目标程序三、解释程序源程序运行结果解释程序边翻译边执行9第二节 编译过程概述一、编译程序的组成例：一段英文翻译为中文时，通常经过以下步骤： 识别句子中的一个个单词； 词法分析 分析句子的语法结构； 语法分析 分析句子的含义； 语义分析 进行初步翻译； 中间代码生成 对译文进行修饰； 中间代码优化 写出最后的译文。 目标代码生成10第三节 编译程序的逻辑结构词法分析程序语法

4、分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查程序源程序源程序 单词符号单词符号中间代码中间代码中间代码中间代码中间代码中间代码语法单位语法单位目标代码目标代码111.1. 任务任务: :2.2. 1) 输入源程序,对构成源程序的字符串(从左到右从左到右)进行扫描和分解,识别出一个个的基本语法单位(也称为单词符号或语法符号)。2) 删除无用的空白字符、回车符以及其它与输入介质相关的非实质性字符。3) 删除注释。4) 进行词法检查,报告所发现的错误。一、词法分析程序(扫描器)12例: For i:=1 To 100 DoFor i:=1 To 100 Do 保留字

5、: ForFor 标识符: i i 赋值符: := := 整常数: 1 1 保留字: ToTo 整常数: 100100 保留字: DoDo 132.单词符号的表示与分类 (1)表示:二元组（ClassClass，ValueValue） 单词的类别 单词的值 (2)分类 关键字(保留字)、标识符、数字 、运算符、界符3.词法分析阶段的工作中依循的是语言的词法规则(即构词规则)。描述词法规则的有效工具是正规式和有限自动机。它是一种线性分析。 14二、语法分析程序1. 任务： 在词法分析的基础上，根据语言的语法规则，把单词符号重构成各类语法范畴(语法单位)。 如“语句”、“程序段”和“程序”等。 例

6、：Z:=X+0.6*Y 语法分析的任务是识别X+0.6*Y为算术表达式，同时，识别上述整个符号串属于赋值表达式。 15例：sum:=first+count*10 ;规则： := “:=” := “+” := “*” := “(”“)” := := := 16赋值语句标识符 := 表达式 表达式 + 表达式表达式 * 表达式标识符id2(first)标识符id3(count)整数(10)id1(sum)sum:=first+count*10 ;172. 分析方法： 完成这种分析,一般的途径是由语法分析程序试着为其构造一棵完整的语法树。描述手段： 在语法分析阶段的工作中依循的是语言的语法规则。描述

7、语法规则的有效工具是上下文无关文法上下文无关文法。它是一种层次结构分析。语法分析三个部分：语法规则、语法分析程序（语法分析三个部分：语法规则、语法分析程序（ 重构算法）重构算法）和语法树。和语法树。18三、语义分析程序1.任务 对语法分析程序所识别出的各类语法成分，分析其含义，以保证源程序在语义上的正确性。 2.语义的分类 语义静态语义：指在编译阶段能检查出的语义。 动态语义：则指只有在目标码的运行阶段 才能检查出的语义。 典型静态语义包括声明和类型检查。 193.分析方法 这一阶段依循的是语言的语义规则。通常使用语法制导翻译描述语义规则。 20四、中间代码生成1.任务 按语言的语义规则把各类

8、语法范畴翻译成中间语言代码。 2.中间代码的定义 所谓“中间代码”是一种含义明确、便于处理的记号系统,是位于源代码和目标代码之间的代码形式,它独立于具体的硬件。这种记号系统比较容易变换成现代计算机的机器指令。简单的说,中间代码是一种独立于具体硬件的记号系统。 213.3.中间代码的形式中间代码的形式 四元式,三元式,间接三元式,逆波兰式等。 例如，四元式的格式为: (算符,左操作数,右操作数,结果)例：Z:=（X+0.8)*Y/W序号 算符 左操作数 右操作数 结果（1） + X 0.8 T1（2） * T1 Y T2（3） / T2 W Z T1和T2是编译期间引进的临时工作变量 22五、代

9、码优化程序1. 任 务 对前段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和空间)的目标代码。2. 分 类 优化分为局部优化和全局优化。3. 优化所遵循的原则 程序的等价变换规则的原则。 234.例1： aindex:=4+2 中间代码：t=4+2 aindex=t（其中t是一个临时变量）优化: t=6 aindex=t优化: aindex=6 24例2： for k:=1 to 100 do begin m:=i+10*k; n:=j+10*k end序号 算符 左操作数 右操作数 结果注 解(1) :=1 k(2) j 100 k (9) 若100K转至第(9)四元式(

10、3)* 10 kT1 T1:=10*k;T1为临时变量(4)+ i T1 m m:=i+T1(5)*10kT2 T2:=10*k;T2为临时变量(6)+jT2n n:=j+T2(7)+k1k k:=k+1(8) j (2) 转到第(2)个四元式(9) 25序号 算符 左操作数 右操作数 结果注解(1):= i mm:=i(2):= j nn:=j(3):= 1 kk:=1(4)j 100 k (9) If(100k) GOTO(9)(5)+m 10 mm:=m+10(6)+n 10 mn:=n+10(7)+k 1 kk:=k+1(8) j (4)GOTO(4)(9) for k:=1 to 1

11、00 do begin m:=i+10*k; n:=j+10*k end26六、目标代码生成程序1.任务 把中间代码（或经过优化处理之后）变换成特定机器上的低级语言代码(汇编语言或机器语言)。 说明:它依赖于具体的计算机的硬件系统结构和指令系统。 2.要求 对于所用的翻译策略或算法要做到: 一是使所生成的目标代码尽可能短； 二是充分利用计算机可用资源的效率。 27绝对地址的机器指令代码 这种代码可以立即执行。汇编语言形式的目标程序 这种代码还需要汇编程序汇编之后才能运行。模块结构的机器指令(可重定位的指令代码) 这种代码在运行前必须借助于一个连接装配程序把各个目标模块连接在一起，装入内存中，使

12、之成为一个可以运行的绝对地址的机器指令代码程序。3.目标代码的形式28错误的种类：语法错误 语法错误是指源程序中有不符合语法(或词法)规则的错误,它们可在词法分析或语法分析时检测出来。 语义错误 语义错误是指源程序中不符合语义规则的错误,这些错误一般在语义分析时检测出来,有的要在运行时才能检测出来。 七、错误检查和处理程序29 1. 最重要的是符号表 2. 信息表的结构八、信息表管理程序名 字信息30第四节 编译程序的组织一、遍 1.定义 是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间代码或目标程序。 31源程序词法分析程序语法分析程序语义分析及代码生成程序目标

13、程序取单词语法单位2.一遍和多遍 (1)一遍 (2)多遍多遍编译程序少占内存，消耗较多时间32二、前端和后端前端后端源代码中间代码目标代码1.前端：主要与源程序有关但与目标机（运行编译程序的 计算机称宿主机，运行编译程序所产生目标代码 的计算机称目标机）无关。 2.后端：包括编译程序中与目标机有关的那些部分。3.优点：取编译程序的前端，改写其后端以生成不同目标 机上的相同语言的编译程序。 33第五节 编译程序的生成一、编译程序的设计目标 目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。34二、编译器的生成1.合理的方法是用另一种语言来编写编译器，而使用

14、该种语言的编译器早已存在了。用语言B编译语言A的编译器语言A正运行的编译器语言B已存在的编译器35(1) LEX: (1) LEX: 自动产生词法分析器自动产生词法分析器2.编译程序生成工具词法规则说明词法规则说明LEX词法分析程序词法分析程序(C /C/C+程序程序)输入：输入：词法（正规表达式）词法（正规表达式）识别动作（程序段）识别动作（程序段）输出：输出：yylexyylex( ) ( ) 函数函数输入串输入串词法分析程序词法分析程序单词单词符号串符号串36语法规则说明语法规则说明YACC语法分析程序语法分析程序(C /C/C+程序程序)输入：输入：语法规则（产生式）语法规则（产生式）语义动作语义动作( (/