1

我有一个简单的操作，如下所示：

k + 1

它的 IR 树表示是什么？
到目前为止，我想出了：

BINOP(+, MEM(NAME(k)), CONST(1))

但我不确定我是否需要 MEM 作为 NAME。欢迎任何帮助。

我们使用的符号与此 pdf 中的符号完全相同：http: //www.computing.dcu.ie/~hamilton/teaching/CA449/notes/translate.pdf

它来自java书中的现代编译器实现。

4

2 回答 2

2

好吧，这实际上取决于您的 IR 是如何表示的。此外，正如mrjoltcola所指出的，您的建议看起来更像是 AST（抽象语法树）。AST 级别更高，通常是直接从源代码生成的树结构。IR 通常更简单，更底层（代码通常表示为简单指令列表，而不是表达式树）。AST 通常高度特定于编译器。IR 通常独立于编译器和/或语言（参见例如LLVM）。

如果你要用文本来表示它，我认为

+(k,1)

会更简单，因为无论如何您都将需要一个相当复杂的词法分析器/解析器，这对人类来说会更具可读性（尽管对计算机来说可读性会降低一些）。不需要像MEMor之类的东西NAME，因为在这种情况下，标识符显然是变量访问（尽管它确实取决于编译器的语言和结构）。不过，我绝对不会使用类似的东西BINOP，因为它实际上只会使代码复杂化（您仍然必须将加法与其他二进制操作分开处理）。

如果您只是将其保存在内存中，则取决于语言。在 Haskell 中，我会做这样的事情：

data Expr = Const Int | Variable String | Add Expr Expr | ...

然后你的例子是：

Add (Variable "k") (Const 1)

在 C++/C#/Java 中，您可能会使用类来模拟代数数据类型。

例如，在粗略的 C++-ish 伪代码中：

class Expr {};
class Const : Expr {int v; Const(int v) : v(v) {}};
class Variable : Expr {string n; Variable(string n) : n(n) {}};
class Add : Expr {Expr a, b; Add(Expr a, Expr b) : a(a), b(b) {}};

...

Add(Variable("k"), Const(1))
于 2010-03-30T22:02:38.783 回答
1

我唯一能做的就是阅读他的 IR 树语言的作者（Appel）规则。

对于语法：

  <ADDEXPR> ::= <EXPR> + <EXPR>

  <EXPR> ::= IDENTIFIER
           | LITERAL

AST 树可能是：

  BINOPEXPR(+, EXPR(IDENTIFIER(k)), EXPR(LITERAL(1)))

或者可能包括 IdentifierExpression 和 LiteralExpression，所以它可能是：

  BINOPEXPR(+, IDENT_EXPR(k), LITERAL_EXPR(1))

但是 AST 和 IR 树是不同的东西。所以根据 Appel 的书，在 C 版本的第 7.1 节中：

NAME(n) = Sumbolic 常数 n 对应于汇编语言标签。

MEM(e) = 从地址 e 开始的 wordSize 字节的内存内容。当 MEM() 用作 MOVE() 的左孩子时，它表示“存储”，但在其他任何地方都表示“获取”。

LABEL(n) = 将名称 n 的常量值定义为当前机器码地址。这就像汇编语言中的标签定义。值 NAME(n) 可能是跳转、调用等的目标。

鉴于他的规则，NAME() 不是你想要的变量 k，名称用于代码标签。

我根据阅读他的猜测是如果 k 是一个变量，在这种情况下它是一个 r 值，那么您只需使用 MEM(e) 但 e 可以是局部变量（在本地堆栈帧中），或者全局变量，甚至是临时变量。所以“k + 1”的翻译将取决于“k”的分配位置。如果它在本地堆栈帧中，那么 k 是：

MEM(BINOP(+, TEMP fp, CONST (address of k)))

所以 k + 1 将是：

BINOP(+, MEM(BINOP(+, TEMP fp, CONST (address of k))), 1)

因此，您需要清楚如何为变量分配存储空间。这将在标识符的符号表中。

我至少有 20 本编译器书籍，老实说，我发现 Appel 的书籍令人困惑，而且在某些方面过于简短。他做出了学生不遵循的概念飞跃，并且可以在某些地方使用更多的细节。因为我从来没有真正实现过 IR 树，（我总是写一个文本中间语言，它支持声明不同范围的变量和符号临时变量）我不能确定他的意思，所以我建议与你的教授确认因为他可能以前用这本书教过，并且可能更了解它。

希望有帮助。

于 2010-03-30T22:09:30.883 回答