软考(程序语言基础知识)

1、第6章 程序语言基础知识第6章 程序语言基础知识o6.1 程序语言基础知识程序语言基础知识n6.1.1 程序语言的基本概念程序语言的基本概念n6.1.2 程序设计语言的分类和特点程序设计语言的分类和特点n6.1.3 程序语言的基本成分程序语言的基本成分o6.2 语言处理程序基础语言处理程序基础n6.2.1 汇编程序基本原理汇编程序基本原理n6.2.2 编译程序基本原理编译程序基本原理n6.2.3 解释程序基本原理解释程序基本原理低级语言和高级语言o低级语言低级语言n机器语言机器语言o使用使用0、1序列序列o效率低，可读性差，难以理解效率低，可读性差，难以理解n汇编语言汇编语言o使用容易记忆的符

2、号使用容易记忆的符号o可读性有所提高，但书写格式在很大程度上取决可读性有所提高，但书写格式在很大程度上取决于特定计算机于特定计算机面向机器面向机器6.1.1 程序语言的基本概念o高级语言高级语言n使用与自然语言比较接近的程序语言使用与自然语言比较接近的程序语言n功能更强，抽象级别更高，大大提高了程序设功能更强，抽象级别更高，大大提高了程序设计的效率计的效率面向应用面向应用6.1.1 程序语言的基本概念低级语言和高级语言编译程序和解释程序o语言处理程序的分类语言处理程序的分类n汇编程序汇编程序o将用汇编语言编写源程序翻译成目标程序后，再将用汇编语言编写源程序翻译成目标程序后，再执行执行n解释程序

3、解释程序o直接执行源程序，或者将源程序翻译成某种中间直接执行源程序，或者将源程序翻译成某种中间表示形式后再加以执行表示形式后再加以执行n编译程序编译程序o先将源程序翻译成目标语言程序，然后在计算机先将源程序翻译成目标语言程序，然后在计算机上运行目标程序上运行目标程序6.1.1 程序语言的基本概念编译程序和解释程序o解释程序和编译程序的根本区别解释程序和编译程序的根本区别n在编译方式下，机器上运行的是与源程序等价在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目的目标程序，源程序和编译程序都不再参与目标程序的执行过程；标程序的执行过程；n在解释方式下，解释程序和源程

4、序要参与到程在解释方式下，解释程序和源程序要参与到程序的运行过程中，运行程序的控制权在解释程序的运行过程中，运行程序的控制权在解释程序。序。n解释器翻译源程序时不产生独立的目标程序，解释器翻译源程序时不产生独立的目标程序，而编译器则需将源程序翻译成独立的目标程序。而编译器则需将源程序翻译成独立的目标程序。6.1.1 程序语言的基本概念程序设计语言的定义o语法语法n由程序语言基本符号组成程序中的各个语法成由程序语言基本符号组成程序中的各个语法成分（包括程序）的一组规则。分（包括程序）的一组规则。n包括词法规则和语法规则包括词法规则和语法规则n语法可以通过形式语言进行描述语法可以通过形式语言进行描

5、述o语义语义n程序语言中按语法规则构成的各个语法成分的程序语言中按语法规则构成的各个语法成分的含义含义n分为静态语义和动态语义分为静态语义和动态语义6.1.1 程序语言的基本概念程序设计语言的定义o语用语用n表示了构成语言的各个记号和使用者的关系，表示了构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。涉及符号的来源、使用和影响。o语境语境n理解和实现程序设计语言的环境理解和实现程序设计语言的环境n包括编译环境和运行环境包括编译环境和运行环境6.1.1 程序语言的基本概念程序语言发展概述 程序设计语言的发展是一个不断演化的过程，程序设计语言的发展是一个不断演化的过程，其根本的推动力

6、就是抽象机制更高的要求，以及其根本的推动力就是抽象机制更高的要求，以及对程序设计思想更好的支持。具体的说，就是把对程序设计思想更好的支持。具体的说，就是把机器能够理解的语言提升到也能够很好地模仿人机器能够理解的语言提升到也能够很好地模仿人类思考问题的形式。类思考问题的形式。 目前，程序设计语言及编程环境正在向面向目前，程序设计语言及编程环境正在向面向对象及可视化编程环境方向发展。对象及可视化编程环境方向发展。6.1.2 程序设计语言的分类和特点程序设计范型o根据程序设计的方法，可分为根据程序设计的方法，可分为n命令式程序设计语言命令式程序设计语言n面向对象的程序设计语言面向对象的程序设计语言n

7、函数式程序设计语言函数式程序设计语言n逻辑型程序设计语言逻辑型程序设计语言6.1.2 程序设计语言的分类和特点命令式程序设计语言o命令式语言是命令式语言是基于动作基于动作的语言。的语言。o用命令式程序设计语言编写程序，就是描述解题过用命令式程序设计语言编写程序，就是描述解题过程中每一步的过程，程序的运行过程就是问题的求程中每一步的过程，程序的运行过程就是问题的求解过程，因此也称为解过程，因此也称为过程式语言过程式语言。o结构化程序设计语言的特点结构化程序设计语言的特点n用自顶向下、逐步求精的方法编程用自顶向下、逐步求精的方法编程n按模块组装的方法编程按模块组装的方法编程n程序只包含顺序、判定及

