Liuye Notebook
0%

编译原理-中间代码生成4

发表于 更新于 分类于 阅读次数： Valine：

阅读更多

1 布尔表达式的回填

1.1 回填

基本思想：生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号

1.2 非终结符$B$的综合属性

  1. $B.truelist$：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为真时控制流应该转向的指令的标号
  2. $B.falselist$：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是当B为假时控制流应该转向的指令的标号

1.3 函数

  1. $makelist(i)$：创建一个只包含$i$的列表，$i$是跳转指令的标号，函数返回指向新创建的列表的指针
  2. $merge(p_1, p_2)$：将$p_1$和$p_2$指向的列表进行合并，返回指向合并后的列表的指针
  3. $backpatch(p, i)$：将$i$作为目标标号插入到$p$所指列表中的各指令中

1.4 布尔表达式的回填

1.4.1 $B \to E_1\;relop\;E_2$

fig1

1.4.2 $B \to true$

fig2

1.4.3 $B \to false$

fig3

1.4.4 $B \to (B_1)$

fig4

1.4.5 $B \to not B_1$

fig5

1.4.6 $B \to B_1\;or\;B_2$

fig6

1.4.7 $B \to B_1\;and\;B_2$

fig7

1.5 例子

输入的布尔表达式如下（假设下一条指令的编号是100）

$$a < b\;or\;c < d\;and\;e < f$$
  • 首先通过产生式$B \to E_1\;relop\;E_2$，将输入符号$a < b$进行归约，然后执行该产生式的语义动作
    • 为终结符$B$生成一个$B.truelist$队列，将放编号为100的$goto$指令压入该队列
    • 为终结符$B$生成一个$B.falselist$队列，将放编号为101的$goto$指令压入该队列
    • 产生一条条件跳转指令$\;\;if\;a < b\;goto\;\_\;\;$，编号为100
    • 产生一条跳转指令$\;\;goto\;\_\;\;$，编号为101

fig8

  • 同理，通过产生式$B \to E_1\;relop\;E_2$，将输入符号$c < d$进行归约，然后执行该产生式的语义动作
    • 为终结符$B$生成一个$B.truelist$队列，将放编号为102的$goto$指令压入该队列
    • 为终结符$B$生成一个$B.falselist$队列，将放编号为103的$goto$指令压入该队列
    • 产生一条条件跳转指令$\;\;if\;c < d\;goto\;\_\;\;$，编号为102
    • 产生一条跳转指令$\;\;goto\;\_\;\;$，编号为103

fig9

  • 由于$and$的运算优先级大于$or$，于是移入而不是归约。然后通过产生式$B \to E_1\;relop\;E_2$，将输入符号$e < f$进行归约，然后执行该产生式的语义动作
    • 为终结符$B$生成一个$B.truelist$队列，将放编号为104的$goto$指令压入该队列
    • 为终结符$B$生成一个$B.falselist$队列，将放编号为105的$goto$指令压入该队列
    • 产生一条条件跳转指令$\;\;if\;e < f\;goto\;\_\;\;$，编号为104
    • 产生一条跳转指令$\;\;goto\;\_\;\;$，编号为105
  • 然后通过产生式$B \to B_1\;and\;M\;B_2$，继续进行归约，然后执行该产生式的语义动作
    • 用$M.quad$回填$B_1.truelist$队列中所有$goto$指令的跳转目标标号
    • $B.truelist=B_2.truelist$
    • 将$B_1.falselist$与$B_2.falselist$合并，作为$B.falselist$

fig10

  • 然后通过产生式$B \to B_1\;or\;M\;B_2$，继续进行归约，然后执行该产生式的语义动作
    • 用$M.quad$回填$B_1.falselist$队列中所有$goto$指令的跳转目标标号
    • 将$B_1.truelist$与$B_2.truelist$合并，作为$B.truelist$
    • $B.falselist=B_2.falselist$

fig11

2 控制流语句的回填

回顾一下控制流语句的文法

$$\begin{split} P &\to S \\ S &\to S_1S_2 \\ S &\to id = E; | L = E; \\ S &\to\;if\;B\;then \;S_1\;|\;if\;B\;then\;S_1\;else\;S_2\;|\;while\;B\;do\;S_1 \end{split}$$

2.1 非终结符$S$的综合属性

  1. $S.nextlist$：指向一个包含跳转指令的列表，这些指令最终获得的目标标号就是按照运行顺序紧跟在S代码之后的指令的标号

2.2 控制流语句的回填

2.2.1 $S \to if\;B\;then\;S_1$

  • 用$M.quad$来记录$S_1$的第一条指令，用于回填$B.truelist$

fig12

2.2.2 $S \to if\;B\;then\;S_1\;else\;S_2$

  • 用$M_1.quad$来记录$S_1$的第一条指令，用于回填$B.truelist$
  • 用$M_2.quad$来记录$S_2$的第一条指令，用于回填$B.falselist$
  • 用$N$来产生$S_1$之后的跳转指令

fig13

2.2.3 $S \to while\;B\;do\;S_1$

  • 用$M_1.quad$来记录$while$循环的的第一条指令，用于回填$S_1.nextlist$
  • 用$M_2.quad$来记录$S_1$的第一条指令，用于回填$B.truelist$

fig14

2.2.4 $S \to S_1S_2$

  • 用$M.quad$来记录$S_2$的第一条指令，用于回填$S_1.nextlist$

fig15

2.2.5 $S \to id = E; | L = E;$

fig16

2.3 例子

有如下程序片段

1
2
3
4
5
while a < b do
    if c < 5 then
        while x > y do z = x + 1;
    else
        x = y;

采用自底向上的分析法，这里直接给出了整棵语法分析树。以从左到右的深度优先顺序来查看所有叶节点，然后按照相应的产生式执行相关的语义动作，不再仔细分析

fig17

3 switch语句的翻译

3.1 方式1

fig18

fig19

3.2 方式2

fig20

fig21

3.3 增加一种$case$指令

指令$case\;t\;V_iL_i$和$if\;t = V_i\;goto\;L_i$的含义相同，但是$case$指令更加容易被最终的代码生成器探测到，从而对这些指令进行特殊处理

fig22

4 过程调用语句的翻译

过程调用翻译的文法如下

$$\begin{split} S &\to call\;id\;(Elist) \\ Elist &\to Elist, E \\ Elist &\to E \end{split}$$

4.1 过程调用语句的代码结构

需要一个队列$q$存放$E_1.addr 、E_2.addr、...、E_n.addr$

fig23

4.2 过程调用语句的SDD

fig24

4.3 例子

翻译如下函数调用

$$f(b*c-1, x+y, x, y)$$

fig25

5 参考

  • 《MOOC-编译原理-陈鄞》