软考笔记——程序设计语言基础知识

第二章节——程序设计语言基础知识

一、程序设计语言概述

1. 程序设计语言的基本概念

程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。

• 低级语言： 机器语言（0，1）、汇编语言
• 高级语言： 功能更强，抽象级别更高，与人们使用的自然语言比较接近。

各程序设计语言特点：

• ①Fortran语言（科学计算，执行效率高）
• ②Pascal语言（为教学而开发，表达能力强)
• ③C语言（指针操作能力强，且高效)
• ④C++语言（面向对象，且高效)
• ⑤Java语言(面向对象，中间代码，跨平台）
• ⑥CH语言（面向对象，中间代码，.NET)
• ⑦Python语言（面向对象，脚本语言，解释型语言)
• ⑧JavaScript语言（脚本语言，广泛用于Web开发)

2. 程序设计语言的基本成分

(1) 数据成分： 指一种程序设计语言的数据和数据类型。数据分为常量、变量、全局量、局部量。数据类型有整形、字符型、单精度浮点型，双精度浮点型、布尔型、枚举型。
(2) 运算成分： 指明运行使用的运算符及运算规则。包括算数运算，逻辑运算，关系运算，位运算。
(3) 控制成分： 指明语言允许表述的控制结构。包括顺序结构，选择结构，循环结构。
(4) 传输成分： 指明语言允许的数据传输方式。如赋值处理，数据的传入传出等。
(5) 函数： 是一段具有处理独立功能的代码块。函数使用涉及三个概念:函数定义、函数声明(先声明再使用）、函数调用。

• 函数定义：

返回值类型 函数名(形参...){
	函数体;
}

• 函数声明:返回值类型函数名(参数类型…)
• 函数调用:函数名(实参…)

函数调用的两种方式：

• 传值调用: 将实参的值传递给形参，形参的改变不会导致实参的改变。实参可以是合法的变量、常量或表达式。
• 引用调用: 即传地址调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此形参的值改变的同时，实参的值也跟着改变。实参不能为常量，只能是合法的变量和表达式。

二、语言处理程序基础

1. 汇编程序基本原理

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。
汇编程序将汇编语言所编写的源程序翻译成机器指令程序。汇编程序一般需要两次扫描源程序才能完成翻译过程。

• 第一次扫描:检查语法错误，确定符号名字;建立符号表
• 第二次扫描:产生目标程序。

2. 编译程序基本原理

2.1 编译程序概述

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言和机器语言）。编译程序工作过程分为六个阶段，如下图

(1) 词法分许： 这个阶段的任务是从左到右一个字符一个字符地扫描源程序，从而识别出一个个单词符号
(2) 语法分许： 语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如"程序"，“语句”，“表达式”等。语法分析程序判断源程序在结构上是否正确。
(3) 语义分许： 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查和类型审查。如类型匹配、除数不为0等。又分为静态语义错误（在编译阶段能够查找出来）和云态语义错误（只能在运行时发现）。

(4) 中间代码生成（非必须): 中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理，有助于提高可移植性。常用的中间代码有后缀式（逆波兰式)、三元式（三地址码)、四元式、树和图等形式。
(5) 代码优化（非必须): 当需要生成高效的目标代码时，就进行优化。所依据的原则是程序的等价变换原则。
(6) 目标代码生成: 把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。需要考虑三个问题（一是如何生成较短的目标代码;二是如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数;三是如何充分利用计算机指令系统的特点，以提高目标代码的质量)。

中间代码生成的后缀式:

• 掌握以上三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出一棵树，再按题目要求求出前缀表达式和后缀表达式。
• 后缀式即逆波兰式，是逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+。这种表示法的优点是根据运算对象和运算符的出现次序进行计算，不需要使用括号。
• 后缀式简单求法：按运算的优先顺序依次将运算符写在运算对象的后面，例如，把写成a+b写成ab+。

2.2 文法

描述语言语法结构规则规则成为文法（就是将我们写的代码翻译为目标程序的过程，规定一个规则，这个规则就是文法）。一个形式文法是一个有序四元组G=(V_N，V_T，P，S)，其中：