8、重复构造，而且每种构造程序只包含顺序、判定及重复构造，而且每种构造只允许单入口和单出口只允许单入口和单出口o代表语言：代表语言：C、Pascal等等6.1.2 程序设计语言的分类和特点面向对象的程序设计语言o包含几个主要概念包含几个主要概念n对象：人们要进行研究的任何事物，具有状态对象：人们要进行研究的任何事物，具有状态和操作。和操作。n类：面向对象语言必须提供的由用户定义的数类：面向对象语言必须提供的由用户定义的数据类型，它将具有相同状态、操作和访问机制据类型，它将具有相同状态、操作和访问机制的多个对象抽象成一个对象类。的多个对象抽象成一个对象类。n继承：实现了一般与特殊的关系，达到概念复继

9、承：实现了一般与特殊的关系，达到概念复用和代码复用的目的。用和代码复用的目的。o代表语言：代表语言：C+、Java等等6.1.2 程序设计语言的分类和特点函数式程序设计语言o函数式语言是一类以函数式语言是一类以-演算演算为基础的语言。为基础的语言。o函数是一种对应规则（映射），它使定义域中函数是一种对应规则（映射），它使定义域中每个元素和值域中唯一的元素相对应。每个元素和值域中唯一的元素相对应。o代表语言：代表语言：LISPLISP6.1.2 程序设计语言的分类和特点逻辑型程序设计语言o逻辑型语言是一类以逻辑型语言是一类以形式逻辑形式逻辑为基础的语言。为基础的语言。o适用于书写自动定理证明、专

10、家系统和自然语适用于书写自动定理证明、专家系统和自然语言理解等问题的程序。言理解等问题的程序。o代表语言：代表语言：PROLOG6.1.2 程序设计语言的分类和特点练习（2008年上）o计算机程序计算机程序 = 算法算法 + 数据结构数据结构 + 程序设计方法程序设计方法 + 语语言工具和环境，其中关于程序设计的叙述，正确的是言工具和环境，其中关于程序设计的叙述，正确的是 （30） 。A、程序设计语言与程序设计方法是一一对应的关系、程序设计语言与程序设计方法是一一对应的关系B、面向对象的程序设计语言只能支持面向对象的程序、面向对象的程序设计语言只能支持面向对象的程序设计方法设计方法C、面向对象

11、的程序设计技术与结构化程序设计技术是、面向对象的程序设计技术与结构化程序设计技术是相互排斥的相互排斥的D、过程式程序设计是一种传统的程序设计方法、过程式程序设计是一种传统的程序设计方法 练习（2008年上）o计算机能直接识别和执行机器语言程序，该语计算机能直接识别和执行机器语言程序，该语言的基本元素是言的基本元素是 （31） 。A、汇编代码、汇编代码 B、0和和1 C、扩展、扩展ASCII码码 D、BCD码码 练习（2008年下）o开发微型嵌入式应用系统，采用开发微型嵌入式应用系统，采用 （29） 更更合适。合适。A、C语言或汇编语言语言或汇编语言 B、HTML或或XML语言语言C、脚本语言脚

12、本语言 D、SQL语言语言 练习（2009年上）o （29） 属于标记语言。属于标记语言。A、PHP B、Lisp C、XML D、SQL 练习（2009年上）o以下关于脚本程序语言的叙述中，错误的是以下关于脚本程序语言的叙述中，错误的是 （35） 。A、脚本语言需要相应的引擎解释执行脚本语言需要相应的引擎解释执行B、脚本语言程序一般以文本方式存在脚本语言程序一般以文本方式存在C、在网页设计中应用脚本可以提高网页浏览在网页设计中应用脚本可以提高网页浏览速度、丰富网页的表现速度、丰富网页的表现D、脚本语言中不允许使用变量脚本语言中不允许使用变量 练习（2010年上）o通过程序设计活动求解问题时，

13、通常可以分为通过程序设计活动求解问题时，通常可以分为问题建模、算法设计、编写代码和编译调试四问题建模、算法设计、编写代码和编译调试四个阶段。个阶段。 （39） 阶段的工作与所选择的程阶段的工作与所选择的程序语言密切相关。序语言密切相关。A、问题建模和算法设计、问题建模和算法设计 B、算法设计和编写代码、算法设计和编写代码C、问题建模和编译调试、问题建模和编译调试 D、编写代码和编译调试、编写代码和编译调试 语言处理程序o主要作用主要作用n将高级语言或汇编语言编写的程序翻译成某种将高级语言或汇编语言编写的程序翻译成某种机器语言程序，使程序可在计算机上运行。机器语言程序，使程序可在计算机上运行。o

14、分类分类n汇编程序汇编程序n编译程序编译程序n解释程序解释程序6.2 语言处理程序基础汇编语言o汇编语言汇编语言是为特定计算机（或计算机系统）设是为特定计算机（或计算机系统）设计的计的面向机器面向机器的符号化程序设计语言。的符号化程序设计语言。o汇编语言源程序汇编语言源程序是用汇编语言编写的程序，需是用汇编语言编写的程序，需要使用专门的汇编程序进行翻译。要使用专门的汇编程序进行翻译。o语句的分类语句的分类n指令语句指令语句n伪指令语句伪指令语句n宏指令语句宏指令语句6.2.1 汇编程序基本原理汇编语言o指令语句（机器指令语句）指令语句（机器指令语句）n指令语句经过汇编产生的机器代码，能被指令语

