第2章

程序语言基础

本章要点

程序设计语言的基本成分

汇编语言的基本原理

编译程序的基本原理

解释程序的基本原理

文法和语言的形式描述

正规式

有限状态机

2.1 程序语言概述

考核说明：本节主要介绍程序设计语言的定义、发展和分类，程序设计语言的基本成分，后者是重点，经常会考到，其中数据成分和函数是考核要点，要理解掌握。

2.1.1 程序设计语言的基本概念

1. 低级语言和高级语言

1) 低级语言

通常称机器语言和汇编语言为低级语言。机器语言是指用0、1字符串组成的机器指令序列，是最基本的计算机语言；汇编语言是指用符号表示指令的语言。汇编语言仍然是一种面向机器的语言。

2) 高级语言

高级语言是从人类的逻辑思维角度出发、面向各类应用的程序语言，抽象程度大大提高。这类语言与人们使用的自然语言比较接近，大大提高了程序设计的效率。常见的C、C++、Java、PHP等都是高级语言。

2. 编译程序和解释程序

用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。如果源程序是使用汇编语言编写的，则需要一个称为汇编程序的翻译程序将其翻译成目标程序后才能执行。如果源程序是使用某种高级语言编写的，则需要相应的解释程序或编译程序对其进行翻译，然后才能在机器上运行。

注意：在解释方式下，翻译源程序时不生成独立的目标程序，而编译器则会将源程序翻译成独立保存的目标程序。

3. 程序设计语言的定义

(1) 语法：由程序设计语言的基本符号组成程序中的各个语法成分(包括程序)的一组规则，其中由基本符号构成符号(单词)的书写规则称为词法规则，由符号(单词)构成语法成分的规则称为语法规则。程序语言的语法可通过形式语言进行描述。

(2) 语义：程序语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。

(3) 语用：表示构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。

(4) 语境：理解和实现程序设计语言的环境，包括编译环境和运行环境。

4. 程序设计语言的发展

FORTRAN是及时个被广泛用来进行科学计算的高级语言。

ALGOL60是一个分程序结构的语言，它采用巴科斯范式(BNF)来描述语言的语法。

COBOL是一种面向事务处理的高级语言，主要用于情报检索、商业数据处理等。

Pascal是一种结构化程序设计语言，它从ALGOL60衍生而来。

C语言是一种通用程序设计语言，允许程序员直接访问操作系统和底层硬件，因此在系统级应用和实时处理应用的开发中成为主要语言。

C++是在C语言的基础上发展起来的，增加了类机制，成为面向对象的程序设计语言。

Java的初始用途是开发网络浏览器的小应用程序，目前已广泛应用于个人电脑(PC)、数据中心、游戏控制台、移动电话和互联网等。

PHP是一种在服务器端执行的、嵌入HTML文档的脚本语言，可以快速地执行动态网页，其语法风格类似于C语言。

Python是一种面向对象的解释型程序设计语言，可用于编写独立程序、快速脚本和复杂应用的原型。

Delphi是一种可视化开发工具，主要特性是基于窗体和面向对象的方法、高速的编译器、强大的数据库支持、与Windows编程紧密结合以及成熟的组件技术。

5. 程序设计语言的分类

1) 命令式程序设计语言

命令式程序设计语言是基于动作的语言，在这种语言中，计算被看作动作的序列。命令式语言族开始于FORTRAN、Pascal和C语言，体现了命令式程序设计的关键思想。

2) 面向对象的程序设计语言

C++、Java和Smalltalk是面向对象程序设计语言的代表。

3) 函数式程序设计语言

函数式程序设计语言是一类以-演算为基础的语言。该语言的代表是LISP语言，其中大量使用了递归。

4) 逻辑型程序设计语言

逻辑型程序设计语言是一类以形式逻辑为基础的语言。该语言的代表是建立在关系理论和一阶谓词理论基础上的Prolog语言。

真题链接

[例2-1]可用于编写独立程序和快速脚本的语言是 (20) 。(2012年11月真题20)

