数据库系统工程师——第二章 程序语言基础知识

📂 第二章、程序语言基础知识

📁 2.1 程序语言概述

低级语言和高级语言：

低级语言：
包括机器语言和汇编语言，是一种面向机器的语言，效率低、程序可读性很差、难以理解、难以修改和维护。

高级语言：
面向各类应用的程序语言，功能更强、抽象级别更高，常见的有Java、C、C++、C#、Python、PHP、JavaScript等，这类语言与人们使用的自然语言比较接近，大大提高了程序设计的效率。

汇编、解释、编译：

高级程序语言必须进行翻译才能为计算机硬件所理解，语言之间的翻译形式有多种，基本方式为汇编、解释和编译。
用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。
如果源程序是用汇编语言编写的，则需要一个汇编程序将其翻译成目标程序后才能执行。
如果源程序是用某种高级语言编写的，则需要对应的解释程序或编译程序对其进行翻译，然后在机器上运行。

编译程序和解释程序：

解释程序（解释器）： 要么直接解释执行源程序，要么将源程序翻译成某种中间代码后再加以执行。它按源程序中语句的执行顺序，逐条翻译并立即执行相关功能。
编译程序（编译器）： 将源程序翻译成目标程序（目标代码），然后再在计算机上运行目标程序。

一般分为两个阶段：
编译阶段：把源程序翻译成目标程序。
运行阶段：执行目标程序。

区别（常考 ⭐ ⭐ ⭐）：

a)	编译方式下:机器上运行的是与源程序等价的目标程序，源程序与编译程序都不再参与目标程序的执行过程；
b)	解释方式下:解释程序与源程序（或者某种等价表示）要参与到程序的运行过程中，运行程序的控制权在解释程序。
c)	解释方式下:翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立保存的目标程序。编译和解释的比较：编译比解释方式可能取得更高的效率，用户程序运行的速度更快；解释方式比编译方式更灵活（解释程序需要反复检查源程序）；解释方式可移植性好。

Tips：

反编译是编译的逆过程。反编译通常不能把可执行文件还原成高级语言源代码，只能转换成功能上等价的汇编程序。

📖 2.1.1 程序语言的基本概念

若一种程序语言不依赖于机器硬件，则称为高级语言；若程序语言能够应用于范围广泛的问题求解领域，则称为通用的程序设计语言。

a) PHP 是一种在服务器端执行的、嵌入HTML文档的脚本语言，PHP可以快速地执行动态网页。
b) Python 是一种面向对象的解释型程序设计语言，可以用于编写独立程序、快速脚本和复杂应用的原型。
c) JavaScript 是一种基于对象、事件驱动编程的客户端动态脚本语言，被广泛用于web应用开发，常用来网页添加各式各样的动态功能，为用户提供更流畅美观的浏览效果，通常嵌入HTML使用。
d）Ruby 是一种开源的面向对象程序设计的服务器端动态脚本语言。脚本语言是为了缩短传统的编写-编译-链接-运行过程而创建的计算机编程语言。
此命名起源于一个脚本“screenplay”，每次运行都会使对话框逐字重复。早期的脚本语言经常成为批处理语言或工作控制语言。
一个脚本通常是解释运行而非编译。

📖 2.1.2 程序语言的基本成分

⭐ ⭐ ⭐

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

程序语言的数据成分：

常量和变量： 变量具有左值（指存储单元：地址、容器）和右值（内容），在程序运行过程中其右值可以改变；常量只有右值，在程序运行过程中其右值不能改变。
全局变量和局部变量： 系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的，而为局部变量分配的存储单元是可以动态改变的。
按照数据组织形式的不同分为基本类型、用户定义类型、构造类型及其他类型，以C语言为例：
– 基本类型：int、char、float、double、bool等；
– 特殊类型：void；
– 用户定义类型：enum（枚举类型）；
– 构造类型：数组、结构、联合；
– 指针类型：type *;
– 抽象数据类型：类类型。

程序语言的控制成分： 顺序结构、选择结构、循环结构。

a）顺序结构计算过程从所描述的第一个操作开始，按顺序依次执行后续的操作，直到序列的最后一个操作。
b）选择结构选择结构提供了在两种或多种分支中选择其中一个的逻辑。（if else）。
c）循环结构循环结构描述了重复计算的过程，通常由三部分组成：初始化、循环体和循环条件(while )。

