1

私は次のような簡単な操作をします：

k + 1

それのIRツリー表現は何でしょうか？
これまでのところ私は思いついた：

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

しかし、NAMEにMEMが必要かどうかはわかりません。どんな助けでも歓迎します。

私たちが使用する表記法は、この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)

とにかくかなり複雑なレクサー/パーサーが必要になるため、より単純になります。これは、人間にとってはもう少し読みやすいでしょう（ただし、コンピューターにとっては少し読みにくいですが）。MEMまたはのようなものを持つ必要はありませんNAME。その場合の識別子は明らかに変数アクセスになるためです (ただし、言語とコンパイラの構造に依存します)。ただし、実際にはコードを複雑にするだけなので、絶対に使用しませんBINOP(他のバイナリ操作とは別に加算を処理する必要があります)。

記憶にとどめているだけなら、それは言語に依存します。Haskell では、次のようにします。

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

そして、あなたの例は次のようになります：

Add (Variable "k") (Const 1)

C++/C#/Java では、おそらくクラスを使用して代数データ型をエミュレートします。

たとえば、ラフな C++ 風の疑似コードでは次のようになります。

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

私にできることは、著者 (Appel) の IR ツリー言語のルールを読むことだけです。

文法の場合:

  <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) = アセンブリ言語ラベルに対応するサンボリック定数 n。

MEM(e) = アドレス e から始まるメモリの wordSize バイトの内容。MEM() が MOVE() の左の子として使用される場合、それは「ストア」を意味しますが、それ以外の場合は「フェッチ」を意味します。

LABEL(n) = 名前 n の定数値を現在のマシン コード アドレスとして定義します。これは、アセンブリ言語でのラベル定義のようなものです。値 NAME(n) は、ジャンプ、呼び出しなどのターゲットになる場合があります。

彼のルールを考えると、NAME() は変数 k に必要なものではなく、name はコード ラベルに使用されます。

彼の読みに基づく私の推測では、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 に答える