(20) A.Python B.Prolog C.Java D.C#

[解析]Python是一种面向对象的解释型程序设计语言，可用于编写独立程序、快速脚本和复杂应用的原型。Python也是一种脚本语言，它支持对操作系统底层的访问。

Prolog是一种逻辑型语言。Prolog程序是一系列事实、数据对象或事实间的具体关系和规则的集合。Prolog有很强的推理功能，适用于书写自动定理证明、专家系统、自然语言理解等问题的程序。

Java是一种面向对象的程序设计语言，能开发应用在Internet上且具有软、硬件独立性和交互能力的程序。Java可以一次编写而到处运行。

C#是微软公司的一种面向对象的、运行于.NET Framework(框架)之上的高级程序设计语言。C#看起来与Java有着惊人的相似：它包括了诸如单一继承、接口、与Java几乎同样的语法和编译成中间代码再运行的过程。但是C#与Java有着明显的不同，它借鉴了Delphi的一个特点，与COM(组件对象模型)是直接集成的，而且它是微软公司.NET Windows网络框架的主角。

[答案]A

2.1.2 程序设计语言的基本成分

1. 数据成分

程序语言的数据成分是指一种程序语言的数据类型。

1) 常量和变量

按照程序运行时数据的值能否改变，将数据分为常量和变量。程序中的数据对象可以具有左值和(或)右值，左值是指存储单元(或地址、容器)，右值是指具体值(或内容)。变量具有左值和右值，在程序运行过程中其右值可以改变；常量只有右值，在程序运行过程中其右值不能改变。

2) 全局量和局部量

按数据的作用域范围，数据可分为全局量和局部量。系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的，而为局部变量分配的存储单元是动态改变的。

3) 数据类型

按照数据组织形式的不同可将数据分为基本类型、用户定义类型、构造类型及其他类型。C(C++)的数据类型如下所示。

基本类型：整型(int)、字符型(char)、实型(float、double)和布尔型(bool)。

特殊类型：空类型(void)。

用户定义类型：枚举类型(enum)。

构造类型：数组、结构和联合。

指针类型：type 。

抽象数据类型：类类型。

其中，布尔类型和类类型是C++在C语言的基础上扩充的。

2. 运算成分

程序语言的运算成分是指允许使用的运算符号及运算规则。大多数高级程序语言的基本运算可以分成算术运算、关系运算和逻辑运算，有些语言还提供位运算。运算符号的使用与数据类型密切相关。为了确保运算结果的性，运算符号要规定优先级和结合性，必要时还要使用圆括号。

3. 控制成分

控制成分用于指明语言允许表述的控制结构，程序员使用控制成分来构造程序中的控制逻辑。

1) 顺序结构

在顺序结构中，计算过程从所描述的及时个操作开始，按顺序依次执行后续的操作，直到执行完序列的一个操作。顺序结构内也可以包含其他控制结构。

2) 选择结构

选择结构提供了在两种或多种分支中选择执行其中一个分支的逻辑。基本的选择结构是指定一个条件P，然后根据条件的成立与否决定控制流走计算A还是走计算B，从两个分支中选择一个执行。

3) 循环结构

循环结构描述了重复计算的过程，通常包括三个部分：初始化、需要重复计算的部分和重复的条件。其中初始化部分有时在控制的逻辑结构中不进行显式的表示。循环结构主要有两种形式：while型重复结构和do-while型重复结构。

4. C(C++)语言提供的控制语句

C(C++)语言提供的控制语句如下。

(1) 复合语句。复合语句是一系列用"{"和"}"括起来的声明和语句，其主要作用是将多条语句组成一个可执行单元。复合语句是一个整体。

(2) if语句和switch语句。这两种语句用于实现选择结构。

if语句实现的是双分支的选择结构。

switch语句描述了多分支的选择结构。

(3) 循环语句。C(C++)语言提供了三种形式的循环语句用于描述循环计算的控制结构。

while语句。

do-while语句。

for语句。

5. 函数

