a simplified C to Java Compiler

Presentation on theme: "a simplified C to Java Compiler"— Presentation transcript:

1 a simplified C to Java Compiler
Compiler Term Project MilkTea a simplified C to Java Compiler NTUCSIE, B 吳介元 B 林軒田

2 Scanner 我們的 Scanner 使用 flex 製作 特別的地方有：
字串部分是採用Hand Coding，原因是若採用flex來處理，須表示成regular expression，而且有escape character要處理(如：\\、\“ )，所以該部分的code是自己處理的。 字元部分也可處理escape character

3 Scanner(continue) 關於 Identifier 部份，為了解決 Parser 所出現的 Conflict, 我們使用 Semantic-Feedback Scanning，即在 Scanning 時依目前 Semantic 的狀況回傳不同的資訊，區分為IDENTIFIER、FIDENTIFIER、TIDENTIFIER，code節錄如下：

4 Scanner(continue) [a-zA-Z_]+[a-zA-Z0-9_]* {
yylval.StringValue = new TString(yytext); if (IsTypeName(yylval.StringValue)) return TIDENTIFIER; else if (IsFuncName(yylval.StringValue)) return FIDENTIFIER; else return IDENTIFIER; }

5 Scanner(continue) System support functions 由 scanner 直接判斷讀入，以節省在 Symbol Table 中搜尋與判斷的時間，如 printint, printfloat, malloc 等，但缺點是擴展性較差。

6 Parser Parser 使用 bison 製作，由於使用 LR-parsing，在幾個常見的 C 語法會出現 Conflict，列舉如下： If-then-else，即 Dangling-else 的問題。在 bison(yacc)中提供了使用 precedence 的標準作法。即讓有 ELSE (需 shift)的 Rule 優先序高於無 ELSE (需 reduce)的來解決。

7 Parser(continue) Struct Dec List, Func Dec List, GlobalVar Dec List, Func Body List的區塊，由於可能有相近的開頭(struct IDENTIFIER)而使 parser 無法 lookahead 出其屬於哪一種而出現 reduce/reduce conflict。即如下的 Grammar: Program : StructDecList FuncDecList GlobalVarDecList FuncBodyList StructDecList: Lambda | StructDecList StructDec … 不是一個 LR Grammar，所以我們把它 Modify 成如下的 Grammar：

8 Parser(continued) 但如此 Semantic 時需作 check 以確定 Program 是照著我們預期的順序寫成。
Program: InfoList InfoList: Lambda | InfoList Info Info: StructDec | FuncDec | GlobalVarDec | FuncBody 但如此 Semantic 時需作 check 以確定 Program 是照著我們預期的順序寫成。

9 Parser(continued) 由於允許 Pointer 宣告的存在，因此如下的語法會出現 Conflict
Complex* x; A*b; 用標準 C 語法宣告可以避開這個問題，另外我們在 scanner 中作了 IDENTIFIER 類別的判斷也可以讓我們對 Semantics 的定義更輕鬆。 struct Complex* x;

10 Semantics Semantics 端可以分為三個部份，首先是 SymbolTable 的建立與操作。
我們的 Symbol Table 使用自訂的 Hash Table，在每個 Scope 中有自己的 Symbol Table 來作區別，因此 Variable binding 的動作可以透過 Display 式的尋找而得到。 而 Type、GlobalVar、FuncDec則置於 GlobalSymbTbl 中，並同時供 Scanner 作 IDENTIFIER 類別的判斷。 Symbol Table 所存的 Symbol Attribute 是以 Object-oriented 的架構配合 RTTI 來判斷該 Attribute 屬於哪一種 Symbol

11 Semantics(continued)
Type 則可透過 Symbol Table 中的 Key 來找到，一樣使用 Object-oriented 和 RTTI。值得注意的是我們把一個 Type 的 Pointer Attribute 掛在 Original Type 的一個欄位中(可以當作 Original Type 的，Primitive Type/Struct Type 則被稱為 TypeWithPointer) Array Type 則存有其 Base 和 Length，但不允許有 Pointer

12 Semantics(continued)
第二部份是 Expression。我們的 Expression 作法如下： 利用了 Java VM 的特性，以 Stack Variable 來當作運算暫存值存放的地方，因此不用寫入多餘的 Local Variable。 要達成這樣的作法，每個 Expression SubTerm 得在適當的時間被載入Stack(即已確定要取其值的時候)。被載入的時機，不外乎是 Do Operation 的時候，為了達成這樣的目的，我們 Modify 了 Action Symbol 的位置：

13 Semantics(continued)
Add: Exp1 + { Exp1 need to be generated here } Exp2 { Exp2 generated, do add } 但如此還有一個問題，如果 Exp1 和 Exp2 的 Type 不同而 Exp1 要作 Type Coercion 呢？這時 do add 就必須把 Exp1 Swap 上來、do coercion、Swap 回去、do add。 因此，每個 Expression Record 會帶有這個 Expression 的狀態(Var、Owner on Stack 的Field、Array Info on Stack 的 ArrayPos、Value on Stack)以讓其後的 Expression 判斷是否要載入(或在 Assignment 中要 Load)

14 Semantics(continued)
但在 C 中，值得注意的是 Assignment 被視為 Expression，即在 JVM 中，作完 Assign 還需要留一份值在 Stack 上，因此我們 Modify 了 Assign 的動作如下： Make sure the location of assgnment is known Dup the location of assignment Do assign Do load

15 Semantics(continued)
還有，C 中的 Logic Expression 有作 Short-cut Evaluation，所以 Evaluate Logic Expression 的動作實際上應被展成判斷的程式碼。這部份需要大量的 if 和 label 來配合。 第三部份是 Control Structure。為了避免 Code 排列的問題，我們所有的 Control Structure 的 Code Generation 順序都與其在 C 中的書寫順序相同，大致結構如下：

16 Semantics(continued)
if(Exp) State Exp==0 ….EndIf State EndIf: if(Exp) State1 else State2 Exp==0 …. EndIf State1 EndIf: …. EndElse StartElse: State2 EndElse:

17 while(Exp) State do State while(Exp) StartWhile(continue):
Exp==0 …. EndWhile State …. StartWhile EndWhile(break): do State while(Exp) StartDo(continue): State Exp!=0 …. StartDo EndDo(break):

18 Semantics(continue) switch(E1) Lstate for(E1;E2;E3) State
Check: E2 …. StartFor/EndFor UpDate(continue): E3 …. Check StartFor: State …. UpDate EndFor(break): switch(E1) Lstate Branched as many if’s break to end of switch

19 Semantics 其他有關特殊的 Semantics 設計有 Object Allocation as in C
Copy initializer of structures similar to C Struct Type Pointer accessing