二、程序设计语言基础知识

发表于 2025-04-25 分类于软件设计师

1 程序设计语言概述

本节主要介绍程序设计语言的基本概念、基本成分和一些有代表性的程序设计语言。

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

1.1.1 低级语言和高级语言

机器语言 ：计算机硬件唯一能直接识别和执行的语言，由 0 和 1 组成的机器指令序列。其特点是效率高（执行度快），但存在效率低（编写困难）、可读性差、难以修改和维护等缺点。
汇编语言 ：用助记符（如 ADD 表示加法、SUB 表示减法等）代替机器指令的二进制代码，克服了机器语言的点，提高了程序设计效率，但汇编语言仍然面向机器，需用汇编程序将汇编语言编写的程序翻译成机器语言程序才能被计算执行。
低级语言 ：机器语言和汇编语言的统称，它们与计算机硬件紧密相关，依赖于特定的计算机系统和机器指令。
高级语言 ：为了克服低级语言的缺点而开发，具有功能更强、抽象级别更高、通用性强、易学易用等特点，且与硬件关系相对疏远，常见的有 Java、C、C++、PHP、Python、Delphi、PASCAL 等。高级语言编写的程序需经过编译或解释才能被计算机执行，虽然执行速度不如低级语言，但大大提高了程序设计的效率和可维护性。

1.1.2 编译程序和解释程序

语言处理程序

作用：将高级语言翻译为计算机可执行的机器语言。
源程序 ：用高级或汇编语言编写的程序，需翻译后才能执行。

解释程序

定义：逐条翻译并执行源程序。
特点：不生成独立目标程序，解释程序参与运行。

编译程序

定义：将整个源程序翻译成目标程序。
特点：生成独立目标程序，编译后源程序和编译程序不参与运行。

区别

目标程序生成 ：编译生成独立目标程序，解释不生成。
执行过程 ：编译后目标程序独立运行，解释时解释程序参与运行。

1.1.3 程序设计语言的定义

定义要素

语法：程序设计语言基本符号组成语法成分的规则，包括词法规则（字符构成符号）和语法规则（符号构成语法分），可用形式语言描述。
语义：语法成分的含义，分静态语义（编译时确定）和动态语义（运行时确定），程序执行效果由其各部分语义定。
语用：语言符号与使用者的关系，涉及符号的来源、使用和影响。
语境：理解和实现语言的环境，包括编译环境和运行环境。

1.1.4 程序设计语言分类

1.1.4.1 程序设计语言发展概述

Fortran ：首个广泛用于科学和工程计算的高级语言，程序由主程序和子程序组成，特点是接近数学公式自然描述执行效率高，用于并行计算和高性能计算。
ALGOL ：程序设计语言发展里程碑，主导 20 世纪 60 年代程序语言发展，奠定软件自动化及软件可靠性基础，入局部性、动态、递归等概念。
PASCAL ：结构化程序设计语言，由 ALGOL 衍生，功能强且易用，曾在高校计算机教学中占主导地位。
C 语言 ：通用程序设计语言，兼具高级和汇编语言特点，提供丰富运算符集合和紧凑语法结构，系统级应用和实时理应用开发的主要语言。
C++ ：基于 C 语言发展，兼容 C，增加封装、抽象和类机制，面向对象的语言。
C# ：Microsoft 开发的面向对象语言，运行于.NET Framework，相对于 C++ 有诸多限制和增强。
Objective - C ：继承 C 特性，面向对象，主要由 Apple 维护，是 MAC 系统主要开发语言，仅支持单继承。
Java ：通用程序设计语言，保留 C++ 基本语法，删去部分不良特征，更简单且语法和语义更合理。
Ruby ：解释型、面向对象、动态类型脚本语言，任何东西都是对象，变量无类型。
PHP ：服务器端执行、嵌入 HTML 的脚本语言，语法类似 C，充分利用服务器性能，支持多种数据库和操作系统。
Python ：面向对象解释型语言，可用于编写独立程序、快速脚本和复杂应用原型，支持底层访问，可扩展。
JavaScript ：脚本语言，用于 Web 应用开发，添加网页动态功能，嵌入 HTML 实现自身功能。
Delphi ：可视化开发工具，Windows 环境下使用，基于面向对象和构件技术。
Visual Basic.NET ：基于.NET Framework 的编程语言，源代码编译成中间代码 MSIL，需.NET Framework 支持。

