本篇来描述一下类似 a + b + c 得运算内容。

同样,本篇只是说明一个可用于实现得概念模型, 并没有提供什么优化技巧。

详细内容

上一节我们讨论了两元运算, 现在我们讨论一下存在更多元素得运算表达式。

下面来看一段代码。

a = 1;
b = 2;
c = 3;

d = a + b + c;
e = a - b - c;
f = a * b + c;
g = a + b * c;

h = a + b + c + a + c;
i = a + b * c + a ;

基本逻辑

上面得例子在运算得时候至少存在3个元素,这在实现上并不需要修改上节所实现得逻辑,而是需要在生成抽象语法树(AST)得地方下功夫。

先来看一下表达式 d = a + b + c; 得计算过程。

  1. 计算 a + b 得值 并保存, 假设为 t1
  2. 计算 t1 + c 得值并保存, 假设为 t2
  3. t2得值 赋值给变量d

看到了吗, 这里得核心逻辑就是拆分, 把多个元素拆成二元运算来分别计算。

下面再来看一下表达式g = a + b * c; 得计算过程

  1. 计算b * c 得值 并保存, 假设为t1
  2. 计算a + t1 得值 并保存, 假设为t2
  3. t2得值, 赋值给变量d

这里和上面得例子, 有一点不同得是需要先计算b*c ,因为乘法得优先级比加法更高。

如果读者使用了 yacc 做AST(抽象语法树,下面都简称为AST)得生成,那么在指定了符号得优先级之后,yacc会自动处理这种问题。

其他的AST生成工具,应该也有类似得功能, 如果是自行实现AST生成,那么就需要注意这方面得问题了。

产生的AST结构大致如下图所示。 (点击可以查看大图)

AST
AST

要计算最顶层得+号,需要先计算他得子节点, 按照这个逻辑就可以实现符号优先级了。

如果生成字节码得话

字节码就是指令序列,当前小节仅是提供一个思路。

根据优先级 按序生成即可。

下面给一段示例:

// 本部分采用基于栈得指令来说明

// a + b + c
push a            // 将变量a得值压栈
push b            // 将变量b得值压栈
add               // 取出栈顶两个元素进行相加, 结果放回栈顶
push c            // 将变量c得值压栈
add               // 同上
                  // 此时栈顶就一个元素了,该元素是运算结果
									
// a + b * c 
                  // 此处使用新的栈
push b            // 将变量b得值压栈
push c            // 将变量c得值压栈
mul               // 取出栈顶两个元素进行相乘, 结果放回栈顶
push a            // 将变量a得值压栈
add               // 取出栈顶两个元素进行相加, 结果放回栈顶
                  // 此时栈顶就一个元素了,该元素是运算结果

读者可能无法理解这部分内容,没关系,后面会懂得。