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

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

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

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; }

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

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

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：

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

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

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

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

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

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)

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

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

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

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):

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

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