1.1.4.2 程序设计语言分类

命令式和结构化程序设计语言：命令式语言基于动作序列，结构化程序设计语言属于命令式语言分支，特点为自顶下编程、模块化编程、程序构造单入口单出口，C、PASCAL 是典型代表。
面向对象的程序设计语言：从 Simula 发展而来，C++、Java、Smalltalk 是代表，需支持数据隐藏、抽象用户定义类型、继承和多态等技术。
函数式程序设计语言*：以 λ-演算为基础，基本概念来自 LISP，函数是对应规则，可用其他函数替代表达式中函数，LISP 程序和数据形式等价，大量使用递归。
逻辑型程序设计语言：以形式逻辑为基础，PROLOG 是代表，基于 Hore 子句，通过事实和规则进行推理，采用归结方法响应用户询问，适用于自动定理证明等领域。

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

程序设计语言的基本成分包括数据、运算、控制和传输等。

1.2.1 程序设计语言的数据成分

数据对象与数据表示：数据对象对应应用系统中有意义的事物，数据表示是程序中值的组织形式。数据类型代表数对象，用于值的内存布局和运算检查。
数据的属性：数据具有存储类别、类型、名称、作用域和生存期等属性，使用时需分配内存空间。
常量与变量：
- 常量：程序运行时值不可改变，只有右值。
- 变量：程序运行时值可改变，具有左值和右值。
全局量与局部量：
- 全局量 ：作用域为整个文件或程序，存储空间在程序运行过程中不改变。
- 局部量 ：作用域为定义它的函数或语句块，存储单元动态改变。
数据类型 ：按数据组织形式分为基本类型、用户定义类型、构造类型及其他类型。C（C++）的数据类型包括基本类型（整型、字符型、实型、布尔型）、特殊类型（空类型）、用户定义类型（枚举类型）、构造类型（数组、结构、联合）、指针类型、抽象数据类型（类类型，由 C++ 提供）。

1.2.2 程序设计语言的运算成分

运算符号及规则 ：指明允许使用的运算符号及运算规则，与数据类型密切相关。
运算分类 ：高级语言基本运算包括算术、关系和逻辑运算等，C、C++ 等语言还提供位运算。
运算规则 ：运算符号有优先级和结合性，必要时用圆括号明确运算结果。

1.2.3 程序设计语言的控制成分

控制结构概述：三种基本控制结构（顺序、选择和循环）可描述所有可计算问题的程序。

顺序结构：表示按顺序依次执行操作，从第一个到最后一个，结构内可包含其他控制结构。

选择结构

基本形式 ：条件 P 成立则执行计算 A，否则执行计算 B，A 和 B 中还可嵌套其他控制结构。
简化形式 ：无计算 B 的分支结构。

循环结构

组成：初始化、循环体和循环条件，初始化有时不在逻辑结构中显式表示。
两种形式 ：
- while 型 ：先判断条件 P，成立则执行循环体 A，否则退出。
- do - while 型 ：先执行循环体 A，再判断条件 P，成立则继续执行 A，否则退出。

C（C++）语言控制语句

