软考中级_【软件设计师】知识点之【程序设计语言】

一、低级语言和高级语言

1. 计算机只能识别0或1（机器语言）
2. 汇编语言
   1. 例：ADD X1 2
3. 低级语言分类：
   1. 机器语言
   2. 汇编语言
4. 高级语言分类：
   1. java
   2. js
   3. python

二、编译程序和解释程序

解释程序

1. 解释程序对应脚本语言
   1. 例如：PHP、js、python
2. 解释程序
   1. 会直接解释源程序执行
   2. 或者
   3. 翻译成某种中间代码再加以执行
3. 解释器：
   1. 翻译源程序不会生成独立的目标程序
   2. 解释程序和源程序要参与到程序的运行过程中

编译程序

1. 编译程序：
   1. 是用编译器将源程序翻译为目标语言程序，在执行
   2. 例如：java
2. 编译器：
   1. 翻译时将源程序翻译成独立保存的目标程序
   2. 机器上运行的是源程序等价的目标程序
   3. 源程序和编译程序都不再参与目标程序的运行过程

三、程序设计语言的结果成本

1. 顺序结构
2. 逻辑结构
3. 循环结构（重复）

四、数据类型

1. 许多程序中规定，程序中的数据必须具有类型，作用是：
   1. 便于为数据合理分配存储单元
   2. 便于对参与表达式计算的数据对象进行检查
   3. 便于规定数据对象的取值范围及能够进行运算
2. 隐式转换：容量小的的数据类型相容量大的数据类型转换
3. 显式转换：容量大的的数据类型相容量小的数据类型转换
4. 变量具有对应的存储单位，常量则没有，常量是存储在常量池中
5. 与或非
   1. 优先级（高到低）：not>and>
   2. and or 为左结合
   3. not为右结合
      1. 例：not 2>3 （先算2>3）

五、函数

1. 传值调用：
   1. 将实参的值传递给形参，实参可以是变量，常量和表达式。
   2. 不可以实现形参和实参间双向传递数据的效果
2. 引用调用：
   1. 将实参的地址传递给形参，形参必须有地址，实参不能是常量（值），表达式
   2. 可以实现形参和实参之间双向传递数据的效果，即改变形参的值的同时也改变了实参的值。

六、编译、解释程序翻译阶段

1. 编译方式（六种）：
   1. 词法分析、语法分析、语义分析、中间代码分析、代码优化、目标代码生成
   2. 编译器方式中中间代码生成、和代码优化不是必要的，可以省略
2. 解释方式：
   1. 词法分析、语法分析、语义分析
3. 编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换

符号表管理

1. 符号表是不断收集，记录和使用源程序中的一些相关符号的类型和特征等信息，并将其存储到符号表中。
2. 记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。
3. 做题技巧：
   1. 选项中出现数据结构名词，排除即可。

词法分析

1. 输入：源程序
2. 输出：记号流
3. 作用作用：是分析程序的字符及由字符按照构造规则构成的符号是否符合程序语言的规定。
   1. 例：inn a=10； （错误：inn应该为：int）

语法分析

1. 输如：记号流
2. 输出：语法数（分析数）
3. 主要作用：
   1. 对各条语句的结构进行合法性分析
   2. 分析程序中的语句结构是否正确，
   3. 可以发现程序中的所有语法错误
4. 例题：
   1. inta =1 (错误：没有分号)

语义分析

1. 输入：语法数（分析数）
2. 主要作用：
   1. 进行类型分析和检查
3. 注意点：
   1. 语义分析不能发现程序中所有的语义错误
   2. 可以发现静态语义错误
   3. 不可以发现动态语义错误（动态语义错误只能在程序运行时发现）
4. 例子：
   1. Boolean a=1; (类型错误)

目标代码生成

1. 目标代码生成的工作与具体的机器密切相关
2. 寄存器的分配工作是处于目标代码生成

动态语义错误

1. 动态语义错误只能在程序运行时发现
   1. 例子：
      1. 死循环
      2. 除数为0

中间代码生成

1. 常见的中间代码生成
   1. 后缀式：
   2. 三地址式
   3. 三元式
   4. 四元式
   5. 树（图）
2. 中间代码生成与具体的机器无关（不依赖具有的机器）
3. 可以将不同的高级程序语言翻译成同一种中间代码
4. 中间代码可以跨平台
5. 使用中间代码生成有利于与机器无关的优化处理和提高编译程序的可移植性。

七、正规式

1. 词法分析的工具
   1. |表示或
   2. *表示具有0个或多个

