【软考zst2001专辑笔记】002程序设计语言
一、编译程序与解释程序
低级语言：机器语言、汇编语言
高级语言：Java、C、C++、PHP、Python、Delphi、PASCAL
语言之间的翻译形式：汇编、解释、编译
高级语言编写的源程序，需要对应的解释程序或编译程序对其进行翻译。
解释程序（解释器）：
- 翻译程序是不产成独立的目标程序。
- 解释程序和源程序都要参与到程序的运行过程中。
编译程序（编译器）：
- 翻译时将源程序翻译成独立保存的目标程序。
- 机器上运行的是与源程序等价的目标程序。
- 源程序和编译程序都不参与目标程序的运行过程。
二、程序设计语言基本成分
基本控制结构：顺序、选择、重复（循环）
数据类型的作用：
- 便于合理分配存储单元
- 便于对参与表达式计算的对象进行检查
- 便于规定数据对象的取值范围以及能进行的运算
变量有对应的存储单元，常量没有。
三、传值调用与传地址调用
函数定义的基本形式：
函数调用：
值调用：
- 将实参的值传递给形参，实参可以是变量、常量、表达式
- 不可以实现形参和传参双向传递数据的效果。
引用调用：
- 将实参的地址传递给形参，形参必须有地址，实参不能是常量、表达式。
- 可以实现形参和实参间的双向传递数据的效果，即改变形参的值同时也改变实参的值
四、编译、解释程序翻译阶段
编译方式：
- 词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
- 中间代码生成和代码优化不是必要，即前三步完成后可直接生成目标代码
解释方式：
- 词法分析、语法分析、语义分析
编译器和解释器都不可省略词法分析、语法分析、语义分析，且顺序不可变
五、符号表
不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表。
记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。
六、词法分析
输入：源程序
输出：记号流
主要作用：分析构成程序的字符，以及字符按照构造规则构成的符号是否符合程序语言的规定。
七、语法分析
输入：记号流
输出：语法树（分析树）
主要作用：对各条语句的结构进行合法性分析，分析程序中的句子结构是否正确。
八、语义分析
输入：语法树（分析树）
主要作用：进行类型分析和检查。
不能发现程序中所有的语义错误，只能发现静态语义错误。动态语义错误只能在运行是发现。
九、目标代码生成
该阶段的工作与机器密切相关。
寄存器的分配处于目标代码生成阶段。
十、中间代码生成
常见的中间代码：后缀式、三地址码、三元式、四元式和树（图）等形式
特征：
- 与具体机器无关（不依赖于具体机器）
- 可以将不用的高级程序语言翻译成同一种中间代码。
- 中间代码可跨平台
因为与机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可执行性。
十一、正规式
词法分析的工具
| 正规式 | 正规集 |
|---|---|
| Ab | 字符串ab构成的集合 |
| a|b | 字符串a、b构成的集合 |
| a* | 由0个或多个a构成的字符串集合 |
| (a|b)* | 所有字符a和b构成的串的集合 |
| a(a|b)* | 以a为首字符的a、b字符串的集合 |
| (a|b)*abb | 以abb结尾的a、b字符串的集合 |
十二、有限自动机
词法分析的工具，能正确识别正规集
确定的有限自动机（DFA）：对每个状态来说识别字符后转移的状态是唯一的
不确定的有限自动机（NFA）：对每个状态来说识别字符后转移的状态是不唯一的
判断依据：看看每个状态（就是哪个小圆圈）是不是存在多个指向别的状态的箭头（指向自己的不算）。
十三、上下文无关文法
广泛用于各种程序设计语言的语法规则。
大写字母为非终结符，小写字母为终结符。
十四、中缀、后缀表达式装换
中缀式转后缀式，优先级相同，从左向右。
十五、语法树中序、后续遍历
中序遍历->中缀式
后序遍历->后缀式
中序：左根右
后序：左右根
- 例：1-2x(3+4)/5
十六、杂题
反编译是编译的逆过程，不能把可执行文件还原成高级语言源代码，只能转换成功能上等价的汇编程序。
脚本语言是动态语言，动态语言都是解释型语言。
变量存储的是内存单元地址时，成为指针变量。对指针变量进行算术运算，可以使其指向其他元素。
链表中的结点空间需要程序员根据需要申请和释放，因此数据空间应该采用堆存储分配策略。
可视化程序设计是以“所见即所得”的编程思想为原则
编译时变量分配存储单元所用地址是逻辑地址，运行时映射成物理地址。
程序运行时，用户内存空间分为代码区、静态数据区、栈区、堆区。栈区、堆区属于动态数据区，常量在静态数据区。
语法分析方法，根据产生语法树的方向：
自顶向下分析法：递归下降分析法、预测分析法。
自底向上分析法：算符优先分析法、LR分析法、移进-规约分析法。
用户可命名的对象：变量、函数、数据类型
编程语言分类
函数式编程语言：Lisp
逻辑式编程语言：Prolog
过程式、面向对象：Python
面向对象：Java、C++
语法制导翻译是静态语义分析方法。
栈区由系统进行管理，堆区由程序员进行管理。
C或C++代码生成可执行文件的过程：预处理->编译->汇编->链接
Java特征：采用即时编译。对象在堆空间分配。自动垃圾回收。
Python中：
列表（list）是可变、有序、可重复的序列结构
元组（tuptle）、字符串（str）是不可变的
集合（set）去重的
Python深度学习模型：TensorFlow、PyTorch、Keras
Python 绘图库：Matplotlib