stage4

homework › 编原
,

stage-4

郭高旭 ggx21@mails.tsinghua.edu.cn 2021010803

实验内容

step7

支持条件语句，包括 if 语句和条件表达式（又称三元/三目表达式，ternary expression）。

由于if代码和条件表达式的前后端代码在框架中均已提供，所以这里只需要考虑条件表达式的tacgen。

由于这也是一个expression，所以模拟二元表达式以及if语句，代码内容如下

这段代码是一个Python函数，用于将条件表达式转换为TAC（Three-Address Code）。它的主要步骤如下：

  1. 创建一个临时变量tempVal来存储条件表达式的结果。

  2. 生成条件部分的TAC代码，并将结果存储在tempVal中。

  3. 创建两个标签，skipLabel和exitLabel，用于控制流跳转。

  4. 如果条件成立，执行expr.then的TAC代码，然后将结果赋给tempVal。

  5. 跳转到exitLabel以避免执行expr.otherwise的TAC代码。

  6. 如果条件不成立，执行expr.otherwise的TAC代码，然后将结果赋给tempVal。

  7. 最后，将tempVal存储在expr中以表示条件表达式的结果。

step8

step8可以看作是对step9的准备，让我们上手整个编译流程，包括之前没有太修改过的lex&parse，增加对循环语句，以及 break/continue 的支持。

前端

按照语法规范给出for，while，continue的实现，如下例（while，break已给出，continue简单）

lex
1
2
3
4
5
6
7
8
9
10
11
# Reserved keywords
reserved = {
    "return": "Return",
    "int": "Int",
    "if": "If",
    "else": "Else",
    "while": "While",
    "break": "Break",
    "continue": "Continue",
    "for": "For",
}
parse
1
2
3
4
5
6
7
8
9
def p_for(p):
    """
    statement_matched : For LParen opt_expression Semi opt_expression Semi opt_expression RParen statement_matched
                        | For LParen declaration Semi opt_expression Semi opt_expression RParen statement_matched
    statement_unmatched : For LParen opt_expression Semi opt_expression Semi opt_expression RParen statement_unmatched
                        | For LParen declaration Semi opt_expression Semi opt_expression RParen statement_unmatched

    """
    p[0] = For(p[3], p[5], p[7], p[9])

并在tree中相应设置好上述语法结点

语义检查

完成 namer.py 中的 visitFor ， visitWhile ， visitContinue 和 visitBreak 方法

  • 对于visitContinue 和 visitBreak，要确定其位于的scope在循环内，这可以通过在visitFor和while中进入循环体前标记此Scope类型为LOOP实现

  • visitFor:

按照提示,生成代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def visitFor(self, stmt: For, ctx: ScopeStack) -> None:
  
# 1. Open a local scope for stmt.init.
# 2. Visit stmt.init, stmt.cond, stmt.update.
# 3. Open a loop in ctx (for validity checking of break/continue)
# 4. Visit body of the loop.
# 5. Close the loop and the local scope.
  
    new_scope = Scope(ScopeKind.LOCAL)
    ctx.push(new_scope)
    stmt.init.accept(self, ctx)
    stmt.cond.accept(self, ctx)
    stmt.update.accept(self, ctx)
    loop_scope = Scope(ScopeKind.LOOP)
    loop_scope.inLoop = True
    ctx.push(loop_scope)
    stmt.body.accept(self, ctx)
    ctx.pop()
    ctx.pop()

中端,后端

框架均已提供

思考题

step7

Q1:

实验框架与你使用语言的框架里是如何处理悬吊 else 问题的?

A1:

实验框架

ply在处理移入-归约冲突时，默认移入：具体来说没有 else分支的 if 语句只能由 statement unmatched 产生，而statement unmatched 只能出现在if的else 分支里。

通过这样的设计，悬挂 else 问题得以解决。当遇到没有 else 分支的 if 语句时，它会被解释为 If 对象，其中 Else 分支为 None。在 AST 中，这种情况明确地表示了这个 if 语句是没有 else 分支的。