复合语句 ：用 “{” 和 “}” 括起来的多条语句组成的可执行单元，可出现在任何能出现语句的地方。
if 和 switch 语句 ：
- if 语句 ：实现双分支选择结构，一般形式为 if(表达式) 语句 1; else 语句 2; 语句 2 可省略简化，意 if 和 else 的匹配关系。
- switch 语句 ：描述多分支选择结构，根据表达式值与常量表达式匹配执行相应语句序列。表达式可为任何型，常用字符型或整型。无匹配时执行 default 语句序列。case 语句序列中无 break 时，程序会继续执行下一个 case 的代码直到 break 或者结束，而不是终止 switch 语句的执行。这种现象称为 case 穿透。
循环语句 ：
- while 语句 ：先判断条件表达式，非零则执行循环体语句，多条语句需用 “{” 和 “}” 括起来。
- do - while 语句 ：先执行循环体语句，再判断条件表达式，非零则重复执行。
- for 语句 ：基本形式为 for(表达式 1; 表达式 2; 表达式 3) 循环体语句。
其他控制流语句 ：C 语言提供 goto、break 和 continue 语句实现控制流跳转，但 goto 不提倡使用。

1.2.4 程序设计语言的传输部分

程序设计语言的传输成分

程序设计语言的传输成分指明语言允许的数据传输方式，主要包括赋值处理、数据的输入和输出等。

1.2.5 函数

1.2.5.1 函数定义

函数由函数首部和函数体组成。函数首部包括函数的返回值类型、函数名和参数列表及类型。函数体描述了函数实现的功能。函数定义形式如下：

返回值类型 函数名（形式参数表） //函数首部
{
    函数体；
}

1.2.5.2 函数声明

函数声明用于告知编译器函数的参数及返回值类型。如果函数调用在函数定义之前，则必须先声明函数。函数声明形式如下：

1	返回值类型函数名（参数类型表）；

1.2.5.3 函数调用

函数调用时，调用函数通过函数名和参数来使用被调函数的功能。在函数体中调用自身称为递归调用。

参数传递方式

值调用（Call by Value）：将实参的值传递给形参。形参不能向实参传递信息。
引用调用（Call by Reference）：引用是 C++ 引入的概念。形参是实参的别名，对形参的修改就是对实参的修改。

2 语言处理程序基础

2.1 汇编程序基本原理

2.2.1 汇编语言

汇编语言是为特定的计算机设计的面向机器的符号化的程序设计语言。用汇编语言编写的
程序称为汇编语言源程序。要用专门的翻译程序——汇编程序进行翻译。

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

2.2.2 汇编程序

汇编程序一般需要两次扫描源程序才能完成翻译过程。

第一次扫描的主要工作是定义符号的值并创建一个符号表ST，还需要对与定义符号值有关的伪指令进行处理。
第二次扫描的任务是产生目标程序。

2.2 编译程序基本原理

2.2.1 编译过程概述

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机
器语言)。编译程序的工作过程可以分为6个阶段，在实际的编译器中可能会将其中的某些阶段结合在一起进行处理。

词法分析：对源程序从前到后（从左到右）逐个字符地扫描。词法分析程序输出的“单词”常以二元组的方式输出，即单词种别和单词白身的值。
语法分析：根据语言的语法规则将单词符号序列分解成各类语法单位，确定整个输入串是否构成一个语法上正确的程序。注：上下文无关
语义分析：分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。注：要结合上下文
中间代码生成：根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。
代码优化
目标代码生成：把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。

2.2.2 文法和语言的形式描述

1. 字母表、字符串、字符串集合及运算

字母表 Σ 和字符：字母表是字符的非空有穷集合，字符是字母表中的元素。例如，Σ = {a, b}，a 或 b 是字符。
字符串：由 Σ 中的字符组成的有穷序列。例如，a、ab、aaa 都是 Σ 上的字符串。
字符串的长度：字符串中的字符个数。如 |aba| = 3。
空串 ε：由零个字符组成的序列，|ε| = 0。
连接：字符串 S 和 T 的连接是将 T 接续在 S 之后，表示为 S·T，连接符号“·”可省略。对于字母表 Σ 上的任意字符串 S，S·ε = ε·S = S。
Σ*：包括空串 ε 在内的 Σ 上所有字符串的集合。例如，设 Σ = {a, b}，Σ* = {ε, a, b, aa, bb, ab, ba, aaa, …}。
字符串的方幂：把字符串 α 自身连接 n 次得到的串，称为字符串 α 的 n 次方幂，记为 αⁿ。α⁰ = ε，αⁿ = ααⁿ⁻¹ = αⁿ⁻¹α（n > 0）。
字符串集合的运算：设 A、B 代表字母表 Σ 上的两个字符串集合。
- 或（合并）：A ∪ B = {α | α ∈ A 或 α ∈ B}。
- 积（连接）：AB = {αβ | α ∈ A 且 β ∈ B}。
- 幂：Aⁿ = A·Aⁿ⁻¹ = Aⁿ⁻¹·A（n > 0），并规定 A⁰ = {ε}。
- 正则闭包：A⁺ = A¹ ∪ A² ∪ A³ ∪ … ∪ Aⁿ ∪ … 。
- 闭包：A* = A⁰ ∪ A⁺。显然，Σ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ … ∪ Σⁿ ∪ … 。

