程序设计语言核心知识点汇总
一、编译程序和解释程序
解释器
- 翻译源程序时不生成独立的目标程序
- 解释程序和源程序要参与到程序的运行过程中
编译器
- 翻译时将源程序翻译成独立保存的目标程序
- 机器上运行的是与源程序等价的目标程序
- 源程序和编译程序都不再参与目标程序的运行过程
二、程序设计语言基本成分
程序的三种基本控制结构
- 顺序
- 选择
- 循环（重复）
数据类型的作用
- 便于为数据合理分配存储单元
- 便于对参与表达式计算的数据对象进行检查
- 便于规定数据对象的取值范围及能够进行的运算
常量和变量
- 常量：不可以修改，没有分配存储单元
- 变量：可以修改，有分配存储单元
逻辑运算
- 逻辑与运算（&&）
- 两边同时为真才为真，有一个假则结果为假
- 短路运算时，左边为假则表达式结果为假
- 逻辑或运算（||）
- 两边同时为假才为假，有一个真则结果为真
- 短路运算时，左边为真则表达式结果为真
- 逻辑非运算（!）
- 真变假，假变真
- 右结合（从右向左算）
- 示例1：!3<2，先算3<2为假，然后!假，结果为真
- 示例2：x=1,y=2,z=3，执行x=y=z时，先算y=z（y的值为3），再算x=y，最终x、y、z的值都为3
三、传值调用与传引用调用
基本概念
- 函数定义形式：返回值 函数名(形参类型 形参, 形参类型 形参)
- 函数调用形式：函数名(实参, 实参)
- 示例：
// 定义函数f1，a和b作为形式参数
void f1(int a, int b) {
// 函数体可根据需求添加具体逻辑
}
// 主函数，程序执行的入口点
int main() {
// 调用函数f1，传递实际参数5和28
f1(5, 28);
return 0;
}
传值调用
- 将实参的值传递给形参，实参可以是变量、常量和表达式
- 不可以实现形参和实参间双向传递数据的效果
传引用（地址）调用
- 将实参的地址传递给形参，形参必须有地址，实参不能是常量（值）、表达式
- 可以实现形参和实参间双向传递数据的效果，即改变形参的值同时也改变了实参的值
四、编译程序基本原理
处理阶段
- 编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
- 解释方式：词法分析、语法分析、语义分析
关键特性
- 编译器和解释器都不可省略词法分析、语法分析、语义分析，且顺序不可交换
- 编译器方式中，中间代码生成和代码优化不是必要步骤，可省略（可在语义分析后直接生成目标代码）
五、符号表
- 功能：不断收集、记录和使用源程序中相关符号的类型和特征等信息，并将其存入符号表
- 作用：记录源程序中各个字符的必要信息，辅助语义的正确性检查和代码生成
六、词法、语法、语义分析与目标代码生成
词法分析
- 输入：源程序；输出：记号流
- 主要作用：分析构成程序的字符，及由字符按构造规则构成的符号是否符合程序语言的规定
语法分析
- 输入：记号流；输出：语法树（分析树）
- 主要作用：对各条语句的结构进行合法性分析，检查程序中的句子结构是否正确
- 特性：可以发现程序中所有的语法错误
语义分析
- 输入：语法树（分析树）
- 主要作用：进行类型分析和检查
- 特性：
- 不能发现程序中所有的语义错误
- 可以发现静态语义错误
- 不能发现动态语义错误（动态语义错误需在运行时发现）
目标代码生成
- 特性：与具体的机器密切相关
- 关键工作：寄存器的分配工作处于此阶段
七、程序异常和错误
- 动态的语义错误在运行的时候才能检测出来
八、中间代码
常见形式
- 后缀式、三地址码、三元式、四元式和树（图）等
特性
- 与具体的机器无关（不依赖具体的机器），可将不同高级程序语言翻译成同一种中间代码，支持跨平台
- 有利于进行与机器无关的优化处理和提高编译程序的可移植性
九、正规式
正规式 | 正规集（对应字符串集合） | 符号解析与规则说明 | 示例字符串 |
ab | 仅包含 “ab” 这一个字符串的集合 | 无特殊符号，直接表示字符按顺序拼接（a 后接 b） | ab |
a|b | 包含 “a” 和 “b” 两个字符串的集合 | “|” 是 “或” 运算符，表示匹配 “a” 或者 “b” 中的任意一个 | a 、 b |
a* | 由 0 个或多个 “a” 组成的所有字符串集合 | “*” 是 “重复” 运算符，表示其前面的字符（此处为 a）可出现 0 次、1 次、2 次……（含空串） | "" （空串）、 a 、 aa 、 aaa …… |
(a|b)* | 由任意个 “a” 或 “b” 组成的所有字符串集合（含空串） | 括号将 “a|b” 视为整体（先算 “a 或 b”），再用 “*” 表示整体可重复任意次 | "" 、 a 、 b 、 ab 、 ba 、 aab …… |
a(a|b)* | 以 “a” 开头，后接任意个 “a” 或 “b” 的字符串集合 | 开头固定为 “a”，后面紧跟 “(a|b)*”（即任意组合的 a 或 b） | a 、 aa 、 ab 、 aba 、 abba …… |
(a|b)*abb | 以 “abb” 结尾，前接任意个 “a” 或 “b” 的字符串集合 | 前面为 “(a|b)*”（任意 a 或 b），结尾固定为 “abb” | abb 、 aabb 、 babbb 、 aababb …… |
十、有限自动机
- 作用：词法分析的工具，能正确地识别正规集
- 分类：
- 确定的有限自动机（DFA）：对每一个状态来说，识别字符后只有一个转移状态
- 不确定的有限自动机（NFA）：对每一个状态来说，识别字符后有一个以上的转移状态
十一、上下文无关文法
- 大多数程序设计语言的语法规则用上下文无关文法描述
十二、中缀、后缀表达式
- 中缀式：如a + b
- 后缀式（逆波兰式）：如ab+
- 求值方式：后缀式利用栈进行求值
- 与语法树的关系：
- 后缀式对应语法树的后序遍历
- 中缀式对应语法树的中序遍历
十三、杂题选讲（语法分析方法）
自顶向下语法分析方法
- 递归下降分析法
- 预测分析法
自底向上语法分析方法
- 移进—归约分析法
- LR分析法