在使用这个 AST 进行后续处理时，你可以检查 If 对象的 else_branch 是否为 None，从而确定是否存在 else 分支。这种明确的表示方式有助于避免悬挂 else 问题。

Python:

Python使用缩进来表示代码块，因此在Python中，if和else语句的匹配是根据缩进来实现的。Python的规则如下：

1
2
3
4
5
6
if condition:
    # if块
    # ...
else:
    # else块
    # ...

在Python中，else语句与最近的未匹配的相同缩进的if语句相关联，而不是通过括号或其他方式。这确保了else与最近的if一起使用。

C语言:

在C语言中，else与最近的if语句相关联，这是通过花括号来实现的，它们定义了代码块的范围。通常，C语言的规则如下：

1
2
3
4
5
6
7
if (condition) {
    // if块
    // ...
} else {
    // else块
    // ...
}

在C语言中，花括号{}用于明确定义代码块的开始和结束，因此else会与最近的if语句匹配，这就避免了悬挂else问题。

Q2:

如果要求条件表达式不短路，在你的实现中该做何种修改？

A2

在tacgen的def visitCondExpr函数中:

将 then.accept 与 otherwise.accept 放在mv.visitCondBranch之前,(此时不能再给then和otherwise的值设置到同一个temp里)

step8

Q1:

将循环语句翻译成 IR 有许多可行的翻译方法，例如 while 循环可以有以下两种翻译方式：

第一种（即实验指导中的翻译方式）：

  • label BEGINLOOP_LABEL：开始下一轮迭代

  • cond 的 IR

  • beqz BREAK_LABEL：条件不满足就终止循环

  • body 的 IR

  • label CONTINUE_LABEL：continue 跳到这

  • br BEGINLOOP_LABEL：本轮迭代完成

  • label BREAK_LABEL：条件不满足，或者 break 语句都会跳到这儿

第二种：

  • cond 的 IR

  • beqz BREAK_LABEL：条件不满足就终止循环

  • label BEGINLOOP_LABEL：开始下一轮迭代

  • body 的 IR

  • label CONTINUE_LABEL：continue 跳到这

  • cond 的 IR

  • bnez BEGINLOOP_LABEL：本轮迭代完成，条件满足时进行下一次迭代

  • label BREAK_LABEL：条件不满足，或者 break 语句都会跳到这儿

从执行的指令的条数这个角度（label 不算做指令，假设循环体至少执行了一次），请评价这两种翻译方式哪一种更好？

A1:

第二种翻译方式更好

循环体执行了一次都是经历了相同的body 的 IR与cond 的 IR.但第一种方式循环体执行了一次后判断是否终止时总是需要两条指令:br BEGINLOOP_LABEL与beqz BREAK_LABEL;但是第二种方式bnez BEGINLOOP_LABEL在条件不满足时直接退出循环,只需要一条指令;而条件满足时beqz BREAK_LABEL,bnez BEGINLOOP_LABEL需要两条指令.

故第二种方式的指令数总是较小

Q2:

我们目前的 TAC IR 中条件分支指令采用了单分支目标（标签）的设计，即该指令的操作数中只有一个是标签；如果相应的分支条件不满足，则执行流会继续向下执行。在其它 IR 中存在双目标分支（标签）的条件分支指令，其形式如下：

1
br cond, false_target, true_target

其中cond是一个临时变量，false_target和true_target是标签。其语义为：如果cond的值为0（假），则跳转到false_target处；若cond非0（真），则跳转到true_target处。它与我们的条件分支指令的区别在于执行流总是会跳转到两个标签中的一个。

你认为中间表示的哪种条件分支指令设计（单目标 vs 双目标）更合理？为什么？（言之有理即可）

A2:

我认为单目标指令更合理,原因如下

  1. 更贴近目标语言(riscvasm)

  2. 减少悬挂else问题:不需要担心其中一个target不存在

  3. 简化了控制流：单目标条件分支指令可以更简单地表示控制流的分支，减少了语义上的复杂性。这使得中间表示更容易理解和优化。



本文总阅读量次