在学习和研究C++的编译器的工作原理时，一定要学习和了解的就是如何将一串表达式运算转换为对应的汇编以及在转换过程中，是否能进行优化以使得要么满足空间的需求，要么满足速度的需求
...

术语

状态机

有限状态机，又称为有限状态自动机，简称为状态机。它表示的是有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。状态机的全称是有限状态自动机，自动两个字也是包含重要含义的。给定一个状态机，同时给定它的当前状态以及输入，那么输出状态是可以明确的计算出来的。

状态存储关于过去的信息，就是说：它反映从系统开始到现在时刻的输入变化。转移指示状态变更，并且用必须满足确使转移发生的条件来描述它。动作是在给定时刻要进行的活动的描述，通过修改某一个状态，就会影响整个系统的状态。

状态机的本质其实就是一个大大的switch-case

自动机

对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态)。

通过扫描，根据状态的改变来确定究竟是哪个条件成立，从而切换当前的状态，来决定当前如何做。

本质上就是一个循环，一直往前扫描，由于有些状态会影响系统的行为。当这些状态发生或改变时，就可以确定出哪个条件成立，根据这个条件去做相应状态的操作。

生成运算表达式的汇编语句

对于自动机和状态机的理解有助于对编译原理的理解，因为编译原理大量的应用到了上述的计算模型。

步骤

1. 编译器扫描字符串，生成对应规则的运算的二叉树
2. 然后先序遍历当前的这颗二叉树，得到相应的遍历结果
3. 然后扫描当前的遍历结果，对应生成相应的函数调用（因为是一一对应的）
4. 最后生成对应的汇编结果。

暴力生成运算二叉树的方法

1. 第一次扫描确定哪些运算，并排列出运算符的优先级。
2. 依次扫描优先级运算符，生成对应的子树
3. 最后拼接成一个完整的运算二叉树

上述操作，生成二叉树的时间复杂度相对较高。

表达式的分类

表达式可以分为：中缀表达式、前缀表达式和后缀表达式。中缀，前缀和后缀表达式分别对应于运算表达式的二叉树的遍历方式（先序、中序、后序），它们的具体形式如下：

• 中缀表达式，指的是形如a + b * c - d / e的表达式，也是我们生活中所使用的表达式的表示方法。

• 前缀表达式，也叫波兰表达式（C风格或者汇编风格）。其特点是要进行的操作在前、操作数在后，如： ADD EAX, EBX; add(a, b) 。对于前缀表达式，其和C调用函数的顺序是一致的，如函数调用sub(add(a, mul(b, c)), div(d, e))，其对应的前缀表达式是-+a*bc/de。

• 后缀表达式，又称为逆波兰表达式。它的特点是操作数在前、操作符在后，与中国古人的读法一致。举个例子，古人读的一个四则运算的式子：a与bc之积求和与de之商求差对应的就是一个后缀表达式，这个后缀表达式就是：abc*+de/-

编译优化方法

常用的优化方法有：

• 常量折叠
• 常量传播
• 复写传播
• 公共表达式

下面是对这些优化方法的分类解释

分类解释

常量折叠

6 + 9 * 3 = 33

当参加运算的都是常量，可以在编译期间内直接求得结果的这类表达式，则就在编译期间直接求值，然后参与后续的编译工作，不为常量与常量的计算产生相应的汇编代码。

常量传播

当一个变量等于一个常量，即：变量是一个常量值时，当我们引用这个变量的过程中，如果这个变量没有发生修改，则和引用这个常量一样

复写传播

与常量传播差不多，只不过对象变为了变量。从而可以减少变量的使用

复写传播可以传播一个变量或者一个表达式。

公共表达式

a = b * 9 + s;
c = b * 9 + d

-> 
t = b * 9;
a = t + s;
c = t + d;

由于两个表达式中有公共部分，则将这个公共部分提取出来，找一个地方暂时存放，然后转为上述表达式。

这个是减少运算了，但是增加了变量；与复写传播不同，是空间换时间的操作**
**

优化原则

优化原则是大事化小，小事化了，遵循：

1. 在有限的行数内考虑优化
2. 每次行数加一，循环此过程，直到源码结束
3. 如果源码发生了修改（因为优化），回到第1步
4. 优化完成

上述套路，称为窥孔优化。

传播的上界和下界是对同一个变量两次写入之间进行传播的，不能传播错。

一个变量，如果不做传参、不做运算、不做返回值，则等于没有使用这个变量，可以删除。

窥孔优化还可以进一步为：

while (逐步扩大行数)
{
    	在有限的行数内考虑优化;
        每次行数加一，循环此过程，直到源码结束;
        如果源码发生了修改（因为优化），回到第1步;
        优化完成;
}

以上讨论是基于能否搞定代码优化问题，而不是具体细节怎么做。

优化时，可以把减法，优化为补码形式，并修改减法变为加法。

示例代码

int a = 9;
int b = a + 1;

printf("%d\n", a + b * 3);

三操作数乘法：操作数二与操作数三相乘，结果写到操作数一。

参考资料

wikipeida：有限状态自动机