西北工业大学：《编译原理》课程教学资源（PPT课件）第1章 绪论（主讲：康慕宁）

编译原理讲义 西北工业大学 计算机学院 康慕宁

编译原理讲义 西北工业大学 计算机学院 康慕宁

第一章 绪论 程序设计语言分低级语言和高级语言两类 低级语言：机器语言、汇编语言及其它面向机器的程序设计语言；其特点对计算机 的依赖性强、直观性差、编写程序的工作量大，对程序设计人员要求较高。 高级语言：有几百种之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等， 高级语言在算法描述能力、编写和调试效率上均比低级语言优越。 但高级语言与机器之间有一“鸿沟”：机器不能理解高级语言！ 因此，要在计算机上实现高级语言，需使该语言能让计算机所理解。 方法：对程序进行翻译或进行解释。 翻译：在计算机中放置一能由计算机直接执行的翻译程序，它将某程序设计语言 (源语言)所编写的程序（源程序）作为加工对象，将其翻译成为与之等价的另 一种语言（目标语言）的程序（目标程序）。这样的程序被称为编译程序。 可见，计算机执行某高级语言程序，需经两个阶段，即编译阶段和运行阶段。 在执行时，一般应有一些辅助子程序配合。如：数据格式转换子程序、标准函数、 动态存储分配子程序等等，由它们构成的子程序库称为运行系统。 编译系统一编译程序+运行系统

第一章 绪论 程序设计语言分低级语言和高级语言两类 低级语言:机器语言、汇编语言及其它面向机器的程序设计语言；其特点对计算机 的依赖性强、直观性差、编写程序的工作量大，对程序设计人员要求较高。 高级语言：有几百种之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等， 高级语言在算法描述能力、编写和调试效率上均比低级语言优越。 但高级语言与机器之间有一“鸿沟”：机器不能理解高级语言！ 因此，要在计算机上实现高级语言，需使该语言能让计算机所理解。 方法：对程序进行翻译或进行解释。 翻译：在计算机中放置一能由计算机直接执行的翻译程序，它将某程序设计语言 （源语言）所编写的程序（源程序）作为加工对象，将其翻译成为与之等价的另 一种语言（目标语言）的程序（目标程序）。这样的程序被称为编译程序。 可见，计算机执行某高级语言程序，需经两个阶段，即编译阶段和运行阶段。 在执行时，一般应有一些辅助子程序配合。如：数据格式转换子程序、标准函数、 动态存储分配子程序等等，由它们构成的子程序库称为运行系统。 编译系统=编译程序+运行系统

计算机执行高级语言程序的步豫 源程序P 编译阶段 计算机A 编译程序 目标程序P 运行阶段 数据 计算机B 运行程序 运行结果S

计算机执行高级语言程序的步骤 源程序P 目标程序P’ 运行结果S 编译程序 数据 运行程序 计算机A 计算机B 编 译 阶 段 运 行 阶 段

编译程序与解释程序 口高级语言程序也可通过解释程序来执行 口解释程序：以源程序为输入，在执行过程中不再产生 目标程序，而是边解释边执行。 0 解释程序运行效率不高，但结构简单，适用于小型语 言。目前，纯粹的解释程序已不多见，通常是将编译 和解释作某种程度的结合。 偏禄程摩是现今任何计算机系统的最重要的系统程序 之一。 本课程的目的，在于向大家介绍设计和构造编译程序 的基本原理和基本方法，其中许多方法也适用于构造 解释程序或汇编程序

编译程序与解释程序 高级语言程序也可通过解释程序来执行 解释程序：以源程序为输入，在执行过程中不再产生 目标程序，而是边解释边执行。 解释程序运行效率不高，但结构简单，适用于小型语 言。目前，纯粹的解释程序已不多见，通常是将编译 和解释作某种程度的结合。 编译程序是现今任何计算机系统的最重要的系统程序 之一。 本课程的目的，在于向大家介绍设计和构造编译程序 的基本原理和基本方法，其中许多方法也适用于构造 解释程序或汇编程序

1.1编译过程概述 翻译外文书刊与编译工作比较 翻译外文书刊 编译源程序 阅读原文 输入并扫描源程序 分析 识别单词 词法分析 分析句子 语法分析 修辞加工 代码优化 综合 写出译文 目标代码生成

1.1编译过程概述 翻译外文书刊与编译工作比较 翻译外文书刊 编译源程序 分析 阅读原文 识别单词 分析句子 输入并扫描源程序 词法分析 语法分析 综合 修辞加工 写出译文 代码优化 目标代码生成

编译程序的构成 编译程序主要由八个部分构成： 1.淘法分析程序（扫描器scanner) 2.福法分杯程序（分析器parser) 3.语义分析程序 4.中向代弱生成程序 5.代码优化程序 6.目标代码生成程序 7.错误检查和处理程序 8.各种信息表格的管程程序

编译程序的构成 编译程序主要由八个部分构成： 1.词法分析程序（扫描器 scanner） 2.语法分析程序（分析器 parser） 3.语义分析程序 4.中间代码生成程序 5.代码优化程序 6.目标代码生成程序 7.错误检查和处理程序 8.各种信息表格的管理程序

1.2编禄程序的逻辑结构 信息表管理程序 语 中间代码 源程序 法分析程序 法分析程 义分析 码优化程 标代码生成 目标代码 会 成 错误检查和处理程序