函数是程序模块的主要成分，它是一段具有独立功能的程序。函数的使用涉及三个概念：函数定义、函数声明和函数调用。

(1) 函数定义：包括函数首部和函数体两个部分。函数的定义描述了函数做什么和怎么做。

(2) 函数声明：函数应该先声明后引用。函数声明定义了函数原型。声明函数原型的目的在于告诉编译器传递给函数的参数个数、类型以及函数返回值的类型，参数表中仅需要依次列出函数定义中的参数的类型。编译器可以通过函数原型检查源程序中对函数的调用是否正确。

(3) 函数调用：当需要在一个函数(称为主调函数)中使用另一个函数(称为被调函数)实现的功能时，便以函数名字进行调用，称为函数调用。调用函数和被调用函数之间交换信息的方法主要有两种：一种是由被调用函数把返回值返回给主调函数，另一种是通过参数带回信息。函数调用时实参和形参之间交换信息的方法有传值调用和引用调用两种。

传值调用。若实现函数调用时实参向形式参数传递相应类型的值(副本)，则称为传值调用。这种方式下形式参数不能向实际参数传递信息。在C语言中，要实现被调用函数对实际参数的修改，必须用指针作形参。即调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参，本质上仍属于传值调用。这种方式实现了间接内存访问。

引用调用。引用是C++中增加的数据类型，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实际参数所做的访问和改变。

真题链接

[例2-2]弱类型语言(动态类型语言)是指不需要进行变量/对象类型声明的语言。 (50) 属于弱类型语言。(2013年11月真题50)

(50) A.Java B.C/C++ C.Python D.C#

[解析]根据定义可知Java、C/C++、C#都需要进行变量/对象声明，所以说是强类型语言。而Python不需要，它属于弱类型语言。

[答案]C

[例2-3]程序运行过程中常使用参数在函数(过程)间传递信息，引用调用传递的是实参的 (20) 。(2014年5月真题21)

(20) A.地址 B.类型 C.名称 D.值

[解析]引用就是某一变量(目标)的一个别名，对引用的操作与对变量直接操作一样。表示该引用名是目标变量名的一个别名。

[答案]C

2.2 语言处理程序基础

考核说明：本节主要介绍汇编语言、编译程序和解释程序的基本原理，编译程序部分经常考到，是重点也是难点，要能透彻理解。

2.2.1 汇编语言的基本原理

1. 汇编语言

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。用汇编语言编写的程序称为汇编语言源程序。

汇编语言源程序由若干条语句组成。一个程序中可以有三类语句：指令语句、伪指令语句和宏指令语句。

(1) 指令语句：又称为机器指令语句，汇编后能产生相应的机器代码，被CPU直接识别并执行相应的操作。指令语句可分为传送指令、算术运算指令、逻辑运算指令、移位指令、转移指令和处理机控制指令等。

(2) 伪指令语句：指示汇编程序在对源程序进行汇编时完成某些工作。与指令语句的区别是：伪指令语句经汇编后不产生机器代码，另外，伪指令语句所指示的操作是在源程序被汇编时完成的，而指令语句的操作必须在程序运行时完成。

(3) 宏指令语句：将多次重复使用的程序段定义为宏。宏的定义必须按照相应的规定进行，每个宏都有相应的宏名。

2. 汇编程序

汇编程序的功能是将用汇编语言编写的源程序翻译成机器指令程序。它一般至少需要两次扫描源程序才能完成翻译过程。及时次扫描的主要工作是定义符号的值并创建一个符号表(ST)；第二次扫描的任务是产生目标程序。除了使用前一次扫描所产生的符号表(ST)外，还要使用机器指令表(MOT2)。在第二次扫描过程中，可执行汇编语句应被翻译成对应的二进制代码机器指令。这一过程涉及两个方面的工作：一是把机器指令助记符转换成二进制机器指令操作码，这可通过查找MOT2来实现；二是求出操作数区各操作的值(用二进制表示)。

2.2.2 编译程序的基本原理

编译程序的功能是把用高级语言书写的源程序翻译成与之等价的目标程序。编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，实际的编译器可能会将其中的某些阶段结合在一起进行处理。