2. 例子：
   1. 由a，b构成且包含偶数个a的集合：
      1. 解：(b*(aba))*

八、有限自动化

1. 词法分析工具
2. 能够正确的识别正规集
3. 图形解释
   1. 两种状态，
      1. 初态
      2. 终态（两种表现形式）

4. 符号解释：
   1. 图形出现a,b表示为a或b
   2. ε表示为空，可以直接跳转
   3. 例图：

5. 分类：
   1. 确定有限自动化（DFA）：对每一个状态来说识别字符后转移的状态是唯一的
      1. 例：a只能转移到终态

2. 不确定有限制动化（NFA）：对每一个状态来说识别字符后转移的状态不是唯一的。
    1. 例：a既可以到终态也可以是本身

九、上下文无关文法

1. 上下文无关文法：广泛的用于表示各种程序设计语言的语法规则
2. 题目形式：（给一个相关的表达式，可以用E、T、F文法推到出来）

或

3. 例题：
   1. 以S为开始符号，通过中间的字符推到终结到T
      1. 产生式意思：表示S可以推出某一个P的某个形式

4. 例题：

5. 例题：
   1. 分析：先分析结果需要的数学符号，再选在需要推产生式

6. 例题：
   1. 技巧：
      1. 括号根本推不出来，B排除
      2. 产生式中没有除好，D排除
      3. 终结式中的id表示为a~z，没有数字，C排除

7. 例题：
   1. 中缀表达式（符号往上提了）

十、中缀、后缀表达式转换

1. 中缀表达式语法

语法格式： a?b
a和b表示数字，?表示运算符号
例如：2+3

2. 后缀表达式(逆波兰式)语法

语法格式： ab?
a和b表示数字，?表示运算符号
例如：23+

3. 符号优先级

优先级（高到低）：
() >>   *  >> /  >> +  >> -  
>  >> and  >>  or
注意点：优先级相同，从右向左算

4. 中缀转后缀
   1.

中缀表达式：1-(2+3)*4/9
第一步：23+
第二步：23+9/
第三步：23+9/4*
第四步：123+9/4*-

5. 后缀转中缀
   1. 可以用栈进行转换
   2. 利用栈存取和弹出的思想，从第一个数字开始入栈，遇到符号后，将前两个弹出计算

中缀表达式：123+9/4*-
第一步：2+3
第二步：(2+3)/9
第三步：(2+3)/9*4
第四步：1-(2+3)/9*4

十一、语法树中、后序遍历

1. 语法树中序遍历可推出====>>中缀表达式

中序遍历读法：左根右

2. 语法树后序遍历可推出====>>后续表达式

后序遍历读法：左右根

十二、杂题总结

1. 编译是将高级语言源程序翻译成机器语言程序（汇编形式或机器代码形式），反编译是编译的逆过程。
2. 反编译通常不能还原成高级语言源代码，只能转换成功能上等价的汇编程序。
3. 脚本语言都是动态语言，动态语言都是解释型语言
   1. 如：js、php
4. 在C和C++中，指针变量可以是全局变量也可以是局部变量
5. 链表中的结点空间需要程序员根据需要申请和释放，因此，数据空间应采用堆存储分配策略
6. 标记语言：
   1. html
   2. xml
   3. wml
7. 可视化程序设计是开发应用程序不用编写或只需编写很少的程序代码，就能完成程序设计。
8. 编译过程中为变量分配存储单位所用的地址为逻辑地址，程序运行时再映射为物理地址。
9. C语言中全局变量存储在静态代码区，
10. C语言程序运行时，
11. 递归下降分析方法和预测分析法是一种自上而下的语法分析方法
12. 算符优先分析法和LR分析法属于自底向上的语法分析方法
13. 在源程序中，程序员可以对变量，数据类型，函数进行命名
14. Lisp是一种函数式编程语言，Prolog是逻辑式程序语言
15. 语法制导翻译是一种静态语义分析方法
16. 栈是函数调用时所需保存的存储区域。
17. 堆是一块动态存储区域，由程序员在程序中进行分配和释放。
18. C/C++编译过程：预处理》》编译》》汇编》》链接
19. Java语言特征;
    1. 采用及时编译
    2. 对象在堆空间分配
    3. 自动垃圾回收机制
20. Python：
    1. 元组（tuptle）：不可变
    2. 字符串（str）：不可变
    3. 集合（set）：不可重复
    4. 列表（List）：可变的、有序的、可重复的
21. Python机器学习库：
    1. TensorFlow
    2. PyTorch
    3. Keras
22. Python可视化库：
    1. Matplotlib