在编译器理论中,一个表达式是使用一棵树来表示的,其实根为运算符,子节点为分解出的子表达式。在实际编译时,一个运算符只有当它所有子节点代表的表达式都求出以后,它才能够做相应的运算。
编译的时候,内存里有一种特殊的储存器“Register”,如果将得出的表达式储存到Register中,可以加快存取速度,但是由于Register数量有限,不能存入的表达式就只好用主Memory来存储,这样的话就会造成时间上的浪费。所以决定如何使用Register可以提高编译的效率。
具体的编译过程如下:
1. 对于一个非叶子节点,选任意一个子节点,进行运算(递归)
2. 计算完以后,对于计算出的数值,可以选择存入Register或者存入主Memory。
a) 若存入Register,那么存取时间不计,但是在计算其他子节点表达式时,这个Register是不可用的。
b) 若存入主Memory,存入需要Cs的时间,以后如果要调用这个值,还需要Cl的时间来调用。
3.重新返回1,直到所有的子节点表达式都处理完毕。
4.这个时候,将所有存入主Memory的数值从主Memory中读入到Register中,一个数值占用一个Register。
5.将所有Register中的数值按照根节点代表的运算符进行运算,得出结果。
6.然后将所有使用到的Register清空。
所有的叶子节点代表的是数值,且必须从主Memory中读入,每种运算符计算时使用的时间各有不同。现要你决定编译的顺序和Register的使用,使得总运算时间最少。