八、程序语言设计基础

8.1 程序设计语言概述

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

低级语言：机器语言（计算机硬件只能识别0和1的指令序列），汇编语言

高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近

• 各程序设计语言的特点

Fortran语言：科学计算，执行效率高

Pascal语言：为教学开发，表达能力强

C语言：指针操作能力强，可以开发系统级软件，高效

C++语言：面向对象，高效

Java语言：面向对象，中间代码，跨平台

C#语言：面向对象，中间代码，.Net框架

Python是一种面向对象、解释型计算机程序设计语言

Prolog是逻辑型程序设计语言

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

汇编：将汇编语言翻译成目标程序执行

解释和编译：将高级语言翻译成目标程序执行。不同之处在于编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。而解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢、效率低。

程序设计语言定义的三要素：语法、语义、语用

语法：是指由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号构成语法成分的规则称为语法规则

语义：是程序设计语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。静态语义指编译时可以确定语法成分的含义，而运行时刻才能确定的含义是动态语义。一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。

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

• 语言的实现有个语境问题。语境是指理解和实现程序设计语言的环境，包括编译环境和运行环境

程序设计语言的分类：

1）命令式和结构化程序设计语言：Fortan、Pascal、C

2）面向对象的程序设计语言：C++、Java、SmallTalk

3）函数式程序设计语言：LISP、Haskell、Scala、Scheme、APL等

4）逻辑型程序设计语言：Prolog

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

1. 数据成分：是指一种程序设计语言的数据和数据类型。数据分为常量（程序运行时不可改变）、变量（程序运行时可以改变）、全局量（存储空间在静态数据区分配）、局部量（存储空间在堆栈区分配）。数据类型有整型、字符型、双精度、单精度浮点型、布尔型等

2. 运算成分：指明允许使用的运算符号及运算规则。包括算术运算、逻辑运算、关系运算、位运算等

3. 控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构

4. 传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等

5. 函数：C语言由一个或多个函数组成，每个函数都有一个名字，其中有且仅有一个名为main的函数作为程序运行时的起点。函数的使用设计3个概念：函数的定义、函数声明、函数调用

8.2 语言处理程序基础

8.2.1 编译程序基本原理

编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征信息，并将其存入符号表中，编译过程如下：

1. 词法分析：编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词（也称单词符号或符号）

2. 语法分析：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确

3. 语义分析：是编译过程的一个逻辑阶段。语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。如类型匹配、除法除数不为0。又分为静态语义错误和动态语义错误

4. 中间代码生成

5. 代码优化

6. 目标代码生成

中间代码和目标代码：中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关代码优化处理。常用中间代码有后缀式（逆波兰式）、三元式、四元式和树等形式。需要考虑三个问题（一、如何生产较短的目标代码；二、如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；三、如何充分利用计算机指令系统的特点，以提高目标代码质量）。

一般正常的表达式是中序遍历

• 简单求法：后缀表达式是从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面

8.2.2 文法定义

1）字母表、字符串、字符串及集合

• 字母表Σ和字符：字母表是字符的非空有穷集合，字符是字母表Σ中的元素。例如Σ={a,b}，a或b是字符

• 字符串：Σ中的字符组成的有穷序列。例如a，ab，aab都是Σ上的字符串

• 字符串的长度：指字符串中的字符个数。如|abc|=3

• 空串ε：由零个字符组成的序列，|ε|=0

• 连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号为“·”可省略。显然，对于字母表Σ的任意字符串S，S·ε=ε·S=S

• Σ*：是指包括空串ε在内的Σ上的所有字符串的集合。例如：Σ={a,b}。Σ *={ε,a,b,ab,....}

• 字符串中的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为α^n。

• 字符串集合的运算：设A、B代表字母集Σ上的两个字符串集合

  • 或（合并）：A∪B={α|α∈A或α属于B}

  • 积（连接）：AB={αβ|α∈且β∈B}

  • 幂：规定A^0={ε}

  • 正则闭包+：A+ = A^1∪A^2...

  • 闭包*：A *=A^0∪A+

文法G是一个四元组，可表示为G=(V,T,P,S)，其中

V：非终结符，不是语言组成部分，不是最终结果，可以推导出其他元素

T：终结符，是语言的组成部分，是最终结果，可以推导出其它元素

S：起始符，是语言的开始符号

P：产生式，用终结符代替非终结符的规则，例如a->b

齐姆斯基（Chomsky）把文法分成4中类型，即0型、1型、2型和3型。

0型文法也称为短语文法，其功能相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言

1型文法也称为上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串。例如，若αAβ->αγβ是1型文法的产生式，α和β不全为空，则终结符A只有在左边是α，右边是β的上下文中才可以替换成γ

2型文法就是上下文无关文法，非终结符的替换无需考虑上下文。程序设计语言中的大部分语法都是上下文无关文法

3型文法等价于正规式，因此也被称为正规文法或线形文法

8.2.3 正规式

语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数和界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集Σ（字母表）上的字符串的一个子集，称为正规集。

正规式和正规集

对于字母表Σ，其上的正规式及其表示的正规集可以递归定义如下：

1.ε是一个正规式，它表示集合L（ε）={ε}

2.若a是Σ上的字符，则a是一个正规式，它所表示的正规集为{a}

3.若正规式r和s分别表示正规集L（r）和L（s）则：

• r|s是正规式，表示集合L(r)∪L(s)

• r·s是正规式，表示集合L(r)L(s)

• r *是正规式，表示集合(L(r)) *

• (r)是正规式，表示集合L(r)

8.2.4 有限自动机

有限自动机是一种识别装置的抽象概念，它能准确的识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。

（1）确定的有限自动机（DFA）：一个确定的有限自动机是一个五元组（S，Σ，f，S0，Z），其中：

S是一个有限集，其每一个元素称为一个状态

Σ是一个有穷字母表，其每个元素称为一个输入字符

f是S*Σ->S上的单值部分映像。f(A,a)=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。

S0∈S，是唯一的一个开始状态。

Z是非空的终止状态集合，Z⊆S。

（2）不确定的有限自动机（NFA）：一个不确定的有限自动机也是一个五元组，它与确定的有限自动机的区别如下

1. f是S*Σ->2S上的映像。对于S中的一个给定的状态及输入符号，返回一个状态的集合。即当前状态的后继状态不是唯一的。

2. 有向弧上的标记可以是ε

确定的有限自动机和不确定的有限自动机：输入一个字符，看是否能够得出唯一的后继，若能，则是确定的，否则若是得出多个后继，则是不确定的

8.2.5 语法分析方法

自上而下语法分析：最左推导，从左至右。给定文法G和源程序串r。从G的开始符号S触发，通过反复使用产生式对巨型的非终结符进行替换（推倒），逐步推出r

递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法

自下而上语法分析：最有推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替（归约），逐步归约到开始符号S

移进-归约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的思想