函数（ ⭐ ⭐ ⭐）：

函数涉及3个概念： 函数定义、函数声明和函数调用。

函数是一段具有独立功能的程序代码。
a）函数定义
C/C++程序中所有函数的定义都是独立的。不允许函数的嵌套定义。
b）函数声明
先声明后引用
c）函数调用 
函数调用时基本的参数传递方式有两种：传值调用和引用调用。

调用函数和被调用函数之间交换信息的方法主要有2种：

一种是被调用函数把返回值返回给主调函数，
另一种是通过参数带回信息，函数调用实参与形参间交换信息的方法有值调用和引用调用：
1、传值调用： 实现函数调用时实参向形式参数传递相应类型的值，形参不能向实参传递信息 （单向传递） ，实参可以是常量（表达式），也可以是变量（数组元素），例如：

int sum(int x, int y){
int z;
Z=x+y;
return z;
### 函数调用时: sum(2,3);

2、引用调用（传地址调用）：
引用是C++中增加的数据类型，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实际参数所做的访问和改变，可以实现双向传递；因此只能是变量（数组元素），而不能是常量（表达式），例如：

void swap(int &x,int &y){
int temp;
temp=x; x=y; y=temp ;
### 函数调用: swap(a,b);x，y就是a，b的别名，调用完成后，交换了a，b的值。

Tips： 函数调用和返回控制是用 栈 实现的。

📁 2.2 程序语言翻译基础

📖 2.2.1 汇编程序基本原理

汇编语言源程序有3类语句：指令语句、伪指令语句和宏指令语句。

汇编程序的功能是将汇编语言所编写的源程序翻译成机器指令程序，汇编程序的基本工作包括每一条可执行汇编语句转换成对应的机器指令，处理源程序中出现的伪指令。
由于汇编指令中形成操作数地址的部分可能出现后面才会有定义的符号，所以汇编程序一般需要两次扫描源程序才能完成翻译过程。

📖 2.2.2 编译程序基本原理

编译程序的作用是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言），编译程序工作过程一般分为6个阶段：

词法分析：

词法分析阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号，“单词”符号是程序设计语言的基本语法单位，如关键字或保留字、标识符、常数、运算符和分隔符（如标点符号、左右括号）等。
  
语法分析：

语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”和“程序”等，检查和处理程序中的语法错误，如果源程序中没有语法错误，语法分析后就能正确地构造出其语法树，否则就指出语法错误，并给出相应的诊断信息。
  
语法分析方法有多种，根据产生语法树的方向，可分为 自底向上(或自下而上) 和 自顶向下（或自上而下） 两类。
  
语义分析：

语义分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用，只有语法和语义都正确的源程序才能翻译成正确的目标代码。

语义分析的一个主要工作是 进行类型分析和检查 ，程序语言中的一个数据类型一般包含两个方面的内容：类型的载体及其上的运算。
例如，整除取余运算符只能对整型数据进行运算，若其运算对象中有浮点数就认为是一种类型不匹配的错误。

中间代码生成：

中间代码生成阶段的工作是根据语义分析的输出生成中间代码。常用的中间代码有：后缀式（逆波兰式）、四元式（三地址码）、树形。
  
中缀式表达式：

即通常所使用的表达式，如

( a + b ) ∗ c − d (a+b)*c-d(a+b)∗c−d;
( a + b ) ∗ d 

后缀表达式转为中缀表达式：
从左至右扫描后缀表达式，若遇到运算对象，则压入栈中，遇到运算符，则从栈中弹出栈顶的两个运算对象进行运算，并将运算结果压入栈中，重复以上过程，直到表达式最右端，结束。

前缀表达式转为中缀表达式：
从右至左扫描后缀表达式，若遇到运算对象，则压入栈中，遇到运算符，则从栈中弹出栈顶的两个运算对象进行运算，并将运算结果压入栈中，重复以上过程，直到表达式最左端，结束。

前缀式表达式（波兰式）：

将运算符在运算对象的前面，(a + b) ∗c−d (a+b)c-d(a+b)∗c−d后缀表达式为− ∗+ a b c d -+abcd−∗+abcd，即中缀表达式转换为前缀表达式，步骤：

a)	按计算顺序全部加上括号：( ( ( a + b ) ∗ c ) − d ) (((a+b)*c)-d)(((a+b)∗c)−d)；
b)	把每一对括号内的运算符移到括号前面：−(∗( + ( a b ) c ) d ) -(*(+(ab)c)d)−(∗(+(ab)c)d)；
c)	去掉括号：−∗+ a b c d -*+abcd−∗+abcd。

