软件设计师—程序设计语言笔记（历年考试重点）

﹏ヽ暗。殇╰゛Y 2024-03-22 19:36 48阅读 0赞

**目录**

解释器

编译器

符号表

常考编译阶段

词法分析

正规式

有限自动机

语法分析

语义分析

中间代码生成

目标代码生成

上下文无关文法

后缀式（逆波兰式）

自上而下分析法

自下而上分析法

栈

堆

--------------------

低级语言：机器语言、汇编语言。

高级语言：Java、C、C++、Php、Python等。

## 解释器 ##

边翻译边执行，工作效率低。

1）翻译源程序时**不生成**独立的目标程序。

2）**解释程序和源程序要参与到程序的运行**过程中，程序执行速度慢。

## 编译器 ##

先翻译后执行，工作效率高，但是可移植性差。

1）翻译时将源程序翻译成**独立保存的目标程序**。

2）机器上运行的是与源程序等价的目标程序，源程序和编译程序**不再参与运行。**

**程序的三种基本控制结构：**

顺序、选择、循环。

**数据类型的作用：**

1）便于为数据合理分配存储单元。

2）便于对参与表达式计算的数据对象进行检查。

3）便于规定数据对象的取值范围及能够进行的运算。

**函数形参调用：**

值调用：实参的值传给形参（不可以双向传递），实参可以是变量、常量、表达式。

引用调用：实参的地址传给形参（双向传递），表达式和常量不能传地址。

## 符号表 ##

不断收集、记录和使用源程序中一些相关符号的类型和特征等信息并将其存入符号表中。

作用：记录源程序中各个字段的必要信息，以辅助语义的正确性检查和代码生成。

## 常考编译阶段 ##

编译阶段分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六大阶段，在这里只介绍软考中比较常考的阶段。

### 词法分析 ###

输入：源程序

输出：记号流

作用：分析构成程序的字符及由字符按照构造规则构成的符号**是否符合程序语言的规定**。

#### 正规式 ####

(a|b) 通俗来讲，这种形式就是在a和b中选一个，只能选其中一个。

(a\*) a的\*次幂，\*可以是0~n中任何正整数。

#### 有限自动机 ####

词法分析的一个工具，它能正确识别正规集。

确定的有限自动机（DFA）：对每一个状态来说识别字符后转移的状态是唯一的。

不确定的有限自动机（NFA）：对每一个状态来说识别字符后转移的状态是不唯一的（识别字符含有空）。

对于有限自动机来说，开始识别单词必须从初态开始，识别完成后，当前状态为终态才合法，才算这个有限自动机可以识别这个字符串。例如，下图中S为初态，F为终态，可以识别的单词为ab或者ac,不能识别单个a、b、c,识别a属于最后结束没停留在终态，识别b和c属于没从初态开始识别。

![bf8e24670708438795242a3a3dcea918.png][]

### 语法分析 ###

输入：记号流

输出：语法树（分析树）

作用：语法分析阶段可以发现程序中**所有语法错误**。

### 语义分析 ###

输入：语法树

作用：进行类型分析和检查，**不能发现程序中所有语义错误**，可以发现静态语义错误，但动态语义错误运行时才可以发现。

动态语义错误：

例如：循环条件为空、除数为0等情况。C语言的表达式中引用了未赋初始量的变量，可以通过编译运行，但运行结果不一定是期望的结果，但在Java中会报错。

### 中间代码生成 ###

常见类型：后缀式、三地址代码、三元式、四元式、树、图等形式。

中间代码生成与**具体的机器无关**（不依赖具体的机器），可以将**不同的高级语言翻译成同一种中间代码**，中间代码可以跨平台。

优点：因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的**可移植性**。

### 目标代码生成 ###

目标代码生成阶段的工作**与具体的机器密切相关**，并且**寄存器的分配工作**处于目标代码生成阶段。

对目标代码进行反编译，不能还原出源程序，只能转变成功能上等价的汇编程序。

**脚本语言**属于**动态语言**，其程序结构在运行时改变，脚本语言执行方式为**解释方式**，不产生独立的目标程序。

C语言属于静态语言，其所有成分可在编译时确定。

## 上下文无关文法 ##

大多数程序设计语言的语法规则用上下文无关文法描述即可。

G=(N，T，P，S)

N：非终结符号集 T：终结符号集 P：产生式集 S：开始符号

### 后缀式（逆波兰式） ###

示例：

![246258e6614a40eea92bb68bcf0e7487.png][]

语法树的后序遍历（左右根）结果就是表达式的逆波兰式。

## 自上而下分析法 ##

递归下降分析法、预测分析法等。

## 自下而上分析法 ##

移进-归约分析法、算术优先分析法、LR分析等。

## 栈 ##

栈是局部变量以及每次**函数调用**时所需保存的信息的存储区域，其空间的**分配和释放由操作系统**进行管理。

## 堆 ##

堆是一块动态存储区域，由**程序员**在程序中进行**分配和释放**，若程序语句没有释放，则程序结束时由操作系统回收。

[bf8e24670708438795242a3a3dcea918.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0c7e50f4d1a642fe8590e1d4efce855c.png
[246258e6614a40eea92bb68bcf0e7487.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/2256bd916f594ede99d73aab742bc332.png