1.2 编译程序的逻辑结构 词 法 分 析 程 序 语 法 分 析 程 序 语 义 分 析 程 序 中 间 代 码 生 成 代 码 优 化 程 序 目 标 代 码 生 成 信息表管理程序 错误检查和处理程序 源 程 序 目 标 代 码

个微型PASCAL语言的定义 为了便于说明，我们引入一个微 程序1-1一个PASCAL源程序source 型PASCAL语言(PASCAL/M) 的定义。它只有如下四种语句： PROGRAM source; 1) PROGRAM语句； [This little source program is used to 2) 说明语句； illustrate compiling procedure 3) BEGN-END语句； VAR x,y,z:integer; 4) 赋值语句； a:integer; BEGIN 每个PASCAL/M语句都以 This program has only 4 statement PROGRAM语句开头，后跟说明 X:=23+5; 语句，再跟以一个BEGN-END z:=x DIV -3; 语句，在其内部可以有若干赋值 语句。 y:=z+18*3; a:=x+(y-2)DIV 4; 右边是一个该语言程序的例子。 END

一个微型PASCAL语言的定义 为了便于说明，我们引入一个微 型PASCAL语言（PASCAL/M） 的定义。它只有如下四种语句： 1）PROGRAM语句； 2）说明语句； 3）BEGIN-END语句； 4）赋值语句； 每个PASCAL/M语句都以 PROGRAM语句开头，后跟说明 语句，再跟以一个BEGIN-END 语句，在其内部可以有若干赋值 语句。 右边是一个该语言程序的例子。 程序1-1 一个PASCAL源程序source PROGRAM source; {This little source program is used to illustrate compiling procedure } VAR x,y,z:integer; a:integer; BEGIN { This program has only 4 statement } x:=23+5; z:=x DIV -3; y:=z+18*3; a:=x+(y-2) DIV 4; END

1.2.1词法分析程序（扫描器) 词法分析程序的任务是： 3) 下一个单词的首字符： 识别出源程序的各个基本语法单位 4)正识别的单词中的一个字符： (单词或语法符号) 5)不合法的字符。 2)删除无用的空白字符及其它与输入介 扫描器输出以单词为单位的单词流 质相关的非实质性字符（空格、回车 等) 例如，以特殊符号“#”分隔的单词流： 3)删除注释 #PROGRAM#source#;#VAR# 4)进行词法检查，报告所发现的错误 x#,#y#,##integer ;a 扫描器依次查看缓冲区中源程序的各 #:integer#BEGIN#x#:=# 字符，根据当前正查看的字符之种类， 23#+#5#;#Z#=#X#DV#。 并参考扫描过程中已得到的信息，就 #3#;#y#:=#Z#+#18#*#3 能判断出该字符在源程序中所处地位。 #;#a#=#X#+#(#y#-#2#)） 般它是下述几种情况之一： #DV#4#;#END#.# 正处理的注释中的一个字符； 2) 无用字符：

1.2.1 词法分析程序（扫描器） 词法分析程序的任务是： 1）识别出源程序的各个基本语法单位 （单词或语法符号） 2）删除无用的空白字符及其它与输入介 质相关的非实质性字符（空格、回车 等） 3）删除注释 4）进行词法检查，报告所发现的错误 扫描器依次查看缓冲区中源程序的各 字符，根据当前正查看的字符之种类， 并参考扫描过程中已得到的信息，就 能判断出该字符在源程序中所处地位。 一般它是下述几种情况之一： 1）正处理的注释中的一个字符； 2）无用字符； 3）下一个单词的首字符； 4）正识别的单词中的一个字符； 5）不合法的字符。 扫描器输出以单词为单位的单词流 例如，以特殊符号“#”分隔的单词流： # PROGRAM # source # ; # VAR # x # , # y # , # z # : # integer # ; # a # : # integer # ; # BEGIN # x # := # 23 # + # 5 # ; # z # := # x # DIV # - # 3 # ; # y # := # z # + # 18 # * # 3 # ; # a # := # x # + # ( # y # - # 2 # ) # DIV # 4 # ; # END # . #

单词流的内部表示 注意，前面的单词流形式只是我们为说明原理便于阅读而假定的 形式。 为了让计算机能够方便地识别和使用，在实际中的常用方法是将 单词计算机内部表示为一个有序对(Class,Value)。 C1ass为一整型数，用于标识该单词的类别； Value)用于存放单词的值。 例如对于source程序，可将其单词分为四类：(1)保留字(2) 专用符号(3)标识符(4)整数。这样，source程序相应的单词 流为： (1,PAROGRAM)(3,'source')(2,';)(1,VAR)()..(2,';) (1,'END)(2,‘.)

单词流的内部表示 注意，前面的单词流形式只是我们为说明原理便于阅读而假定的 形式。 为了让计算机能够方便地识别和使用，在实际中的常用方法是将 单词计算机内部表示为一个有序对(Class,Value)。 Class为一整型数，用于标识该单词的类别； Value用于存放单词的值。 例如对于source程序，可将其单词分为四类：（1）保留字（2） 专用符号（3）标识符（4）整数。这样，source程序相应的单词 流为： (1,‘PAROGRAM’) (3,’source’) (2,’;’) (1,’VAR’) (...) … … (2,’;’) (1,’END’) (2, ‘.’)