15、句经过汇编产生的机器代码，能被CPU直接识别并执行相应的操作。直接识别并执行相应的操作。n基本指令如：基本指令如：ADD、SUB和和MOV等。等。n可分为：传送指令、算术运算指令、逻辑运算可分为：传送指令、算术运算指令、逻辑运算指令、移位指令、转移指令和处理机控制指令指令、移位指令、转移指令和处理机控制指令等类型。等类型。6.2.1 汇编程序基本原理汇编语言o伪指令语句伪指令语句n伪指令语句指示汇编程序在汇编源程序时完成伪指令语句指示汇编程序在汇编源程序时完成某些工作。某些工作。n伪指令语句与指令语句的区别伪指令语句与指令语句的区别o伪指令语句经汇编后不产生机器代码，而指令语伪指令语句经汇编后

16、不产生机器代码，而指令语句经汇编后产生相应的机器代码；句经汇编后产生相应的机器代码；o伪指令语句所指示的操作是在源程序被汇编时完伪指令语句所指示的操作是在源程序被汇编时完成的，而指令语句的操作必须在程序运行时完成。成的，而指令语句的操作必须在程序运行时完成。6.2.1 汇编程序基本原理汇编语言o宏指令语句宏指令语句n在汇编语言中，还允许用户将多次重复使用的在汇编语言中，还允许用户将多次重复使用的程序段定义为宏。程序段定义为宏。n每个宏都有相应的宏名。每个宏都有相应的宏名。n在程序的任意位置，只要使用宏名，就相当于在程序的任意位置，只要使用宏名，就相当于使用了相应的程序段。使用了相应的程序段。n

17、宏指令语句就是宏的引用。宏指令语句就是宏的引用。6.2.1 汇编程序基本原理汇编程序o功能：功能：将汇编语言所编写的源程序翻译成机器指令程序。将汇编语言所编写的源程序翻译成机器指令程序。o基本工作基本工作n将每一条可执行汇编语句转换成对应的机器指将每一条可执行汇编语句转换成对应的机器指令；令；n处理源程序中出现的伪指令和宏指令。处理源程序中出现的伪指令和宏指令。6.2.1 汇编程序基本原理汇编程序o汇编程序一般需要汇编程序一般需要两次扫描两次扫描源程序才能完成翻源程序才能完成翻译过程。译过程。n第一次扫描第一次扫描 的主要工作是定义符号的值并创建的主要工作是定义符号的值并创建一个符号表一个符号

18、表ST。n第二次扫描第二次扫描 的任务是产生目标程序。在第二次的任务是产生目标程序。在第二次扫描中，可执行汇编语句应被翻译成对应的二扫描中，可执行汇编语句应被翻译成对应的二进制代码机器指令。进制代码机器指令。6.2.1 汇编程序基本原理练习（2008年上）o关于汇编语言，以下叙述中正确的是关于汇编语言，以下叙述中正确的是 （28） 。A、汇编语言源程序可直接在计算机上运行、汇编语言源程序可直接在计算机上运行B、将汇编语言源程序转换成目标程序的软件、将汇编语言源程序转换成目标程序的软件称为解释程序称为解释程序C、在汇编语言程序中，不能定义符号常量、在汇编语言程序中，不能定义符号常量D、将汇编语言

19、源程序翻译成机器语言程序的、将汇编语言源程序翻译成机器语言程序的软件称为汇编程序软件称为汇编程序 练习（2009年下）o以下关于汇编语言和汇编指令的叙述中，正确以下关于汇编语言和汇编指令的叙述中，正确的是的是 （29） 。A、汇编语言程序中只能包含、汇编语言程序中只能包含CPU可直接识别可直接识别的汇编指令的汇编指令B、一条汇编指令可以没有操作码字段，但是、一条汇编指令可以没有操作码字段，但是必须具有操作数字段必须具有操作数字段C、汇编语言源程序都是通过对某种高级语言、汇编语言源程序都是通过对某种高级语言源程序进行编译而得到的源程序进行编译而得到的D、一条汇编指令可以没有操作数字段，但是、一条

20、汇编指令可以没有操作数字段，但是必须具有操作码字段必须具有操作码字段 编译过程概述 编译程序的功能是把编译程序的功能是把某高级语言书写的源程序某高级语言书写的源程序翻译成与之等价的目标程翻译成与之等价的目标程序（汇编语言程序或机器序（汇编语言程序或机器语言程序）。语言程序）。6.2.2 编译程序基本原理编译过程概述o词法分析词法分析n任务：对源程序从前到后（从左到右）逐个字任务：对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个符地扫描，从中识别出一个个“单词单词”符号。符号。n分析依据：语言的词法规则分析依据：语言的词法规则n分析结果：常以二元组方式输出，即单词的种分析结果：常以二

21、元组方式输出，即单词的种类和单词自身的值类和单词自身的值6.2.2 编译程序基本原理编译过程概述o例如，对于某例如，对于某PASCAL源程序中的语句：源程序中的语句：VAR X, Y, Z: real;X := Y+Z*60;词法分析阶段将语句分割成如下的单词序列：词法分析阶段将语句分割成如下的单词序列：（1）保留字）保留字 VAR （2）标识符）标识符 X（3）逗号）逗号 , （4）标识符）标识符 Y（5）逗号）逗号 , （6）标识符）标识符 Z（7）冒号）冒号 : （8）标准标识符）标准标识符 real（9）分号）分号 ; （10）标识符）标识符 X（11）赋值号）赋值号 := （12）标