后缀式表达式（逆波兰式）：

将运算符写在运算对象的后面，这种表示法的优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号，也便于用栈实现求值，( a + b ) ∗ c − d (a+b)c-d(a+b)∗c−d后缀表达式为a b + c ∗ d − ab+cd-ab+c∗d−，即中缀表达式转换为后缀表达式，步骤：

a）按计算顺序全部加上括号：( ( ( a + b )∗c )−d ) (((a+b)*c)-d)(((a+b)∗c)−d)；
b）把每一对括号内的运算符移到括号后面：( ( ( ( a b ) + c )∗d )−((((ab)+c)*d)-((((ab)+c)∗d)−；
c）去掉括号：a b + c∗d − ab+c*d-ab+c∗d−。

代码优化：

由于编译器将源程序翻译成中间代码的工作时机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间方面的效率较差，当需要生成高效的目标代码时，就必须进行优化。
优化代码可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。

目标代码生成：

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

符号表管理：

符号表的作用是记录源程序中各符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。

出错处理：

源程序中不可避免地会有一些错误，这些错误大致分为静态错误和动态错误。
动态错误发生在程序运行时，如：变量取零时作除数、引用数组元素下标错误等。
静态错误是指编译阶段发生的程序错误，可分为语法错误和静态语义错误，如单词拼写错误、标点符号错、表达式中缺少操作数、括号不匹配等有关语言结构上的错误成为语法错误。
静态语义错误是指语义分析时发现的运算符与运算对象类型不合法等错误。

📖 2.2.3 解释程序基本原理

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

💯第二章 程序语言基础知识（经典例题）

22、（2021年上）在程序编译过程中，执行类型分析和检查是在（ ）阶段。

A.词法分析
B.语法分析
C.语义分析
D.代码优化

参考答案：C
试题解析： 在程序编译过程中，执行类型分析和检查是语义分析阶段的工作。

20、（2020年上）程序设计语言的基本成分包括数据、运算、控制和（ ）。 数据是程序操作的对象，按照数据组织形式可以分为多种类型，其中枚举属于（ ）类型；数组属于（ ）类型。

问题1
A.存储
B.分配
C.传输
D.函数

问题2
A.基本
B.用户定义
C.构造
D.特殊

问题3
A.基本
B.用户定义
C.构造
D.特殊

参考答案：C、B、C
试题解析： 程序设计语言的基本成分包括数据、运算、控制和传输，数据是程序操作的对象，按照数据组织形式可以分为多种类型，其中枚举属于用户定义类型， 数组属于构造类型。

20、（2019年上）以下关于编译和解释的叙述中，正确的为（ ）。
① 编译是将高级语言源代码转换成目标代码的过程
② 解释是将高级语言源代码转换为目标代码的过程
③ 在编译方式下，用户程序运行的速度更快
④ 在解释方式下，用户程序运行的速度更快

参考答案：A
试题解析：两种语言处理程序的根本区别是：在编译方式下，机器上运行的是与源码程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程，程序运行速度快；而在解释方式下，解释程序和源程序（或其某种等价表示）要参与到程序的运行过程中，运行程序的控制权在解释程序，边解释边执行，程序运行速度慢。

22、（2019年上）函数调用和返回控制是用（ ）实现的。

A.哈希表
B.符号表
C.栈
D.优先队列

参考答案：C
试题解析： 函数调用和返回控制是用栈实现的，而哈希表、符号表和优先队列是跟函数调用和返回控制是没有任何关系，属于干扰选项。

23、（2019年上）通用的高级程序设计语言一般都会提供描述数据、运算、控制和数据传输的语言成分，其中，控制包括顺序、（ ）和循环结构。

A.选择
B.递归
C.递推
D.函数

参考答案：A
试题解析： 程序设计语言的基本成分包括数据、运算、控制和传输等。
程序设计语言的控制成分包括顺序、选择和循环3种结构。
所以本题选择A选项。

4、（2018年上）算术表达式采用后缀式表示时不需要使用括号，使用（ ）就可以方便地进行求值。a－b（c＋d）（其中，-、＋、*表示二元算术运算减、加、乘）的后缀式为（ ），与该表达式等价的语法树为（ ）。

问题1
A.队列
B.数组
C.栈
D.广义表

问题2
A.a b c d -+
B.a b c d+ -
C.ab-cd+
D.a b c d+-

问题3

参考答案：C、D、D
试题解析： 直接用算术运算符的优先级解题，后缀式用括号法。

18、（2018年上）在下列机制中，（ ）是指过程调用和响应调用所需执行的代码在运行时加以结合；而（ ）是过程调用和响应调用所需执行在编译时加以结合。

问题1
A.消息传递
B.类型检查
C.静态绑定
D.动态绑定

问题2
A.消息传递
B.类型检查
C.静态绑定
D.动态绑定

参考答案：D、C
试题解析： 程序运行过程中，把函数（或过程）调用与响应调用所需要的代码相结合的过程称为动态绑定。静态绑定是指序编译过程中，把函数（方法或者过程）调用与响应调用所需的代码结合的过程称之为静态绑定。

2、（2017年上）要判断字长为16 位的整数 a 的低四位是否全为 0，则（ ）

A.将 a 与 0x000F 进行"逻辑与"运算，然后判断运算结果是否等于 0
B.将 a 与上一题 0x000F 进行查看答案与解析 "逻辑或"运算，然后判断运算结果是否等于 F
C.将 a 与 0xFFF0 进行"逻辑异或"运算，然后判断运算结果是否等于0
D.将 a 与 0xFFF0 进行"逻辑与"运算，然后判断运算结果是否等于 F

参考答案：A
试题解析：
要判断数的最后四位是否都为0，应该将最后四位与1进行逻辑与运算，其他数位与0做逻辑与运算，最后判定的结果是否为0；因此得出与a进行逻辑与运算的数：前12位为0最后4位为1，即0x000F
逻辑或运算：0 或 0 = 0；1 或 0 = 1；0 或 1 = 1；1 或 1 = 1；
逻辑与运算：0 与 0 = 0；1 与 0 = 0；0 与 1 = 0；1 与 1 = 1；

18、（2017年上）在高级语言源程序中，常需要用户定义的标识符为程序中的对象命名，常见的命名对象有（ ）。
①关键字（或 保留字） ②变量 ③函数 ④ 数据类型 ⑤注释

A.①②③
B.②③④
C.①③⑤
D.②④⑤

参考答案：B
试题解析：在编写程序时需要命名的对象有变量，函数，数据类型。

19、（2017年上）在仅由字符a、b 构成的所有字符串中，其中以 b 结尾的字符串集合可用正规式表示为（ ）。

A.(b|ab)b
B.(ab)b
C.ab*b
D.(a|b)*b

参考答案：D
试题解析： 正规式(a|b)*对应的正规集为{ε，a，b，aa，ab，…，所有由a和b组成的字符串}，结尾为b。

20、（2017年上）在以阶段划分的编译中，判断程序语句的形式是否正确属于（ ）阶段的工作。
A.词法分析
B.语法分析
C.语义分析
D.代码生成

参考答案：B
试题解析：
词法分析阶段：
是编译过程的第一阶段，其任务是对源程序从前到后（从左到右）逐个字符扫描，从中识别出一个个“单词”符词法分析过程的依据是语言的词法规则，即描述“单词”结构的规则。
语法分析阶段：
其任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位。
通常语法分析是确定整个输入串是否构成一个语法上正确的程序。
一般来说，通过编译的程序，不存在语法上的错误。
语义分析阶段：
其任务主要检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。
语义分析的一个主要工作是进行类型分析和检查。
中间代码生成：
其任务是根据语义分析的输出生成中间代码。
目标代码生成：
是编译器工作的最后一个阶段。其任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码编指令代码。本阶段与具体机器密切相关。