回填 (Backpatching)
基本思想：生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号。
非终结符B的综合属性
B.truelist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号。
B.falselist：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号。
函数
为了处理跳转指令的列表我们构造了三个函数
-
makelist(i)
创建一个只包含i的列表，i是跳转指令的标号，函数返回指向新创建的列表的指针。（注：i对应的跳转指令一般没有包含目标标号，需要被回填） -
merge(p1, p2)
将p1和p2指向的列表进行合并，返回指向合并后的列表的指针。 -
backpatch(p, i)
将i作为目标标号插入到p所指列表中的各指令中
布尔表达式的回填
0.png
上述的布尔表达式将被翻译成两条跳转指令。两条跳转指令的标号都不填写因为这两条跳转指令的标号都在等待回填，因此我们要把它放到相应的列表中。
第一条跳转指令的目标标号是B的真出口，因此我们把它放到B.truelist中。调用makelist函数生成一个只包含nextquad的列表，并把这个列表的指针赋值给truelist，这里的nextquad是指即将生成的下一条指令的标号，即gen('if' E1.addr relop E2.addr'goto_')这条指令的标号。
第二条跳转指令的目标标号是B的假出口，因此把这条跳转指令存放到B.falselist中。因此我们调用makelist函数生成一个只包含nextquad+1这样一个标号的列表，nextquad+1标号就是gen('goto_')这条指令的标号。
这样的话我们就将这两条指令分别放入到B.truelist和B.falselist中。
问：list中存的是对应跳转指令的标号？
1.png
当B定义为true时，此时可以确定布尔表达式的值为真，生成一条跳转到B的真出口的一条指令。由于此真出口的标号不能确定有待回填，我们把它放入到B.truelist中。
2.png
当B定义为false时，此时可以确定布尔表达式的值为假，生成一条跳转到B的假出口的一条指令。由于此真出口的标号不能确定有待回填，我们把它放入到B.falselist中。
3.png
对B的翻译与其对应的子表达式B1的翻译是相同的，因此B的属性值等于B1的属性值。
4.png
B的值与B1的值正好相反，因此将两个非终结符的属性进行对调。
5.png
B1.truelist中的这些指令都要跳转到B1的真出口，当B1为真的时候整个表达式的值就是为真的，因此B1的真出口就是B的真出口。要跳转到B1的真出口就是跳转到B的真出口，因此B1.truelist中的指令都要放到B.truelist中。
B2.truelist的指令都要跳转到真出口，当B2为真时整个表达式的值也为真，因此B2的真出口就是B的真出口。要跳转到B2的真出口就是要跳转到B的真出口，因此B2.truelist中的指令都要放到B.truelist中。
B1.falselist中的指令它们都是要跳转到B1的假出口，当B1的值为假的时候我们要进一步判断B2的值，因此B1的假出口就是B2的第一条指令，因此B1.falselist中的指令都要跳转到B2的第一条指令。
B2.falselist中的指令都要跳转到B2的假出口，当B2的值为假的时候那么整个布尔表达式的值也是假的。因此B2的假出口就是B的假出口，要跳转到B2的假出口也就是要跳转到B的假出口。B2.falselist中的指令都要放置到B.falselist中。
根据此示意图可以看出，在分析B2之前，要用B2的第一条指令的标号来回填B1.falselist中的各条指令。当然我们可以记录下B2的第一条指令的标号在归约时完成此回填动作。为了记下B2第一条指令的标号我们在非终结符B2之前插入一个标记非终结符M。与M关联的语义动作它的任务就是记录下B2的第一条语义动作的标号。我们给M设置一个综合属性quad,M.quad等于下一条指令的标号。因为我们把M放在B2之前，因此M.quad记录的是第二条指令的标号。根据翻译方案示意图，我们要用M.quad来回填B1.falselist中的各条指令，因此调用backpatch用M.quad回填B1.falselist中的各条属性。B.truelist是由B1.truelist和B2.truelist合并而成的，因此我们调用merge函数将B1.truelist和B2.truelist进行合并，将合并后的指针赋值给B.truelist。
6.png
例子
0.png
注：因为这里我们定义的都是综合属性，从左向右扫描输入串。makelist函数生成一个只包含下一条指令的列表，并把指针赋值给B.trulist。我们假设下一条指令从100开始。gen(‘if ’ E 1 .addr relop E 2 .addr ‘goto _’)中E1.address等于a，relop就是小于号，E2.address等于b，引号中的字符串按字面值传递。下划线表示待回填的目标标号。
1.png
注：将栈顶中的空串归约成一个标记非终结符M
2.png
3.png
注：有四条指令是等待回填的，在B的truelist中有两条指令100和104，当B的真出口确定以后我们将用B的真出口的标号这两条指令。同理当B的假出口确定以后将会用B的假出口的标号回填此两条指令。
网友评论