22、识符）标识符 Y（13）加号）加号 + （14）标识符）标识符 Z（15）乘号）乘号 * （16）整常数）整常数 60（17）分号）分号 ;6.2.2 编译程序基本原理VAR id1, id2, id3: real;id1 := id2+id3*60;编译过程概述o语法分析语法分析n任务：在词法分析的基础上，根据语言的语法任务：在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如规则将单词符号序列分解成各类语法单位，如表达式、语句、程序等。表达式、语句、程序等。n分析结果：分析结果：o如果源程序中没有语法错误，则能正确地构造出如果源程序中没有语法错误，则能正确地构造出其语

23、法树；其语法树；o否则就指出语法错误，并给出相应的诊断信息。否则就指出语法错误，并给出相应的诊断信息。6.2.2 编译程序基本原理编译过程概述6.2.2 编译程序基本原理对语句：对语句：VAR id1, id2, id3: real;id1 := id2 + id3 * 60;进行语法分析后形成如下语法树：进行语法分析后形成如下语法树：编译过程概述o语义分析语义分析n任务：检查源程序是否包含语义错误，并收集任务：检查源程序是否包含语义错误，并收集类型信息供后面的代码生成阶段使用。类型信息供后面的代码生成阶段使用。n分析依据：语言的语义规则分析依据：语言的语义规则n注意：注意：只有语法和语义都正

24、确的源程序才能被只有语法和语义都正确的源程序才能被翻译成正确的目标代码。翻译成正确的目标代码。6.2.2 编译程序基本原理编译过程概述o例如，对语句例如，对语句 id1 := id2 + id3 * 60 进行语义进行语义分析后得到如下的语法树：分析后得到如下的语法树：6.2.2 编译程序基本原理编译过程概述o中间代码生成中间代码生成n任务：根据语义分析的输出生成中间代码。任务：根据语义分析的输出生成中间代码。n中间代码中间代码o是一种简单且含义明确的记号系统是一种简单且含义明确的记号系统o特征：与具体的机器无关特征：与具体的机器无关o设计原则：一是容易生成；二是容易被翻译成目设计原则：一是容

25、易生成；二是容易被翻译成目标代码。标代码。o最常用的一种中间代码是三地址码，其实现方式最常用的一种中间代码是三地址码，其实现方式常采用四元式：常采用四元式：运算符，运算对象运算符，运算对象1，运算对象，运算对象2，运算结果，运算结果6.2.2 编译程序基本原理编译过程概述o例如，对语句例如，对语句 X := Y + Z * 60，可生成以，可生成以下四元式序列：下四元式序列：o(inttoreal, 60, -, t1)o(*, id3, t1, t2)o(+, id2, t2, t3)(:=, t3, -, id1) 6.2.2 编译程序基本原理编译过程概述o代码优化代码优化n优化过程可以在

26、中间代码生成阶段进行，也可优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。以在目标代码生成阶段进行。n代码优化一般建立在对程序的控制流和数据流代码优化一般建立在对程序的控制流和数据流分析的基础之上，与具体的机器无关。分析的基础之上，与具体的机器无关。n优化原则：程序的等价变换规则优化原则：程序的等价变换规则n例如，例如，6.2.2 编译程序基本原理o(inttoreal, 60, -, t1)o(*, id3, t1, t2)o(+, id2, t2, t3)o(:=, t3, -, id1)优化优化o(*, id3, 60.0, t1)o(+, id2, t1, id1)编

27、译过程概述o目标代码生成目标代码生成n任务：把中间代码变换成特定机器上的绝对指任务：把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。令代码、可重定位的指令代码或汇编指令代码。n这个阶段与具体的机器密切相关。这个阶段与具体的机器密切相关。n例如，使用两个寄存器例如，使用两个寄存器R1和和R2，可对上述的，可对上述的四元式生成如下的目标代码：四元式生成如下的目标代码：oMOVF id3, R2oMULF #60.0, R2oMOVF id2, R1oADDF R2, R1MOV R1, id16.2.2 编译程序基本原理编译过程概述o符号表管理符号表管理n作用：记录源程

28、序中各个符号的必要信息，以作用：记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效的查找、插入、程中需要对符号表进行快速有效的查找、插入、修改和删除等操作。修改和删除等操作。n符号表的建立可以始于词法分析阶段，也可以符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。用有时会延续到目标代码的运行阶段。6.2.2 编译程序基本原理编译过程概述o出错处理出错处理n静态错误静态错误o发生在程序编译时发生在程序

29、编译时o分为语法错误和静态语义错误分为语法错误和静态语义错误n动态错误动态错误o也称为动态语义错误也称为动态语义错误o发生在程序运行时发生在程序运行时6.2.2 编译程序基本原理字母表、字符串、字符串集合及运算o字母表字母表：元素的非空有穷集合。：元素的非空有穷集合。o字符字符：字母表：字母表中的一个元素。中的一个元素。o字符串字符串：字母表：字母表中字符组成的有穷序列。中字符组成的有穷序列。o字符串的长度字符串的长度：字符串中的字符个数。：字符串中的字符个数。o空串空串：由：由0 0个字符组成的序列。个字符组成的序列。o连接连接：字符串：字符串S S和和T T的连接是指将串的连接是指将串T

