目录
7.1 基本概念
分类
硬件/抽象层次
- 低级语言: 通常称机器语言和汇编语言为低级语言。机器语言是指用0、1字符串组成的机器指令序列,是最基本的计算机语言。汇编语言是指用符号表示指令的语言。
- 高级语言:是从人类的逻辑思维角度出发、面向各类应用的程序语言,其抽象程度大大提高,需要编译成特定机器上的目标代码才能执行。这类语言与人们使用的自然语言比较接近,大大提高了程序设计的效率。
编程范式/计算模型
- 命令式程序设计语言 命令式程序设计语言是基于动作的语言,在这种语言中,计算被看作是动作的序列.命令式语言族开始于Fortran、Pascal和C语言,体现了命令式程序设计的关键思想。
- 面向对象的程序设计语言 面向对象的程序设计在很大程度上应归功于从模拟领域发展而来的Simula,Simula提出了对象和类的概念。C++、Java和Smalltalk是面向对象程序设计语言的代表。
- 函数式程序设计语言 函数式程序设计语言是一类以2-演算为基础的语言。该语言的代表是LISP,其中大量使用了递归。
- 逻辑型程序设计语言 逻辑型程序设计语言是一类以形式逻辑为基础的语言。该语言的代表是建立在关系理论和一阶谓词理论基础上的Prolog.
常见定义
- 语法:由程序设计语言的基本符号组成程序中的各个语法成分的一组规则,其中由基本字符构成的符号书写规则称为词法规则,由符号构成语法成分的规则称为语法规则。程序语言的语法可通过形式语言进行描述。
- 语义:程序语言中按语法规则构成的各个语法成分的含义,可分为静态语义和动态语义。
- 语用:表示构成语言的各个记号和使用者的关系,涉及符号的来源、使用和影响。
- 语境:理解和实现程序设计语言的环境,包括编译环境和运行环境。
基本成分
数据成分
- 常量和变量
- 全局量和局部量
- 数据类型
- 基本类型: 整型(int)、字符型(char)、实型(float、double)和布尔类型(bool)。
- 特殊类型: 空类型(void)
- 用户定义类型: 枚举类型(enum)
- 构造类型: 数组、结构和联合
- 指针类型: type
- 抽象数据类型: 类类型
运算成分
- 算术运算: 加减乘除
- 逻辑运算: 或与非
- 关系运算
控制成分
- 顺序结构
- 选择结构
- 循环结构
函数和函数的调用
- 值传递
7.2 编译与解释
汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。用汇编语言编写的程序称为汇编语言源程序。汇编语言源程序由若干条语句组成。一个程序中可以有3类语句:指令语句、伪指令语句和宏指令语句。
编译程序的功能是把用高级语言书写的源程序翻译成与之等价的目标程序。 编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段,实际的编译器可能会将其中的某些阶段结合在一起进行处理。
解释程序是一种语言处理程序,在词法、语法和语义分析方面与编译程序的工作原理基本相同,但在运行用户程序时,它直接执行源程序或源程序的内部形式(中间代码)。因此,解释程序并不产生目标程序,这是它和编译程序的主要区别。

- 词法分析阶段的任务是:对源程序从前到后(从左到右)逐个字符进行扫描,从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位,如关键字、标识符等。
- 语法分析阶段的任务是:在词法分析的基础上,根据语言的语法规则将单词符号序列分解成各类语法单位,如“表达式”“语句”和“程序”等。词法分析和语法分析本质上都是对源程序的结构进行分析。
- 语义分析阶段主要是:审查源程序是否存在语义错误,并收集类型信息供后面的代码生成阶段使用,只有语法和语义都正确的源程序才能翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。
- 中间代码生成阶段的工作:是根据语义分析的输出生成中间代码。
- 代码优化阶段的任务是:对前一阶段产生的中间代码进行变换或进行改造,目的是使生成的目标代码更为高效,即省时间和省空间。
- 目标代码生成阶段的任务是:把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。这是编译的最后阶段,它的工作与具体的机器密切相关。
7.3 文法
一个形式文法是一个有序四元组 ,其中:
- :非终结符。不是语言组成部分,不是最终结果,可理解为占位符。
- :终结符。是语言的组成部分,是最终结果。
- :起始符。是语言的开始符号。
- :产生式。用终结符替代非终结符的规则。形如
| 类型 | 别称 | 说明 | 对应自动机 |
|---|---|---|---|
| 0型 | 短语文法 | 的每条产生式 满足 属于 的正则闭包且至少含有一个非终结符,而 属于 的闭包 | 图灵机 |
| 1型 | 上下文有关文法 | 的任何产生式 满足 ,仅仅 例外,但 不得出现在任何产生式右部 | 线性界限自动机 |
| 2型 | 上下文无关文法 | 的任何产生式为 , 为非终结符, 为 的闭包 | 非确定的下推自动机 |
| 3型 | 正规文法 | 的任何产生式为 或 , 属于非终结符的闭包,、 都属于非终结符 | 有限自动机 |
语法推导树
一棵语法树应具有以下特征:
- 每个结点都有一个标记,此标记是 的一个符号;
- 根的标记是 ;
- 若一结点 至少有一个它自己除外的子孙,并且有标记 ,则 肯定在 中;
- 如果结点 的直接子孙,从左到右的次序是结点 ,其标记分别是:,那么 ,一定是 中的一个产生式。
例题
例:
文法 ,其中: ; 。
请构造句型 的推导树。
答案&解析:

