2010-03-30 75 views
1

的IR樹表示我有一個簡單的操作,像這樣:二元運算

k + 1 

什麼是它的IR樹表示?
到目前爲止,我想出了:

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

,但我不知道如果我需要的MEM姓名或不。任何幫助歡迎。

我們所使用的符號是完全一樣的注意事項的: http://www.computing.dcu.ie/~hamilton/teaching/CA449/notes/translate.pdf

距離modern compiler implementation in java書。

+0

這是一本書或其他東西的練習嗎?我問這是因爲我想知道你在哪裏得到這個符號。 – SamB 2010-03-30 22:08:34

+0

是,已更新的問題。 – drozzy 2010-03-31 00:43:08

+0

不確定的Java頁碼,我有本書的「C」版本。第7章「中間表示樹」7.1將NAME(n)定義爲對應於彙編語言標籤。我將它讀作代碼偏移標籤(跳轉,分支,調用)。我會更新我的答案。 – codenheim 2010-03-31 02:16:07

回答

1

我唯一能做的事情就是閱讀他的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)=對應於彙編語言標籤的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樹,(我總是寫一個文本中間語言,彙編程序支持聲明不同範圍的變量和象徵性的臨時對象),但我不能確定他的意思,所以我建議向你的教授證實因爲他以前可能曾經和這本書一起教過,並可能更好地瞭解它。

希望有所幫助。

+0

對不明確我的意思是什麼意思。更新。 – drozzy 2010-03-31 00:54:47

+0

好的。我有Appel的書(C版本,而不是Java),所以我會更新我的答案。 – codenheim 2010-03-31 01:55:46

+0

謝謝,說實話,沒有人確切地理解這些事情應該如何在我認爲我們班上工作。 – drozzy 2010-03-31 02:56:34

2

嗯,這實際上取決於你的IR如何表現。此外,由於pointed outmrjoltcola,你有什麼建議看起來更像是一個AST(抽象語法樹)。 AST更高級別,通常是從源直接生成的樹結構。 IR通常更簡單和更低級(代碼通常表示爲簡單指令列表,而不是表達式樹)。 AST通常對編譯器非常具體。 IR通常是編譯器和/或語言獨立的(參見例如LLVM)。

如果你要代表它在文本,我認爲

+(k,1) 

會更簡單,因爲你會需要一個相當複雜的詞法/語法分析器反正,這將是一個對人類來說更易讀(儘管對計算機而言可讀性稍差)。不需要像MEMNAME這樣的東西,因爲這種情況下的標識符顯然是一個變量訪問(它的確取決於編譯器的語言和結構)。儘管如此,我絕對不會使用像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)) 
+0

對不起,我不清楚。更新了我得到符號的問題。 – drozzy 2010-03-31 00:43:28