30、T接续在串接续在串S S之后，表之后，表示为示为S ST T，连接符号，连接符号“”可省略。可省略。o空集空集：用符号：用符号表示。表示。o*：指包括空串：指包括空串在内的在内的上所有字符串的集合。上所有字符串的集合。o字符串的方幂字符串的方幂：把字符串：把字符串自身连接自身连接n n次得到的串，称次得到的串，称为字符串为字符串的的n n次方幂，记为次方幂，记为n n 。6.2.2 编译程序基本原理字母表、字符串、字符串集合及运算o字符串集合的运算字符串集合的运算n或（合并）或（合并）：AB=|A 或或 Bn积（连接）积（连接）：AB=|A 且且 Bn幂幂：An=AAn-1=An-1A(n0)

31、，并规定，并规定A0=n正则闭包正则闭包+：A+=A1A2A3Ann闭包闭包*：A*=A0A+。显然，。显然，*=012n6.2.2 编译程序基本原理词法分析器o词法分析的任务是把构成源程序的字符串依据词法分析的任务是把构成源程序的字符串依据词法规则转换成单词符号序列。词法规则转换成单词符号序列。o词法规则可用词法规则可用3型文法（正规文法）或正规表型文法（正规文法）或正规表达式描述，它产生的集合是语言基本字符集达式描述，它产生的集合是语言基本字符集（字母表）上的字符串的一个子集，称为正规（字母表）上的字符串的一个子集，称为正规集。集。6.2.2 编译程序基本原理正规表达式和正规集o定义定义n

