用 Erlang 寫 Forth 直譯器的感想

這幾天我在寫 Forth 程式的編譯器, github.com 的存放位置在 https://github.com/YauHsien/erl4th 。我的發想,是先用 Erlang 環境跑 Forth 語法,即用 Erlang 寫 Forth 直譯器。

另外,有個側面的想法,是想要每天寫程式丟在 github.com 。結果,老實說,這二天開始上班之後,每天晚上連寫那一個小時都懶,只能做一點小幅的改進,沒辦法做太多思考。所以昨天我停下來,開始重新好好想。

我覺得要編譯 Forth ,一開始只要先把輸入的程式用空格分開,就已經是後序式了,而後序式也是一種二元樹或多元樹。然後, Forth 程式區分為三種符號:文字、值、區隔符號,所以做 lexical analysis 時,應該要這樣做:

  • 文字應該要表示為〈文字,參數數目〉,因為文字是運算符號,有相對的參數,而參數數目表示為負整數。例如〈my-emit, -1〉,相當於在函數語言中有個函數名叫 my-emit/1 。
  • 值應該要表示為〈值,消化參數數目〉。值的存在,可能之後會被運算符號消化掉,所以需要定義「消化參數數目」,去跟〈文字,參數數目〉做加總抵消。於是,如果有一個運算符號的「參數數目」沒有抵消為 0 ,就可以印出那個運算符號是 stack underflow error 。
  • 區隔符號只能照樣存在 lexical analysis 的結果,因為之後做 semantic analysis 要用。

Syntax analysis 就不必了,因為 Forth 程式經 lexical analysis 之後,得到一串東西,就是語法樹。

至於 semantic analysis 的任務,是把 Forth 程式整理成一份字典和一個運算用的 stack 。字典中的每一筆,是一個文字定義,而且定義好的文字其實就是函數,例如 : star 42 emit ; 是函數 start/0 。在這一階段,要把每一筆文字的參數數目算出來,所以一筆文字表達成 (key, value) ,則是(〈star, 0〉,[42, emit]),本來 lexem value 是 [〈42, 1〉, 〈emit, -1〉] ,後來經由 semantic analysis 處理之後,若把第二個數字消掉,變成 [42, emit] ,就可以直接拿去算。至於註解類型的字詞,如果是有關參數格式的註解,如 ( m n — … ) ,可以製做成 type-check 的特點,否則,可跳過其他普通的註解。

接下去,要產碼的時候,字典的每一筆內部格式都可以翻譯成函數,很方便。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Programming 並標籤為 , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s