沒想到的今天

用C++建立四則運算解題工具:語法分析器(Precedence climbing) 經過九天，一個空想成形，雖然不是很滿意，畢竟架構有些凌亂，可能再把它改好一些(?)，重寫一篇更好的文章系統性講解(?)，達到一個希望以技術著稱的部落客該有的水準(?)。這三個問號可能要到幾個禮拜後才會成真。明後天休息，著手找下一個計劃，還是會與C++相關，目前練習還不充足。 所有的程式碼放在 Github 上，Precedence climbing的實作也一並完成。記得看README。 有抽象語法樹(AST)之後求值就不難。 double AST::eval(AST* tree) { if(tree->tk->isNumber()) return (double)tree->tk->de.num; else if(tree == nullptr) return 0.0; else { switch(tree->tk->tok_t) { case tk_Add: return eval(tree->left) eval(tree->right); case tk_Sub: return eval(tree->left) - eval(tree->right); case tk_Mul: return eval(tree->left) * eval(tree->right); case tk_Div: return eval(tree->left) / eval(tree->right); case tk_Negate: return -eval(tree->left); default: throw runtime_error("Error: Unsu...

兩天沒寫，精神很難集中，然後看了影集和電影，電影看了<<流浪地球>>，4月30就在Netflix上可以收看(原定:5月6日)，不打算這裡評論他。 從看懂語法分析器(Parser)的原理到時做耗費了很多心力，小的妄議大大的話題，才造成這種下場，說得上理解Parser原理的時刻約在除錯的時候，因為一直不理解原理又想著有寫部落格的壓力，選擇不明究理的先抄一遍，把虛擬碼(Pseudo code)轉成C++，先是在編譯時遇到很多困難，由於物件導向概念是在高中學Java(SE 6)的時候建立(今天我也忘了差不多，應該要在自介中把Java拿掉)，與C++11相比其實有多有不同，而C++在大一的計算機語言有教，但那是一堂C/C++的課，所以交作業都是用C語言，然後買的教課書根本沒看幾頁，過了一兩年就把書跟朋友用換書的方式脫手，還幾本中文C/C++都不見了，有些是有意識地送人或是有可能捐給圖書館，有些可能只是不小心借出去，反正都沒甚麼印象了，手邊最後的C++書籍只剩下資料結構與演算法相關書籍，所以C++相關的資料幾乎都在網路上東找西查。這可能是學習C++速度與效果不佳的可能原因(翻閱實體書才有吸收並理解的感覺)，然而拖了兩天還是該改進。繼續摸索適合的步伐和方式學習。 先來一首這兩天很喜歡的歌 SOS - Avicii, Aloe Blacc 因為一開始對Lexer、Parser的陌生，很可惜沒有一開始將兩個東西看成高度關聯共存在一起的主題，不過在實作中漸漸透露出他們的關係，如果有時光機，我會先一次看完Lexer和Parser，然後在專注實作Lexer然後Parser。 在 rosettacode中syntax_analyzer的C語言實作 是一個被稱作Precedence Climbing的方法也提供 介紹原理的文章(Parsing Expression by Recursive Descent) ，以下的實作就是其中介紹的The classic solution，當時不理解Precedence Climbing所以選擇The classic solution。 理解文法就不用害怕密密麻麻的pseudo code，被pseudo code耽誤 The classic solution概要: 為每個相同優先序的運算子建立新的nontermin...

兩天沒更新，理所當然週休二日啊!(明明就是自宅守備員)但這兩天雖然沒有更新但有持續學習如何建立詞 法分析器(Lexer) 與 語法分析器(Parser) ， 上一集 說錯了，我把Lexer與Parser混為一談。目前已經完成Lexer的部分。遇到很多問題，畢竟我跟C++不熟，一直做一直查，速度真的很慢。即使選定了目標，但還是會不斷冒出支線任務。好了，看看有什麼成果。 先來個程式碼: lexer.h : #ifndef LEXER_H #define LEXER_H #include <string> #include <regex> #include <vector> #include <stdexcept> #include <iostream> using namespace std; enum TokenType{ tk_Mul, tk_Div, tk_Add, tk_Sub, tk_Negate, tk_Lparen, tk_Rparen, tk_Integer }; union detail { int num; string *ident; }; class Token { public: Token(TokenType, int, detail); ~Token(); TokenType tok_t; int err_col; detail de; static string tk_name[]; const string tok_name(){ return this->tk_name[static_cast<int>(tok_t)];}; bool isNumber(){return this->tok_t == tk_Integer;}; bool isSymbol(){return ! this->isNumber();}; }; class Lexer { public: static void run_lexer(s...

第二天就遇到大麻煩，昨天訂的目標今天應該是無法完成了，主因是太懶，沒把參考資料好好消化吸收，次要是那些東西真的不好理解，最後是身體有點不舒服似乎是沒睡飽(還有手遊讓我分心)。 言歸正傳，首先昨天訂定的目標是要完成完整的四則運算功能，老實說要實作這個功能不難，相關的資料在網路上也很豐富，但要達到一種簡潔或是美觀的作法卻不容易(心中的美學審查)。 基本原理如下: 普遍看到的四則運算式為' 中序表達 '的形式 閱讀方便，但在計算時並非很方便，必須採取許多計算規則 例如:先乘除後加減，括號內先算 將四則運算式從中序表達轉換成後序表達可以讓計算規則簡化  中序表達、後序表達，甚至是前序表達，如果以樹的形式會很容易明白， 演算法筆記--二元樹 有很好的教學， 中序式轉後序式（前序式）- OpenHome.cc 只要把C語言範例程式稍加修改就大功告成，但這種功不符合這部落格的動機，即使要改也要改成簡潔美的形式，不過是似乎是不可行的其中有 switch陳述式 ，因為在switch(expression)中的expression需式整數或是可以轉型成整數的型別；同時也有替代方案把switch換成 if陳述式 ，然而寫一堆if、else if不好看，另外並不能確定使用者一定會輸入合法的四則運算式，所以建立的工具必須能 判斷語法錯誤 ，如果能夠 指出可能的錯誤位置 就更好不過了。幻想至此已經大大超越我目前的能力，想像力總是遠甩能力，所以接下來幾天要有曲速引擎才能與想像力會合。 經由這個過程此專案的規格漸漸有了形體(雖然依舊好高鶩遠XD)。  一個與語法分析器(parser)可以判斷與法正確與否，可能外加指出錯誤之處 可行的語法分析器 用C++寫個不依賴非標準函式庫的 用boost Spirit 呼叫Prolog幫忙 建立相對應的型別與語法分析器搭配 該型別可以適當表達數學結構與處理最後的計算步驟 四則運算只是中程目標，長程目標是能運算指數、對數、(反)三角函數等等 所用的型別與語法分析器要能夠擴充上述要求 廢話夠多了，今天還是要來點程式碼 檔案下載 (SHA1: FEA021FE41D2B88DACD4DB7DC53D45594CF14BCB) 檔案有多個: fraction.h, fractioi...

接下來幾天會每天寫一些，逐漸建立一個完整的算術運算工具，功能會像是 bc(Basic Calculator) ，功能當然會像它一樣強大囉，不過這會是一個過程好玩的專案，一個過程讓我覺得好玩的專案，所以程式碼一定要充滿趣味，基本上會有以下特性: 良好的可讀性 精簡的程式 刻意採用的設計模式 一些C++語言特性的功能濫用 1.可讀性是我在學習程式語言過程中相當在意的，就像說說話說得清楚，讓溝通順利，程式碼不只是給機器讀取後順利達成目標，在很多時候程式碼會與自己或他人交流，清楚表達程序與邏輯概念讓自己好維護、除錯，與人交流時也比較省力。 2.一天的時間有限，寫得越長閱讀時間越長，如果有精簡作法節省時間就要來省一下。 3.作為練習的專案，刻意練習平常不用的東西是好事 4.因為最近想學習C++11，事實上C++也不算熟，對於STL只有粗淺的認識，C++標準函式庫也需要一直查資料才會用(函式庫用了很多STL很讓人崩潰)。

先來個MV開場 頑童MJ116 幹大事 BIG THING 不同的階段我都有自己幻想的清單 但我的清單通常都以'待辦事項'方式想像與呈現 有時實際寫出來，或記錄成檔案，更多時候為空想 天真以為完成那些事情就可以成為某種超現實的角色 可能是超級英雄或某本小說中的人物 現在寫這些不是因完成了許多待辦事項而成為想像力創造的角色 而是幾乎沒有完成任何一項，所以清單越來越長 長到還想把它寫下去，寫得更長 認真寫部落格曾在清單中出現，進出清單多次(這不是我第一個部落格) 現在這篇就是因為空想清單中又再次新增任務而產生 希望一週能更新五篇，其實心中希望能夠一天一篇 至少寫到六月下旬，下旬之後人生可能有新的副本，或是要跑路了 寫的範圍可能很廣泛，包含許多我有興趣的事情 其中佔很大比例的內容會與程式語言有關 不過不排除寫更多類型的內容 寫些國家大事應該也會包含，畢竟想要成為某種超現實的角色 祝計畫順利 也祝所有人今天的一切順利克服