32、是一个正规式，表示集合是一个正规式，表示集合L()=。n若若a是是上的字符，则上的字符，则a是一个正规式，它所表是一个正规式，它所表示的正规集为示的正规集为L(a)=a。n若正规式若正规式r和和s分别表示正规集分别表示正规集L(r)和和L(s)，则，则or|s是正规式，表示集合是正规式，表示集合L(r)L(s)。ors是正规式，表示集合是正规式，表示集合L(r) L(s)。or*是正规式，表示集合是正规式，表示集合(L(r)*。o(r)是正规式，表示集合是正规式，表示集合L(r) 。 仅由有限次地使用上述上述三个步骤定义的表仅由有限次地使用上述上述三个步骤定义的表达式才是达式才是上的正规式。上

33、的正规式。6.2.2 编译程序基本原理正规表达式和正规集o设设=a, b6.2.2 编译程序基本原理正规式正规式正规集正规集 ab 符号串符号串ab构成的集合构成的集合 a|b 符号串符号串a、b构成的集合构成的集合 a* 由由0个或多个个或多个a构成的符号串集合构成的符号串集合 (a|b)* 所有字符所有字符a和和b构成的串的集合构成的串的集合 a(a|b)* 以以a为首字符的为首字符的a、b字符串的集合字符串的集合 (a|b)*abb 以以abb结尾的结尾的a、b字符串的集合字符串的集合【练习】o1、(ab|b)*c 与以下哪些串匹配？与以下哪些串匹配？ababbc abab c babc

34、 aaabc答案：答案： ababbc c babc o2、ab*c*(a|b)c 与以下哪些串匹配？与以下哪些串匹配？acac acbbc abbcac abc acc答案：答案：acac abbcac abco3、(a|b)a+(ba)* 与以下哪些串匹配？与以下哪些串匹配？ba bba ababa aa baa答案：答案：ba aa baa6.2.2 编译程序基本原理【练习】o4、正规式、正规式(1|3|5)(202)(c|de)表示的正规集表示的正规集合中元素数目为合中元素数目为 ， 是该正规集合中是该正规集合中的元素。的元素。 A、6 B、7 C、8 D、无穷无穷 A、135202c

35、de B、1202c C、302cde D、52c6.2.2 编译程序基本原理练习（练习（2008下）下）o设正规式设正规式 S = ( a | ba )*，则其对应正规集的，则其对应正规集的字符串字符串 （30） 。A、长度必须是偶数、长度必须是偶数 B、长度必须是奇数、长度必须是奇数C、a不能连续出现不能连续出现 D、b不能连续出现不能连续出现 6.2.2 编译程序基本原理有限自动机o定义定义n有限自动机是一种识别装置的抽象概念，它能有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。准确地识别正规集。o分类分类n确定的有限自动机确定的有限自动机n不确定的有限自动机不确定的有限自动机

36、6.2.2 编译程序基本原理有限自动机o确定的有限自动机（确定的有限自动机（DFA）n一个确定的有限自动机是个五元组一个确定的有限自动机是个五元组：（：（S，f，s0，Z），其中：），其中：oS是一个有限集合，它的每个元素称为一个状态。是一个有限集合，它的每个元素称为一个状态。o是一个有穷字母表，它的每个元素称为一个输入字是一个有穷字母表，它的每个元素称为一个输入字符。符。of是是SS上的单值部分映像。上的单值部分映像。f(A, a)=Q表示当表示当前状态为前状态为A、输入为、输入为a时，将转换到下一状态时，将转换到下一状态Q。称。称Q为为A的一个后继状态。的一个后继状态。os0S，是唯一的一

37、个开始状态。，是唯一的一个开始状态。Z是非空的终止状态集合，是非空的终止状态集合，Z S。6.2.2 编译程序基本原理有限自动机【例】【例】DFA M1=(s0, s1, s2, s3, a, b, f, s0, s3)，其中其中f为：为：f(s0, a)=s1,f(s0, b)=s2, f(s1, a)=s3, f(s1, b)=s2, f(s2, a)=s1, f(s2, b)=s3, f(s3, a)=s36.2.2 编译程序基本原理终态终态abs0s1s2s1s3s2s2s1s3s3s3-状态转换矩阵状态转换矩阵状态状态输入字符输入字符初态初态有限自动机o对于对于中的任何字符串中的任何

38、字符串，若存在一条，若存在一条从初态节点到从初态节点到某一终态节点某一终态节点的路径，且这条路径上所有弧的标记符的路径，且这条路径上所有弧的标记符连接成的字符串等于连接成的字符串等于，则称，则称可由可由DFA MDFA M识别识别（接受（接受或读出）。或读出）。o若一个若一个DFA MDFA M的初态节点同时又是终态节点，则空字的初态节点同时又是终态节点，则空字可由该可由该DFADFA识别（或接受）。识别（或接受）。oDFA MDFA M所能识别的语言所能识别的语言L(M)=|L(M)=|是从是从M M的初态到终态的初态到终态的路径上的弧上标记所形成的串的路径上的弧上标记所形成的串 。6.2.

39、2 编译程序基本原理有限自动机o例如，对于字符串例如，对于字符串“ababaa”ababaa”在上面的状态转换图的在上面的状态转换图的识别路径是识别路径是s s0 0ss1 1ss2 2ss1 1ss2 2ss1 1ss3 3。而。而“abab”abab”和和“baab”baab”不能被该不能被该DFADFA接受。接受。6.2.2 编译程序基本原理有限自动机o不确定的有限自动机（不确定的有限自动机（NFA）n一个不确定的有限自动机也是个五元组一个不确定的有限自动机也是个五元组：（：（S，f，s0，Z），它与），它与DFA的区别如下：的区别如下：of是是S2S上的映像。对于上的映像。对于S中的一

40、个给定这台及中的一个给定这台及输入符号，返回一个状态的集合。即当前状态的后输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。继状态不一定是唯一确定的。有向弧上的标记可以是有向弧上的标记可以是。6.2.2 编译程序基本原理有限自动机【例】【例】NFA N=(s0, s1, s2, s3, a, b, f, s0, s3)，其中其中f为：为：f(s0, a)=s0,f(s0, a)=s1, f(s0, b)=s0, f(s1, b)=s2, f(s2, b)=s3abs0s0, s1s0s1-s2s2-s3s3-6.2.2 编译程序基本原理状态转换矩阵状态转换矩阵显然，显然，D

41、FA是是NFA的特例。的特例。练习（2009年上）o下图所示的有限自动机中，下图所示的有限自动机中，s0是初始状态，是初始状态，s3是终止状是终止状态，该自动机不能识别态，该自动机不能识别 （31） 。 A、abab B、aaaa C、babb D、abba练习（2009年下）o某有限自动机的状态图如下图所示，其特点是某有限自动机的状态图如下图所示，其特点是 （31） 。A、仅识别以、仅识别以0开始以开始以1结尾的结尾的0、1串串B、仅识别含有、仅识别含有3个个0的的0、1串串C、仅识别含有偶数个、仅识别含有偶数个1的的0、1串串D、仅识别以、仅识别以0开始以开始以1结尾且结尾且0和和1交错出

42、现的交错出现的0、1串串 练习（2010年上）o某有限状态自动机的状态图如下图所示（状态某有限状态自动机的状态图如下图所示（状态0是初态，是初态，状态状态2是终态），则该自动机不能识别是终态），则该自动机不能识别 （30） 。 A、abab B、aabb C、bbaa D、bbab词法分析器o手工构造词法分析器的方法手工构造词法分析器的方法n用正规式描述语言规定的单词符号；用正规式描述语言规定的单词符号；n构造相应有限自动机的状态转换图；构造相应有限自动机的状态转换图；从状态转换图出发编写词法分析器（程序）。从状态转换图出发编写词法分析器（程序）。6.2.2 编译程序基本原理语法分析o程序语言

43、的语法常采用上下文无关文法描述。程序语言的语法常采用上下文无关文法描述。o文法不仅规定了单词如何组成句子，而且刻画文法不仅规定了单词如何组成句子，而且刻画了句子的组成结构。了句子的组成结构。o形式文法是一个规则（或称产生式）系统，它形式文法是一个规则（或称产生式）系统，它规定了单词在句子中的位置和顺序，也刻画了规定了单词在句子中的位置和顺序，也刻画了句子的层次结构。句子的层次结构。6.2.2 编译程序基本原理练习（2008年上）o对高级语言源程序进行编译时，可发现源程序对高级语言源程序进行编译时，可发现源程序中的中的 （29） 错误。错误。A、堆栈溢出、堆栈溢出 B、变量未定义、变量未定义 C

44、、指针异常、指针异常 D、数组元素下标越界、数组元素下标越界 练习（2008年下）o编译型程序设计语言若规定程序中的变量必须编译型程序设计语言若规定程序中的变量必须先定义（或声明）再引用，那么违反此规定的先定义（或声明）再引用，那么违反此规定的程序在程序在 （28） 时报错。时报错。A、编辑、编辑 B、编译、编译 C、链接、链接 D、运行、运行 解释程序o工作原理工作原理n在运行用户程序时，直接执行源程序或源程序在运行用户程序时，直接执行源程序或源程序的内部形式。的内部形式。n不产生源程序的目标程序。不产生源程序的目标程序。6.2.3 解释程序基本原理1:11:n解释程序o基本结构基本结构n分

45、析部分分析部分 包括通常的词法分析、语法分析和语义分包括通常的词法分析、语法分析和语义分析程序，经语义分析后把源程序翻译成中间代析程序，经语义分析后把源程序翻译成中间代码，中间代码采用逆波兰表示形式。码，中间代码采用逆波兰表示形式。n解释部分解释部分 用来对分析部分产生的中间代码进行解释用来对分析部分产生的中间代码进行解释执行。执行。6.2.3 解释程序基本原理编译和解释工作方式的比较o效率效率n编译比解释方式可能取得更高的效率编译比解释方式可能取得更高的效率o灵活性灵活性n解释方式能够比编译方式更灵活解释方式能够比编译方式更灵活o可移植性可移植性n只要对解释器进行重新编译，就可以使解释器只要

46、对解释器进行重新编译，就可以使解释器运行在不同的环境中运行在不同的环境中练习（2009年上）o （28） 属于系统软件，它直接执行高级语言属于系统软件，它直接执行高级语言源程序或与源程序等价的某种中间代码。源程序或与源程序等价的某种中间代码。A、编译程序、编译程序 B、预处理程序、预处理程序 C、汇编程序、汇编程序 D、解释程序、解释程序 练习（2009年下）o （30） 的任务是将来源不同的编译单元装配的任务是将来源不同的编译单元装配成一个可执行程序。成一个可执行程序。A、编译程序、编译程序 B、解释程序、解释程序 C、链接程序、链接程序 D、装入程序、装入程序C语言的特点o具有低级语言的功

47、能，允许直接访问物理地址具有低级语言的功能，允许直接访问物理地址和进行位运算。和进行位运算。o具有高级语言的功能，有结构化控制语句流，具有高级语言的功能，有结构化控制语句流，是结构化程序设计语言。是结构化程序设计语言。o可用于系统软件的开发，也可用于应用软件的可用于系统软件的开发，也可用于应用软件的开发。开发。o安全性低，如：对指针没有适当的限制。指针安全性低，如：对指针没有适当的限制。指针错误，可能引起内存中的信息被破坏，如果经错误，可能引起内存中的信息被破坏，如果经常出现这种错误，极有可能导致系统的崩溃。常出现这种错误，极有可能导致系统的崩溃。6.1.3 程序语言的基本成分第一个程序/*

48、该程序在屏幕上输出 Hello, world! */#include void main( ) printf(Hello, world!n);注释行注释行预处理命令预处理命令主函数主函数语句语句6.1.3 程序语言的基本成分说明o函数是函数是C语言程序的基本单位。语言程序的基本单位。o一个一个C语言程序一般由一个主函数和若干其他语言程序一般由一个主函数和若干其他函数组成。函数组成。o一个一个C语言程序必须包含且只能包含一个语言程序必须包含且只能包含一个main函数。函数。oC语言程序从语言程序从main函数开始执行，调用其他函函数开始执行，调用其他函数后再返回数后再返回main函数。函数。6.

49、1.3 程序语言的基本成分数据类型6.1.3 程序语言的基本成分C语语言言的的数数据据类类型型基本类型基本类型聚合类型聚合类型指针类型指针类型 以以 * 为标志为标志整型整型 int实型实型单精度型单精度型 float双精度型双精度型 double字符型字符型 char空类型空类型 void数组类型数组类型 以以 为标志为标志结构体类型结构体类型 struct共用体类型共用体类型 union枚举类型枚举类型 enum基本类型的修饰符o除除 void 类型外，基本类型的前面可以有各种类型外，基本类型的前面可以有各种修饰符。修饰符。nsigned（有符号）（有符号）nunsigned（无符号）（无

50、符号）nlong（长型符）（长型符）nshort（短型符）（短型符）适用于字符型和整型适用于字符型和整型可用于可用于double类型类型6.1.3 程序语言的基本成分名称名称类型类型位数位数取值范围取值范围整型整型int16-3276832767短整型短整型short16-3276832767长整型长整型long32-2147483648 2147483647无符号整型无符号整型unsigned int16065535无符号短整型无符号短整型unsigned short16065535无符号长整型无符号长整型unsigned long3204294967295单精度型单精度型float32-3

51、.4*1038 3.4*1038双精度型双精度型double64-1.7*10308 1.7*10308字符型字符型char8-128127标识符o命名规则命名规则n由英文字母或下划线开头。由英文字母或下划线开头。n在第一个字符后，可以是任意的字母、数字和在第一个字符后，可以是任意的字母、数字和下划线的序列。下划线的序列。长度不超过长度不超过8个。个。n不能跨行书写。不能跨行书写。n区分大小写。区分大小写。n自定义标识符不能与关键字同名。自定义标识符不能与关键字同名。6.1.3 程序语言的基本成分常量和变量o常量常量n在程序运行过程中，其值不能改变的量称为常在程序运行过程中，其值不能改变的量称

52、为常量。量。n分为整型常量、实型常量、字符型常量和符号分为整型常量、实型常量、字符型常量和符号常量。常量。o变量变量n在程序运行过程中其值可以改变的量称为变量。在程序运行过程中其值可以改变的量称为变量。n变量名是用标识符来表示的。变量名是用标识符来表示的。n所有的所有的C变量必须先定义后使用。变量必须先定义后使用。6.1.3 程序语言的基本成分变量的定义o定义变量的一般形式：定义变量的一般形式：变量类型变量类型 变量名表变量名表; 其中，变量名表可以由一个或多个标识符其中，变量名表可以由一个或多个标识符名构成，中间用名构成，中间用“,”分隔。分隔。例如：例如：int a, b, c; char

53、 s;注意：此时变量的值为不定值。注意：此时变量的值为不定值。6.1.3 程序语言的基本成分变量的初始化o变量的初始化，即为变量赋值。变量的初始化，即为变量赋值。o例如：例如：int a, b; a = 1; b = 2;等价于：等价于：int a=1, b=2;6.1.3 程序语言的基本成分整型常量o十进制数：以非十进制数：以非0数字开头的数。数字开头的数。例如：例如：123、-45、0o八进制数：以八进制数：以数字数字0开头的数。开头的数。例如：例如：012 表示八进制表示八进制 (12)8 ，等于十进制数，等于十进制数 (10)10o十六进制数：以十六进制数：以0 x或或0X开头的数。开

54、头的数。例如：例如：0 x12 表示十六进制表示十六进制 (12)16 ，等于十进，等于十进制数制数 (18)106.1.3 程序语言的基本成分整型变量o三种类型：短整型（三种类型：短整型（short int）、普通整型）、普通整型（int） 和长整型（和长整型（long int）o每种类型分为有符号型（每种类型分为有符号型（signed）和无符号型）和无符号型（unsigned）。默认时为）。默认时为signed类型。类型。o无符号数：在整常数后加无符号数：在整常数后加字母字母U或或u。例如：例如：unsigned u;u = 123U;o长整型：在整常数后加长整型：在整常数后加字母字母L或

55、或l。例如：例如：long l;l = 45L;6.1.3 程序语言的基本成分实型常量o十进制形式：由数字和小数组成（十进制形式：由数字和小数组成（必须有小数点必须有小数点），），但小数点前后的但小数点前后的0可以省略。可以省略。例如：例如：12.3、0.12、.45、1.o指数形式：由整数部分、小数部分和指数部分构成。指数形式：由整数部分、小数部分和指数部分构成。指数部分，即指数部分，即 E（或（或e）后面的数必须是整数。）后面的数必须是整数。例如：例如：1.2E2表示表示 1.2102， 3.E-2表示表示 3.010-2， .45e3表示表示 0.451036.1.3 程序语言的基本成分

56、实型变量o三种类型：单精度型（三种类型：单精度型（float）、双精度型）、双精度型（double）、长双精度型（）、长双精度型（long double）o一个实型常数默认为一个实型常数默认为double型。型。ofloat型数：在实数后面加上型数：在实数后面加上字母字母f或或F。例如：例如：float f; f = 12.45f;olong double型数：在实数后面加上型数：在实数后面加上字母字母l或或L。例如：例如：long double ld; ld = 12.36L;6.1.3 程序语言的基本成分字符常量o字符常量是用字符常量是用单引号单引号括起来的括起来的单个字符单个字符。例如：

57、例如：A、b、*o转义字符：以转义字符：以 开头的字符序列。开头的字符序列。nn 回车换行回车换行nt 水平制表符水平制表符nddd 三位八进制数三位八进制数 例如：例如：101 字母字母A（ASCII值：值：65）nxhh 两位十六进制数两位十六进制数例如：例如：x42 字母字母B（ ASCII值：值：66）6.1.3 程序语言的基本成分字符串常量o字符串常量是由一对字符串常量是由一对双引号双引号括起来的字符序列。括起来的字符序列。例如：例如：Hello、123456oC语言编译器会自动在字符串的末尾加一个转语言编译器会自动在字符串的末尾加一个转义字符义字符 0，作为字符串常量的结束标志。，

58、作为字符串常量的结束标志。例如：例如：a和和a是完全不同的。前者是字符常是完全不同的。前者是字符常量，占的字节数是量，占的字节数是1；后者是字符串常量，占；后者是字符串常量，占的字节数是的字节数是2。oC语言中没有专门的字符串变量，字符串变量语言中没有专门的字符串变量，字符串变量只能存放在字符型数组中。只能存放在字符型数组中。6.1.3 程序语言的基本成分符号常量o定义的一般形式：定义的一般形式：#define 标识符标识符 字符串字符串o说明：说明：ndefine是是预编译命令，在预编译命令，在编译之前编译之前中用对应的中用对应的字符串字符串替换替换程序中的标识符，然后再编译程序程序中的标识

59、符，然后再编译程序n该定义必须放在该定义必须放在程序的开头程序的开头，每个定义，每个定义独占一独占一行行；不是语句，尾部；不是语句，尾部不跟分号不跟分号。n为了与变量区分，一般符号常量用为了与变量区分，一般符号常量用大写大写表示。表示。6.1.3 程序语言的基本成分符号常量的使用#define PI 3.14void main() int r=3; float c, s; c = 2*PI*r; s = PI*r*r; printf(c=%f, s=%fn, l, s);6.1.3 程序语言的基本成分 当开始编译前，系统先将程序中当开始编译前，系统先将程序中所有的所有的 PI 标识标识符换成符

60、换成 3.14，再进行编译。，再进行编译。符号常量的使用#define R 10-7void main() int x; x = 3 * R; printf(“x=%dn, x);6.1.3 程序语言的基本成分运行结果：运行结果：x = 23枚举类型o定义的一般形式：定义的一般形式：enum 类型标识符类型标识符 枚举值名表枚举值名表 ;o例如：例如：enum weekday sun, mon, tue, wed, thu, fri, sat;o说明：说明：n每一个枚举值都有一个序号，并规定从每一个枚举值都有一个序号，并规定从0开始编开始编号。号。n第一个枚举值的序号为第一个枚举值的序号为0，以后顺序加，以后顺序加1。6.