[閒聊] 在 C++ 中黏出 DSL 解決學校組譯器作業消失

看板PLT (程式語言與理論)作者ronin728時間7年前 (2017/03/11 07:53)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

大家好，我又來了 (`・ω・′) 今天要來曬寫得很爛的作業是一個殘廢等級的 Parser Combinator ... 小弟上學期在學校修了一門課叫做系統程式那堂課是用 Beck 的 System Software 當教材 (我不是很喜歡那本書，沒有那種接觸現實處理器指令集的實際感) 其中有個作業是要寫 SIC/XE 的 Assembler (SIC/XE 是課本中的一套虛擬組合語言) 這個作業需要處理簡單的語言格式所以我就在 C++ 中弄了一個簡易的 DSL 來處理語法解析的部分其實就是用幾個函數組合出想要的規則然後把 Token 的序列餵進去組合出來的函數簡介一下大概會用到的的類型 type Result = (Boolean, TokenStream) 包含解析是否成功、解析剩餘的Token 不過組合語言的AST不是樹狀的所以我沒針對那種情況做處理 type Parser = TokenStream -> Result 解析 TokenStream 並返回結果 type Rule = Parser -> Result 就只是用來包裝 Parser 用的東西而已這裡是原始碼 https://goo.gl/oStNv9 https://goo.gl/aBY4eq 接下來介紹幾個比較有用的函數這些函數的返回類型一定要是 Rule 要不然會組不起來 one : Rule -> Rule 配對一個規則 and : Rule -> Rule -> Rule 配對兩個規則，必須兩個都成功 or : Rule -> Rule -> Rule 配對兩個規則，只需一個成功假如說要配對乘法算式數字*數字變數名*數字數字*變數名變數名*變數名就能表示成 Rule mul = and( one(or(isIdentify, isNumber)), and( one(isString("*"))), one(or(isIdentify, isNumber)))); 還好 C++ 有 Operator overloading 所以可以寫成 Rule idOrNum = isIdentify | isNumber; Rule mul = idOrNum * one("*") * idOrNum; 所以整個 SIC/XE 組合語言的語法就能寫成這樣： https://goo.gl/pf74S4 看起來還有點像 Antlr 的語法不過效能與功能性差多了就是了 (笑這程式時間、空間複雜度頗高壓堆疊、回溯等的操作也相當頻繁這部分還有很大的改進空間另外就是希望之後能找到從解析演算法本身改善的方法我打算在下學期修編譯理論的時候研究如何用類似的方式寫出更好的 Parser 不過可能不是用 C++，用 C++ 很難享受樂趣 XD -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.224.83.21 ※ 文章網址: https://www.ptt.cc/bbs/PLT/M.1489189980.A.607.html ※ 編輯: ronin728 (125.224.83.21), 03/11/2017 07:56:54