一、编译系统基本原理（下）
（1）有限状态机
1.1 概念
如果有限状态机每次转换后的状态是唯一的则称之为确定有限状态自动机（DFA）；
如果转换后的后继状态不是唯一的则称之为不确定有限状态自动机（NFA）；
状态机有三种状态：
初始状态: 最开始的状态；
后继状态：有限状态机在读入一个字符时，其状态改变为另一种状态，则改变后的状态被称为后继状态；
终止状态（接收状态）： 当前活动或事件的结束状态；
1.2 确定有限状态机（DFA）
一个确定有限自动机（DFA）M是一个五元式：
M = { S ，Σ ，δ ，K ，F }，其中
1. S 是一个有限集，包括了该状态机内的所有状态；
2. Σ 是一个有穷字母表，存储转换字符；
3. δ 是一个转换函数 δ（ 前一个状态 ，转换字符 ）= 转换后的状态 ；
4. K 是 S 当中的初态，具有唯一性；
5. F 是终态集，F ⊆ S ；（可空）
例：
M = { S ，Σ ，δ ，K ，F }
其中：
S = { S0 ，S1 ，S2 ，S3 };
Σ = { a ， b ，c }；
δ 转换函数：
( S0 ，a ) = S1 ； ( S1 ，b ) = S2 ； ( S1 ，c ) = S3 ；
K = S0 ；
F = { S2 ，S3 }；
（2）语法分析阶段
语法分析器以单位符号作为输入，分析单词符号串是否形成语法规则的语法单位，如表达式、赋值、循环等，按语法规则分析检查每条语句是否有正确的逻辑结构；
例如：
int arr[2] ，b；
b = arr * 10；
语法分析器只能判断其运算符搭配问题，不会发现数组不能直接跟变量相乘的问题；
语法分析的方法：
1. 自上而下分析法；
2.自下而上分析法；
（3）语义分析阶段
语义分析阶段主要是检查源程序是否存在语义错误，并收集类型信息供后面的代码生成阶段使用，只有语法和语义都正确的源程序才能翻译成正确的目标代码；
语义分析的主要工作是进行各类型分析和检查，比如赋值语句的左右两端是否类型匹配、表达式的除数是否为 0 等；
（4）中间代码生成阶段
中间代码生成阶段的工作是根据语义分析的输出生成中间代码；
中间代码是一种简单且含义明确的记号系统，可以有若干种形式，常见的有逆波兰记号、四元式、三元式和树；
他们的共同特征是代码的方式与具体的机器无关；
（5）代码优化阶段
代码优化阶段是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高级，即节省时间和空间；
（6）目标代码生成阶段
是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码；
这是编译的最后阶段，它的工作与硬件系统的结构和指令的含义有关；
二、程序语言的控制结构
三种基本结构：顺序结构、选择结构、循环结构；
（1）表达式
前缀表达式：
也被称为波兰表示法，其特点是将操作符置于操作数之前，如 + - 3 2 1 ；
中缀表达式：
即我们常用的表示方法，如 3 - 2 + 1 ；
后缀表达式：
又被称为逆波兰法，其特点是将操作符置于操作数之后，如 3 2 - 1 + ；
（2）操作符的优先级
在一个表达式中可能包含多个有不同运算符连接起来的、具有不同数据类型的数据对象；
由于表达式有多种运算，不同的结合顺序可能得出不同结果甚至出现错误运算错误，因为当表达式中含多种运算时，必须按一定顺序进行结合，才能保证运算的合理性和结果的正确性、唯一性。
优先级从上到下依次递减，最上面具有最高的优先级，逗号操作符具有最低的优先级。表达式的结合次序取决于表达式中各种运算符的优先级。优先级高的运算符先结合，优先级低的运算符后结合，同一行中的运算符的优先级相同；
（3）过程控制
参数传递的方式：
传值调用 --- 数据的传递是单向的
引用调用（地址调用）--- 数据的传递是双向的