用 PEG 寫一個 C parser 續
自從去年十月把 nixie tube clock 完工之後，好像都在耍廢之類的，結果 11/12 月兩個月都沒有發文，
其實這兩個月裡面，有的時間都在改之前寫的 C parser
，
其實整體完成度愈來愈高了，今天發個文來整理一下到底做了啥。
這次做了幾個改變，主要的修正就是加上 expression, declaration, statment 的處理，也學到不少東西，這裡一一列一下：
rust
用 PEG 寫一個 C parser
故事是這樣子的，之前我們寫了一個自創的程式語言 Simple Language ， 還用了 Rust 的 pest 幫他寫了一個 PEG parser ， 雖然說它沒有支援新加入的函式等等，本來想說如果年底的 MOPCON 投稿上的話就把它實做完，結果沒上，看來是天意要我不要完成它（欸
總而言之，受到傳說中的 jserv 大神的感召，就想說來寫一個複雜一點的，寫個 C language 的 PEG parser 如何？ 然後我就跳坑了，跳了才發現此坑深不見底，現在應該才掉到六分之一深界一層吧 QQQQ。
...寫了一個不知道幹什麼用的 regex library 跟 parser
故事是這樣子的，之前寫 understanding computation 的時候，發現 regular expression 的實作，只有最基本的五種：
- empty 匹配空字串
- literal 匹配文字
- repeat * 匹配零個或多個 regex
- concatenate 匹配連續的 regex
- choose 匹配嘗試數個 regex
大約幾天前想到也許可以把這個 project 拓展一些，讓它威力更強力一點點，順便當個練習。
...把 NFA 轉成 DFA 這檔事
故事是這樣子的，最近寫了一些跟 Regex 相關的程式碼，無意間發現我之前understanding computation 這本書的實作中，並沒有實作非確定有限自動機（下稱 NFA）轉成有限自動機（DFA）的程式碼。
...有關 Rust test 的那些奇奇怪怪的東西
有關 Rust test 的那些奇奇怪怪的東西
最近因為在寫 Rust code，想到那句朗朗上口的口號「原碼未動，測試先行」，想說就來寫點測試，嘗試一下傳說中的 TDD 開發，連路上的計程車也愈來愈多 TDD 了你還不 TDD。
想說就來整理一下 Rust 測試相關的編排，還有我遇到那堆奇奇怪怪的開發經驗。
簡而言之，我們先放掉什麼把 test 寫在 comment 裡面的設計，那東西我至今沒用過也不太看人用過，註解跟文件什麼的只是裝飾而已，上面的大人物是不會懂的。
實作麻雀雖小五臟俱全的程式語言
故事是這樣子的，很早以前曾經看過 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， 可以參考這篇的內容 ：
...使用 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 管理，帶來的好處包括有：
- 可以一次 cargo build 編譯所有程式
- 引入 cargo test 代替本來編譯成執行檔用 println debug 的實作
- 在各章的內容間重用 module ，提升重用比例
- 另外也能使用網路上其他人寫的 Rust module（其實這才是原初整理的目的）
例如在我之前實作的程式碼，在寫 finite automata 時，dfa, nfa 各自有一個實作，使用 u32 作為狀態； 但到了 regular expression 的時候，為了產生 nfa 就不能用 u32 作為狀態，於是我複製了一版 nfa， 改成用 object pointer 作為狀態 ， 兩者程式碼的重複率就非常高，這次也一併改成 generic 的 nfa 實作，兩邊就能分享同一套程式碼。
...