寫了一個不知道幹什麼用的 regex library 跟 parser

故事是這樣子的,之前寫 understanding computation 的時候,發現 regular expression 的實作,只有最基本的五種:

  • empty 匹配空字串
  • literal 匹配文字
  • repeat * 匹配零個或多個 regex
  • concatenate 匹配連續的 regex
  • choose 匹配嘗試數個 regex

大約幾天前想到也許可以把這個 project 拓展一些,讓它威力更強力一點點,順便當個練習。

...

 August 17, 2018 |    rust  |    rust , regex  | 1 min  |  YodaLee

把 NFA 轉成 DFA 這檔事

故事是這樣子的,最近寫了一些跟 Regex 相關的程式碼,無意間發現我之前understanding computation 這本書的實作中,並沒有實作非確定有限自動機(下稱 NFA)轉成有限自動機(DFA)的程式碼。

...

 July 27, 2018 |    rust  |    rust  | 2 min  |  YodaLee

有關 Rust test 的那些奇奇怪怪的東西

有關 Rust test 的那些奇奇怪怪的東西
最近因為在寫 Rust code,想到那句朗朗上口的口號「原碼未動,測試先行」,想說就來寫點測試,嘗試一下傳說中的 TDD 開發,連路上的計程車也愈來愈多 TDD 了你還不 TDD
想說就來整理一下 Rust 測試相關的編排,還有我遇到那堆奇奇怪怪的開發經驗。
簡而言之,我們先放掉什麼把 test 寫在 comment 裡面的設計,那東西我至今沒用過也不太看人用過,註解跟文件什麼的只是裝飾而已,上面的大人物是不會懂的

...

 July 14, 2018 |    rust  |    rust  | 1 min  |  YodaLee

實作麻雀雖小五臟俱全的程式語言

故事是這樣子的,很早以前曾經看過 understanding computation 這本書, 這本書第二章的內容,是利用操作語義(operational semantic)的方式,自訂一款極簡程式語言,非常簡單但已經有 if 判斷式,while 迴圈等功能。
最近剛修完 coursera 上面的 programming language, 其中有一個作業也是用 racket 的操作語義定義一款程式語言, 這個程式語言更複雜,在資料結構上支援 pair -> list,同時還支援函式,這是之前 Understanding Computation 沒有實做的部分。

...

使用 procedence climbing 正確處理運算子優先順序

上一篇我們說完如何用 Rust 的 PEG 套件 pest 生成簡單的程式碼分析器,但其實還有一些沒有解決的問題,像是 1 * 2 + 3 * 4 = 20,這是因為我們在處理 expression 時沒有處理運算子優先次序,只是從左到右掃過一遍。
真正的 parsing 要考慮運算子優先權跟括號等等,例如:

1 + 2 + 3 -> ((1 + 2) + 3) : Left associative(左相依)
1 + 2 * 3 -> (1 + (2 * 3)) : * 優先權高於 +
2 ^ 3 ^ 4 -> (2 ^ (3 ^ 4)) : Right associative(右相依)

在這裡我們要介紹 precedence climbing 這套演算法,假設我們已經有了 Term (op Term)* 這樣的序列,現在要將它 parse 成 syntax tree, 可以參考這篇的內容

...

 May 10, 2018 |    rust  |    rust  | 3 min  |  YodaLee

使用 rust pest 實作簡單的 PEG simple 剖析器

上一篇我們看了 PEG 相關的內容,這篇我們就來介紹該如何用 PEG 寫一個簡單的剖析器。

...

剖析表達文法 PEG 簡介

剖析表達文法 PEG 為 Parsing Expression Grammar 的縮寫,2004 年由 Bryan Ford 教授所提出, 相對於一般在編譯器課上教 parsing 所用的 CFG (Context Free Grammar) ,已經被鑽研數十年之久,可說是相當年輕的形式化語言。

...

整理 rust module 的安排方式

故事是這樣子的,兩年前因為傳說中的 jserv 大神的推薦,我讀了 Understanding Computation 這本書,讀完覺得學到很多東西,深受啟發; 後來大概花了兩個月的時間,用Rust 重寫了裡面所有的範例程式碼,目前在 github 上查了一下, 我應該是除了原作實作之外,實作最完整的一個,可謂一人之下,萬人之上(誤。

最近因為一些原因,把之前的實作打開來看,馬上關上,假的!趕快在筆電前面打坐。
當初到底怎麼寫這麼醜,還查到有些章節的內容沒有實作完,那時候可能太難不會寫,先跳過結果就忘了QQ……最近這一兩個禮拜陸續花了一點時間整理。

這次整理的一大修正,是把本來是散在各處的原始碼,重新照 rust 慣例統整到 src 資料夾下面,並使用 cargo 管理,帶來的好處包括有:

  1. 可以一次 cargo build 編譯所有程式
  2. 引入 cargo test 代替本來編譯成執行檔用 println debug 的實作
  3. 在各章的內容間重用 module ,提升重用比例
  4. 另外也能使用網路上其他人寫的 Rust module(其實這才是原初整理的目的)

例如在我之前實作的程式碼,在寫 finite automata 時,dfa, nfa 各自有一個實作,使用 u32 作為狀態; 但到了 regular expression 的時候,為了產生 nfa 就不能用 u32 作為狀態,於是我複製了一版 nfa, 改成用 object pointer 作為狀態, 兩者程式碼的重複率就非常高,這次也一併改成 generic 的 nfa 實作,兩邊就能分享同一套程式碼。

...

使用rust closure實作fizzbuzz

之前用Rust 重寫Understanding Computation 裡面的ruby code,目前從 github 上來看,我的 Rust code 應該是僅次於原作者的 code,完成度最高的一個版本。
從去年五月,把大部分的 code 完成以來,唯一一個沒寫的章節:chapter 6 的 fizzbuzz,最近終於實作出來了\weee/。

...

Rust 開發迷你ARM kernel 系列 0:Hello world

故事是這樣的,很久以前曾經在rust 上面實作 hello world 的 arm 程式,不過那時候的作法現在已經不能用,而且除了輸出x 之外其實不能幹嘛,更別提後面更多的東西了。

其實網路上也查得到不少Rust OS 的實作,沒道理我做不到,於是就來試一試了。

...