1. 词法分析阶段

词法分析阶段的任务是对源程序从前到后(从左到右)逐个字符进行扫描，从中识别出一个个"单词"符号。"单词"符号是程序设计语言的基本语法单位，如关键字、标识符等。词法分析程序输出的"单词"常常采用二元组的方式，即单词类别和单词自身的值。

2. 语法分析阶段

语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如"表达式"、"语句"和"程序"等。词法分析和语法分析本质上都是对源程序的结构进行分析。

过程(函数)说明和过程(函数)调用是程序中一种常见的语法结构。过程说明和调用语句的翻译，有赖于形式参数和实际参数结合的方式以及数据空间的分配方式。需要分配存储空间的对象有基本数据类型、结构化数据类型和连接数据(如返回地址、参数等)。分配的依据是名字的作用域和生存期的定义规则。分配的策略有静态存储分配和动态存储分配两大类。

如果在编译时就能确定目标程序运行时所需要的全部空间大小，则在编译时就可以安排好目标程序运行时的全部数据空间，并确定每个数据对象的存储位置。这种分配策略为静态存储分配。

如果一个程序语言允许递归过程和可变数据结构，那么就需要采用动态存储分配技术。动态存储分配策略的实现有栈分配和堆分配两种方式。

3. 语义分析阶段

语义分析阶段主要是审查源程序是否存在语义错误，并收集类型信息供后面的代码生成阶段使用，只有语法和语义都正确的源程序才能翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。

描述程序语义的形式化方法主要有属性文法、公理语义、操作语义和指称语义等，其中属性文法是对上下文无关文法的扩充。目前广泛使用的静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性值的计算以语义规则的形式赋予文法的产生式。在语法分析的推导或归纳的步骤中，通过语义规则实现对属性值的计算，以达到对语义的处理。

4. 中间代码生成阶段

中间代码是一种结构简单且含义明确的记号系统，可以有多种形式。中间代码生成阶段的工作就是根据语义分析的输出生成中间代码。语义分析和中间代码生成所依据的是语言的语义规则。

实际上，中间代码起着编译器前端和后端分水岭的作用，使用中间代码有利于提高编译程序的可移植性。常用的中间代码有后缀式、三元式、四元式和树等形状。

后缀式：把运算符写在运算对象的后面。例如，ab的后缀式为ab。这种表示法的优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号，也便于用栈实现求值。

三元式：由运算符OP、及时运算对象ARG1和第二运算对象ARG2组成。例如，x:=a+b的三元式为：① (+, a, b) ② (:=, ①, x)。

四元式：组成成分为运算符OP、及时运算对象ARG1、第二运算对象ARG2和运算结果RESULT。例如，x:=a+b的四元式为：① (+, a, b, t) ② (:=, t, _, x)。

树：例如，表达式x:=(a+b)(c-d)可以表示为图2-1所示的结构。

图2-1 树型结构

5. 代码优化阶段

代码优化阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。

6. 目标代码生成阶段

目标代码生成阶段的任务是把中间代码变换成特定机器上的指令代码、可重定位的指令代码或汇编指令代码。这是编译的阶段，它的工作与具体的机器密切相关。

7. 符号表管理

符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成。符号表的建立可以始于词法分析阶段，也可以放到语法分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。

8. 出错处理

用户编写的源程序中的错误大致可分为静态错误和动态错误。动态错误也称动态语义错误，指程序中包含的逻辑错误。静态错误是指编译阶段发现的程序错误，可分为语法错误和静态语义错误。出错处理程序的任务包括检查错误、报告出错信息、排错、恢复编译工作。

真题链接

[例2-4]将高级语言源程序翻译成机器语言程序的过程，常引入中间代码。以下关于中间代码的叙述中，不正确的是 (22) 。(2014年11月真题22)

(22) A.中间代码不依赖于具体的机器

B. 使用中间代码可提高编译程序的可移植性

C.中间代码可以用树或图表示

D.

……