软考复习之编译原理
# 软考复习之编译原理
## 语言处理程序
*语言处理程序是将高级语言或汇编语言编写的程序**翻译**成某种机器语言*
### 汇编语言
*汇编语言是为特定计算机设计的面向机器的符号化的设计语言*
汇编语言源程序是指用汇编语言编写的程序
#### 语句
##### 指令语句
*指令语句又叫机器指令语句*
将其汇编后能产生相应的机器代码
基本指令有`ADD`.`SUB`,`AND`等
##### 伪指令语句
*伪指令语句指示汇编程序在汇编源程序时完成的工作*
汇编后不产生相应的机器码
##### 宏指令语句
*宏指令语句就是宏的引用*
宏的定义必须按照相应的规定进行，每个宏都有相应的宏名
#### 汇编程序
*汇编程序的功能是将用汇编语言写的源程序翻译成机器指令程序*
汇编程序一般需要两次扫描源程序才能完成翻译过程
**第一次扫描**
- 创建记录汇编时遇到的符号的值的符号表ST
- 一个固定的表MOT1记录每条机器指令的记忆码和指令长度
- 设立一个位置计数器或单元地址计数器LC来计算各汇编语句标点的地址，其初值一般是0
第二次扫描
- 使用符号指令表MOT2
- 设立一个伪指令表POT2
第二次扫描中，可执行的汇编语句应被翻译成对应的二进制代码机器指令
### 编译程序
*编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序*
#### 词法分析
*对源程序从前到后、从左到右的逐个字符扫描，从中识别出一个个“单词”符号*
词法规则用3型号文法或正规表达式描述，它产生的集合是语言基本字符集字母表上的字符串的一个子集叫做正规集
##### 正规表达式与正规集
##### 有限状态机
**确定有限状态机（DFA）**
**不确定的有限状态机（NFA）**
##### NFA到DFA的转换
[NFA到DFA的转化_暗夜绿的博客](https://blog.csdn.net/weixin_48627356/article/details/121321357)
~~感觉不考~~
##### DFA的最小化
[【编译原理】最小化 DFA_零碎@流年絮语的博客](https://blog.csdn.net/qq_44824148/article/details/115477583)
~~感觉也必考~~
##### 正规式与有限自动机之间的转换
~~感觉还是不考~~
##### 词法分析器构造
1. 用正规表达式描述语言中的单词构成规则
2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集
3. 将构造出的NFA转换成等价的DFA
4. 对DFA进行最小化处理
5. 从DFA构造词法分析器
#### 语法分析
*根据语言的语法规则将单词符号序列分解成各类语法单元，如果没有语法错误，语法分析后就能正确的构造出语法树，否则指出语法错误。*
语法分析的任务是根据语言的规则分析单词串中是否构成短语和句子
- ##### 文法和语言分析
*描述语言语法结构的规则成为<b>文法</b>*
[【编译原理】文法的分类_Tuuua_的博客](https://blog.csdn.net/qq_42933533/article/details/109681369)
[语法分析_Shanhj的博客](https://blog.csdn.net/Shanhj/article/details/124771451)
#### 语义分析
*分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息。*
只有语法检查与语义检查都正确的源程序才能被翻译成正确的目标代码
#### 中间代码生成
*中间代码生成阶段的工作是根据语义分析的输出生成中间代码*
- 中间代码是一种简单且含义明确的记号系统
- 可以有多种形式
- 特征是与具体机器无关
- 最常用的是三地址码，实现方式是四元式
**常用的中间代码形式：**
- **后缀式**：[逆波兰式_百度百科 (baidu.com)](https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437?fromtitle=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F&fromid=6160580&fr=aladdin)
- 树形表示
- 三元表示
- 四元表示
**常用语法结构翻译**
布尔表达式和控制语句：[【编译原理系列】布尔表达式及控制语句翻译_槑！的博客](https://blog.csdn.net/weixin_43934607/article/details/113068312)
算数表达式和赋值语句：[【编译原理系列】算术表达式与数组元素翻译_槑！的博客](https://blog.csdn.net/weixin_43934607/article/details/113077357?ops_request_misc=&request_id=&biz_id=102&utm_term=%E7%AE%97%E6%95%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E7%BF%BB%E8%AF%91&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-113077357.142^v51^new_blog_pos_by_title,201^v3^add_ask&spm=1018.2226.3001.4187)
**动态存储分配和过程调用的翻译**
~~没见考过~~
#### 代码优化
*代码优化生成高效的目标代码*
可以在中间代码生成阶段进行也可以在目标代码生成阶段进行
一般建立在对程序的控制流和数据流分析的基础上
#### 目标代码生成
*把中间代码变换成特定机器上的绝对指令代码、可重定向的指令代码或汇编指令代码*
和机器密切相关
是编译器工作的最后一个阶段
**代码生成所需要考虑的主要问题**
- 中间代码形式
- 目标代码形式
- 寄存器的分配
- 计算时序的选择
#### 符号表管理
*记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成*
#### 出错处理
*<b>动态错误</b>又成为语义错误，发生在程序运行时*
*<b>静态错误</b>时指编译状态发现的程序错误*
编译时发现错误后，应该采用适当的策略修复他们，使得分析过程能够继续下去，以便能够在一次编译过程中尽可能多的找出程序中的错误
### 解释程序
*解释程序与编译程序在词法、语法、语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的中间表达式*
#### 基本结构
##### 分析部分
- 词法分析
- 语法分析
- 语义分析
##### 解释部分
### 编译与解释的比较
- 效率：编译方式可能取得更高的效率
- 灵活性：解释方式更灵活
- 可移植性：解释方法更好