2. 文法和语言的形式描述

文法的定义

语言是一种规则生成的字符串集合。文法是描述语言语法结构的规则，乔姆斯基将文法分为四型：0 型、1 型、2 型、3 型。文法 G 由四元组表示：(G=(V_N, V_T, P, S))，其中：

$V_T$ 是终结符集合， $V_N$ 是非终结符集合，且 $V_N \cap V_T = \emptyset$ 。 $V = V_N \cup V_T$ 是词汇表。
$P$ 是产生式规则集合，形式为 $\alpha \rightarrow \beta$ ，其中 $\alpha \in V^*\$ 且至少含一个非终结符，$ \beta \in V^*$。
$S \in V_N$ 是开始符号，至少出现在一条产生式的左部。

文法的分类

0型文法：产生式 $\alpha \rightarrow \beta$ 中， $\alpha$ 至少含一个非终结符， $\beta$ 是任何字符串。等价于图灵机，描述递归可枚举语言。
1型文法（上下文有关文法）：除 $S \rightarrow \epsilon$ 外，产生式 $\alpha \rightarrow \beta$ 满足 $|\alpha| \leq |\beta|$ 。等价于线性有界自动机，描述上下文有关语言。
2型文法（上下文无关文法）：产生式形如 $A \rightarrow \beta$ ，其中 $A \in V_N$ ， $\beta \in (V_N \cup V_T)^*$ 。等价于下推自动机，描述上下文无关语言。
3型文法（正规文法或线性文法）：产生式形如 $A \rightarrow a$ 或 $A \rightarrow aB$ （或 $A \rightarrow Ba$ ），其中 $A, B \in V_N$ ， $a \in V_T$ 。等价于有限自动机，描述正规语言。

3. 句子和语言的形式描述

推导：从文法开始符号 S 出发，用产生式替换非终结符，直到得到终结符序列。
直接推导：若产生式 $\alpha \rightarrow \beta$ 存在，则 $\gamma \alpha \delta$ 可直接推导出 $\gamma \beta \delta$ 。
句型：从 S 推导出的符号串。
句子：仅含终结符的句型。
语言 $L(G)$ ：文法 G 产生的所有句子的集合。
文法的等价：若两个文法产生的语言相同，则它们等价。

2.2.3 词法分析

词法分析的任务是将源程序字符串转换为单词符号序列，包括标识符、常数、运算符和界限符等。

1. 正规表达式和正规集

正规表达式是描述词法规则的工具，使用 3 型文法或正规文法。
基本定义：
- $\varepsilon$ 表示空串集合。
- 字符 $a$ 表示集合 $\{a\}$ 。
- 运算规则：
  - $r|s$ 表示 $L(r) \cup L(s)$ 。
  - $r \cdot s$ 表示 $L(r)L(s)$ ，连接运算符可省略。
  - $r^*$ 表示 $(L(r))^*$ ，闭包运算。
  - $(r)$ 表示 (L®)，用于改变运算优先级。
正规表达式示例：
- $ab$ ：字符串 $ab$ 的集合。
- $a|b$ ：字符串 $a$ 或 $b$ 的集合。
- $a^*$ ：0 个或多个 $a$ 的集合。
- $(a|b)^*$ ：所有由 $a$ 和 $b$ 构成的字符串。
- $a(a|b)^*$ ：以 $a$ 开头的字符串。
- $(a|b)^* abb$ ：以 $abb$ 结尾的字符串。