7.4 有限自动机
- 是一个有限集,每个元素为一个状态
- 是一个有穷字母表,每个元素为一个输入字符
- 是转换函数:是一个单值对照
- ,属于,是其唯一的初态
- 是一个终态集(可空)
有限状态自动机可以形象地用状态转换图表示,设有限状态自动机:
其中:

例题
例:下图所示为一个有限自动机(其中,A是初态、C是终态),该自动机可识____。

A:0000 B:1111 C:0101 D:1010
答案: C
解析:
从初态 A 开始,跳转到指定数字的路径,从左到右依次尝试:
A:
B:
C:
D:
7.5 正规式
有限自动机的另一种表达形式
正规式是描述程序语言单词的表达式,对于字母 ,其上的正规式及其表示的正规集可以递归定义如下。
- 是一个正规式,它表示集合 。
- 若 是 上的字符,则 是一个正规式,它所表示的正规集 。
- 若正规式 和 分别表示正规集 ,则
- (a) 是正规式,表示集合 ;
- (b) 是正规式,表示集合 ;
- (c) 是正规式,表示集合 ;
- (d) 是正规式,表示集合 。
仅由有限次地使用上述三个步骤定义的表达式才是 上的正规式。由此可见,正规式要么为空,要么由字母、或、连接、闭包运算符组成。其中闭包运算符“”具有最高的优先级,连接运算具有次高优先级,或运算符“|”具有最低优先级。
例题
例题:下面文法 它无法识别( 1 ),此文法对应正规式为( 2 )。
:
( 1 ) A. ababab B. bababa C. abbaab D. babba
( 2 ) A. B. C. D.
答案:(1) D (2) C
解析:
根据题意得:
(1) 尝试写出推导式: A:
B:
C:
D:
因此选择 D
(2)
A:数个 a / b 的组合,无法排除上题中D选项的情况
B:数个 ab 的组合,无法实现ba的情况
C:可以正确匹配表达式
D:数个 ab 为开头的组合加 数个 ba 的组合
因此选择 C
7.6 表达式
一句话,就是利用树的遍历来求前缀、中缀和后缀表达式。
(表达式树结构示意:根节点为 +,左孩子为 a,右孩子为 b)
- 前缀表达式 (根左右) : (+ab)
- 中缀表达式 (左根右) : (a+b)
- 后缀表达式 (左右根) : (ab+)
graph TD plus(("+")) --> a(("a")) plus --> b(("b"))例题
例:表达式的后缀式是______。
A. a b c 5 + * -
B. a b - c + 5 *
C. a b c - * 5 +
D. a b - c 5 + *
答案:D
解析:
7.7 传值与引用
传值调用: 形参取的是实参的值, 形参的改变不会导致实参的值发生改变。
引用(传址)调用: 形参取的是实参的地址, 即相当于实参存储单元地址的引用 因此其值改变的同时就改变了实参的值。
例题

答案:D
解析:
外部调用f(x, &x),其中两个x均为10
x = 2 * x - 1 // 2 * 10 - 1 = 19a = a + x // 10 + 19 = 29(a为引用,此时外部变量更改)return;7.8 各种程序设计语言特点
- Fortran语言(科学计算,执行效率高)
- Pascal语言(为教学而开发的,表达能力强, Delphi )
- C语言(指针操作能力强,高效)
- Lisp语言(函数式程序语言,符号处理,人工智能)
- C++语言(面向对象,高效)
- Java语言(面向对象,中间代码,跨平台)
- C#语言(面向对象,中间代码,.Net)
- Prolog语言(逻辑推理,简洁性,表达能力,数据库和专家系统)
NOTE实际上还有太多太多编程语言,如HTML、JavaScript、Python、Dart…,但是不在考点范围内,因此这里只是简单介绍