• V_N：非终结符集合。不是语言组成部分，不是最终结果，可理解为占位符。
• V_T：终结符集合。是语言的组成部分，是最终结果。V_N $\bigcap$ V_T= $\varnothing$
• P：产生式集合。形如$\alpha$ =>$\beta$。用非终结符推到出终结符的规则。
• S：起始符。是语言开始符号
• 终结符:最终结果，不能推导出其他元素。
• 非终结符:能够推导出其他元素。
• 产生式:即非终结符推导出终结符的公式。
• 正则闭包：A⁺ = A¹$\cup$ A²$\cup$ A³$\cup$···$\cup$Aⁿ$\cup$···(所有幂的组合)
• 闭包：A^* = A⁰$\cup$A⁺ (在正则闭包的基础上，加上A⁰={$\epsilon$})

文法的分类：

程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述。

正规表达式：
用于词法分析，对于字母表E，其上的正规式及其表示的正规集可以递归定义如下:
(1) $\epsilon$是一个正规式，它表示集合L($\epsilon$)={$\epsilon$}。
(2）若a是$\sum$上的字符，则a是一个正规式，它所表示的正规集为{a}。
(3）若正规式r和s分别表示正规集L(r )和L(s)，则:
①r | s是正规式，表示集合L(r )U L(s)。
②r · s是正规式，表示集合L(r )L(s)。
③r^*是正规式，表示集合(L(r ))^*。
④(r )是正规式，表示集合L(r )。
仅由有限次地使用上述三个步骤定义的表达式才是E上的正规式。

正规式和正规集示例：
设$\sum$= {a, b}，如下列出了2上的一些正规式和相应的正规集。

有限自动机：
(1）确定的有限自动机（DFA）：
是词法分析的工具，一个确定的有限自动机DFA是一个五元组M=(S,$\sum$, f,S₀,Z)，其中:
①S是一个有限集，其每个元素称为一个状态。
②$\sum$是一个有穷字母表，其每个元素称为一个输入字符。
③f是状态转换函数，为S×$\sum$上的单值部分映像。f(A,a)=Q表示当前状态为A、输入为a时，将转换到下一个状态Q，称Q为A的一个后继状态。
④S₀∈ S，是唯一的一个开始状态。
⑤z是非空的终止状态集合，其中Z$\subseteq$S。
有限自动机可以形象地用状态转换图表示，设有限自动机；
DFA =({S₀,S₁,S₂,S₃，{a，b}， f ，S₀，{S₃})
其中f为: f(S₀,a) =S₁, f(S₀,b) = S₂,f(S1,a) = S₃, f(S₁,b)= S₂,f(S₂,a) = S₁,f(S₂,b) = S₃. f(S₃,a) = S₃
由S₀输入一个a，可得出S₁，输入一个b，可得出S₂,以此类推。一般在考试中，会给出一个状态转换图，问能否构造出abb这样的字符串，解决方法就是从起始状态S₀到终止状态S3之间是否有一条路，权值为abb。本质就是有向图从起点到终点的遍历。

(2）不确定的有限自动机（NFA）：
是词法分析的工具，一个不确定的有限自动机NFA是一个五元组M= (S,$\sum$, f ,S₀,Z)，
其中:
①S是一个有限集，其每个元素称为一个状态。
②$\sum$是一个有穷字母表，其每个元素称为一个输入字符。
③f是状态转换函数，为S × $\sum$上的多值部分映像。f(A,a)=Q或f(A,a)= W表示当前状态为A、输入为a时，将转换到下一个状态Q或W，即给定一个状态和输入符号，其后继状态可能有多个。
④S₀ $\in$ S，是非空初态集。
⑤Z是可空的终止状态集合。

DFA是NFA的特例;对于每一个NFA，都可以转换为DFA。
如何分辨确定的有限自动机和不确定的有限自动机:输入一个字符，看是否能得出唯一的后继，若能，则是确定的有限自动机，否则就是不确定的有限自动机。

（3）DFA和NFA的区别：

（4） 正规式与有限自动机之间的转换：

(5) 语法分析方法：

• 自上而下语法分析法:最左推导，从左至右。给定文法G和源程序串r，从G的开始符号S出发，通过反复使用产生式P对句型中的非终结符进行替换（推导），逐步推导出r。
• 递归下降分析法:原理是利用函数之间的递归调用，模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法。
• 自下而上语法分析法:最右推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替（归约）之，逐步归约到开始符号S。
• 移进-归约分析法:设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式P的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部推导出左部，因此是自下而上语法分析的核心思想。

3.解释程序基本原理

解释和编译，都是将高级程序语言翻译成计算机硬件认可的机器语言加以执行。