2. 有限自动机

有限自动机是识别正规集的抽象装置，分为确定的有限自动机（DFA）和不确定的有限自动机（NFA）。

确定的有限自动机（DFA）

DFA 是五元组 $(S, \Sigma, f, s_0, Z)$ ，其中：

$S$ ：有限状态集。
$\Sigma$ ：有穷输入字母表。
$f$ ：状态转移函数， $f: S \times \Sigma \to S$ 。
$s_0$ ：唯一初态。
$Z$ ：非空终态集。

表示方式

状态转换图：结点表示状态，有向弧表示转换，标记为输入字符。
状态转换矩阵：行表示状态，列表示输入字符，单元格表示下一状态。

识别语言：若存在从初态到终态的路径，且路径上的输入字符组成字符串 $\omega$ ，则 $\omega$ 被识别。DFA 能识别的语言是正规的。

不确定的有限自动机（NFA）

NFA 也是五元组 ((S, \Sigma, f, s_0, Z))，与 DFA 的区别：

状态转移函数 $f: S \times \Sigma \to 2^S$ ，即输入字符可导致多个下一状态。
允许 $\varepsilon$ 转换，即无输入字符的状态转换。

2.2.4 正规式与有限自动机之间的转换

1. 有限自动机转换为正规式(参见教材 30 页的图)
2. 正规式转换为有限自动机(参见教材 30 页的图)

2.2.5 词法分析器构造

基于正规式和有限自动机的理论基础。构造词法分析器的步骤如下：

使用正规式描述单词规则。
为每个正规式构造 NFA。
将 NFA 转换为等价的 DFA。
对 DFA 进行最小化处理。
基于最小化 DFA 构造词法分析器。

2.2.6 语法分析

任务：依据语法规则分析单词串是否构成有效短语或句子，同时处理语法错误。
方法分类：
- 自顶向下分析：从根节点开始尝试构造语法树。
- 自底向上分析：从输入单词串开始，逐步向上归约以构造语法树。

2.2.7 语法制导翻译和中间代码生成

语义分析：程序设计语言的语义分为静态语义和动态语义。静态语义分析主要通过语法制导翻译进行。
语法制导翻译：将语言结构的语义以属性的形式赋予文法符号，属性的计算以语义规则的形式赋予文法产生式。在语法分析的推导或归约步骤中，执行语义规则以计算属性，实现语义处理。

2.2.8 中间代码优化和目标代码生成

中间代码优化

目标：对程序进行等价变换，生成更有效的目标代码。等价指不改变程序运行结果，有效指目标代码运行时间短、占用存储空间少。
阶段：主要在目标代码生成前进行，不依赖具体计算机。

目标代码生成

代码生成器：将中间代码转换为特定机器语言或汇编代码。
中间代码形式：常用四元式。
目标代码形式：绝对机器指令代码和可再定位机器代码。
寄存器分配：合理分配寄存器以提升效率。
计算次序选择：优化计算次序以提高代码效率。

2.3 解释程序基本原理

解释程序通常可以分成两部分：第一部分是分析部分，包括通常的词法分析、语法分析和语义分析程序，经语义分析后把源程序翻译成中间代码，中间代码常采用逆波兰表示形式。第二部分是解释部分，用来对第一部分产生的中间代码进行解释执行。

2.3.1 解释程序的基本结构

可能会用到栈这种数据结构。

2.3.2 高级语言编译与解释方式的比较

（1）效率。编译比解释方式可能取得更高的效率。
（2）灵活性。由于解释程序需要反复检查源程序，这也使得解释方式比编译方式更灵活。
（3）可移植性。一般只要对解释器进行重新编译，就可以使解释器运行在不同的环境中。因此解释方式移植性更好。

3 加餐和总结

前缀表达式根左右
中缀表达式左根右
后缀表达式左右根