自主學習 - CASC編譯器功能實現

在這學期前，我和老師打包票我能做個編譯器出來，沒想到我真的做出來了w(雖然只有最基本的一些功能例如函式、迴圈、和條件式)。

而在本學期中，為了讓這個編譯器有更多高階語言應有的功能，我預計在本學期實作出以下兩個非常實用的功能：

Import (導入模塊)
Class (類別)

Import沒什麼好說的，最基本的概念就是將另一個source file內的source code和本地的source code一起compile進而讓本地端的source code能呼叫到外部source code的一些物件(如函式)。

但Import和一般的syntax扮演著非常不同的角色，前者是在compiple前呼叫並解析的，而後者則是在runtime時執行的。也就是說，兩者要呼叫的時刻是不同的。現有的架構是(以外部檔案實現)：

導入檔案至一個編譯的thread (Read file)
分析詞彙 (Lex)
賦予特定詞彙或表達式標記 (Tokenize)
分析標記並嘗試組合成更為複雜的標記組合 (Complex Tokenize)
將所有標記分析各自關係並檢查其邏輯，諸如型別判斷或是隱式轉型 (Bound)
部分語法可能需要跳過部分程式碼或是跳回特定位置繼續執行，故必須再加以分析並插入一些語法至程式碼 (Bound Tree Analyse)
將一些語法降級(例如for迴圈降級為while迴圈) (Lower)
運算並執行 (Evaluate)

這是目前最精簡的過程，而我們的Import功能若以上面的流程來看，必須在第三步驟至第四步驟之間就執行，否則外部的source code後續無法並聯同步分析，造成後續可能讀不到檔案之間正確的依賴關係。

蒐集到足夠架構一個Import功能的實現方法後，首先：

由於我希望我的import功能目前能單純導入外部程式碼並呼叫即可，基本語法如：import "/ex.casc"或導入 "/ex.casc"，那麼我們要先tokenize才能得知我們import關鍵字後的相對路徑。 Pseudo Code如下(以csharp為例):

public ImmutableArray<string> ParseReferencedSources(string path) {
    var tokens = ParseTokens(Source);
    var referencedSources = new List<string>();

    for (var i = 0; i < tokens.Length; i++)
        if (tokens[i].Kind == SyntaxKind.ImportKeyword)
            referencedSources.Add(path + tokens[i + 2].Text.Replace("\"", ""));

    return referencedSources.ToImmutableArray();
}

上面我們先將檔案的位置作為參考路徑，之後將import後的字串分析並concentrate後加入一個集合供後續程序使用。

接下來要把步驟一收集到的相對路徑一一加入至編譯單位。為了保證import的東西都相當於Static Linking的處理，所以在編譯&運行的程序中我們將收集到的檔案逐一先行編譯後，我們的主程式才不會有問題。
最終我們的主程式方可使用外部程式庫。

值得注意的是依照上面程序所加入的函式庫會因為外部檔案的擴大而一同增加整體的編譯時間，但對於我們的JIT編譯器來說至此已經夠用了，所以我們將轉換目標到Class的實現上。

一般的OOP語言中的Class (或是struct)一般來說就是種以Key to Value的形式去儲存內部成員的資料結構，也就是說Class可以簡單理解成一個事先定義好的HashMap。

而C#有一個非常適合實現的meta programming特性稱為dynamic，在C#以dynamic關鍵字宣告的變數一律在後續的程序內不會經由編譯器的判斷，舉例來說：

var a = true;
System.WriteLine(a + 1);

// Compiler Error

上面的程式明顯有誤，因為true沒有對應可用的Plus Operator可以套用到integer上，所以會無法編譯成功。但如果我們將以上程式更改為下：

dynamic a = true;
System.WriteLine(a + 1);

// No Compiler Error but Runtime Error

將var更改為dynamic將會使Compiler不去針對以dynamic宣告的變數去做任何判斷，相當於我們讓變數a繞過了Compiler Checking直接讓他執行。但是這樣還是會在執行階段發生Runtime Error，主要是因為true在Runtime階段中還是找不到可以對應布林值的Plus Operation，所以在IL Code中，執行上還是會發生問題。

而dynamic之所以能夠幫助我們建立一個Class的原因有二：

我們可以結合C#的另一個特性(或是物件): ExpandoObject 來宣告其物件中的一個Object，因此可以動態的將以CASC語言宣告的Class子成員放入ExpandoObject而不會造成錯誤。
如果使用純HashMap來實作的話，在C#呼叫位於HashMap的子成員函式時將無法以 Clazz.func(...) 的方式呼叫，是因我們所取得的所有property call都只能取得字串，所以上面的方式是不可行的，但如果我們以ExpandoObject則能用index的方式呼叫子成員： Clazz["func"](...)。

而我們有了上述的要素，我們就能實現Class了嗎？不，我們還缺少一個非常重的的東西：Type Checking，很可惜Type Checking在現有的架構上要實現要花太多時間去處理，所以最後我改用JVM Bytecode去實現它，相對簡單的原因是因為JVM已經實作了Type Checking，我們唯一要做的事只有Lexing, Paring, 和Emitting (將CASC code轉譯為JVM Bytecode)。

這次的編譯器實作較我平常做的專案相對要花更多腦力去實現相關的編譯器細節，而大部分的編譯器素材都是從網路上不同編譯器專案一一剖析而得到的成果，但是努力總是有回報的，至少我以我喜歡的Language Spec做出了一個能由電腦執行的程式語言。

相關連結：

CASC - JIT - 以C#實現的CASC JIT編譯器
CASC - JVM - 以JVM Bytecode實現的CASC編譯器

自主學習 - CASC編譯器功能實現

Read more

Metamorphosis - Akt I

Tangle：A prototype one-pass parser for C language

Incubating the JVM Backend ecosystem for rustc

Google Developer Student Club FCU '23 成員招募