阅读更多
1 控制流语句及其SDT
1.1 控制流语句的基本文法
$$\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}$$1.2 控制流语句的代码结构
布尔表达式$B$被翻译成由跳转指令构成的跳转代码，非终结符$B$包含如下继承属性
- $S.next$：是一个地址，该地址中存放了紧跟在$S$代码之后的指令(S的后继指令)的标号
- $B.true$：是一个地址，该地址中存放了当$B$为真时控制流转向的指令的标号
- $B.false$：是一个地址，该地址中存放了当$B$为假时控制流转向的指令的标号
- 用指令的标号标识一条三地址指令
1.3 控制流语句的语义动作
- $newlabel()$：生成一个用于存放标号的新的临时变量$L$，返回变量地址
- $label(L)$：将下一条三地址指令的标号赋给$L$
1.4 控制流语句的SDT
1.4.1 $if-then-else$语句的SDT
1.4.2 $if-then$语句的SDT
1.4.3 $while-do$语句的SDT
2 布尔表达式及其SDT
2.1 布尔表达式的基本文法
$$\begin{split} B &\to B\;or\;B \\ &|\;B\;and\;B \\ &|\;not\;B \\ &|\;(B)\; \\ &|\;E\;relop\;E \\ &|\;true \\ &|\;false \end{split}$$优先级：not > and > or
relop（关系运算符）：<, <=, >, >=，==, !=
在跳转代码中，逻辑运算符&&、|| 和!被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的
2.2 布尔表达式的SDT
2.2.1 $B \to B_1\;or\;B_2$ 的SDT
2.2.2 $B \to B_1\;and\;B_2$ 的SDT
3 控制流翻译的例子
3.1 控制流语句的SDT
3.2 SDT的通用实现方法
任何SDT都可以通过下面的方法实现：首先建立一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作
- 首先生成$L_1$用于存放$S.next$
- 执行完$S$后，才能确定$L_1$的值
- 生成$L_2$用于存放$S.begin$
- 确定$S.begin$的值，即$L_2=1$，即下一条三地址指令的标号
- 生成$L_3$用于存放$B.true$
- 将$B.false$绑定为$S.next$（这里用到绑定一词，当$S.next$最终确定后，$B.false$才会确定，因此这里只是绑定关系，而非最终确定$B.false$的值）
- 将$B$生成两条三地址指令
- $1.\;if\;a < b\;goto\;L_3$
- $2.\;goto\;L_1$
- 确定$B.true$的值，即$L_3=3$，即下一条三地址指令的标号
- 将$S_3.next$绑定为$S.begin$
- $S_3$展开为$if\;B\;then\;S_1\;else\;S_2$
- 生成$L_4$用于存放$B1.true$
- 生成$L_5$用于存放$B1.false$
- 将$B_1$生成两条三地址指令
- $3.\;if\;c < d\;goto\;L_4$
- $4.\;goto\;L_5$
- 确定$B1.true$的值，即$L_4=5$，即下一条三地址指令的标号
- 将$S_1.next$绑定为$S_3.next$
- 将$S_1$生成三地址指令
- $5.\;t_1 = y+z$
- $6.\;x = t_1$
- 生成三地址指令
- $7.\;goto\;S_3.next$，即$7.\;goto\;S.begin$
- 确定$B1.false$的值，为即$L_5=8$，即下一条三地址指令的标号
- 将$S_2.next$绑定为$S_3.next$
- 将$S_2$生成三地址指令
- $8.\;t_2 = y-z$
- $9.\;x = t_2$
- 生成三地址指令
- $10.\;goto\;S.begin$
- 确定$S.next$的值，即$L_1=11$，即下一条三地址指令的标号
4 参考
- 《MOOC-编译原理-陈鄞》