boost.spirit (上)

boost.spirit (上)

其實我是很想好好來聊聊 boost.spirit, 無奈最近狀況真的是很差，只想到一大堆
想要或是「應該要」做的事，卻沒一件有辦法真的提起精神來做。每每只能靠著
心血來潮，一次解決掉一件事，如果一次沒解決掉，恐怕也再也沒有再拿起來的時候。
之所以又把 boost.spirit 拿出來用，都是因為學校的「網際網路程式設計」選修課，
上課內容完全是「資料結構」，要交的作業也是資料結構的作業。而這次其中的
一個項目則是：

2.3.8 撰寫C語言的程式完成下列之轉換：
a). 前序字串轉換後序式
b). 後序字串轉換成前序式
c). 前序字串轉換成中序式
d). 後序字串轉換成中序式

基本上如果真的要完全以 C 語言來寫過，這只能說是很折騰人的一件事。
除了要自己實作 stack 的包裝外，還要自己分析各種排序間轉換的演算法。
嗯，我演算法很差是眾所皆知的事，所以這部份是要我自己分析，或是查資料。
身為懶人集團的一份子，怎麼可能有耐心做分析演算法這種辛苦差事呢？
嗯不，也許話不是這樣講，應該說，這種光我用肉腦就可以想出該怎麼做的事，
哪有那個興趣把他用 C 語言這種表達能力低下的語言去實作出來？上次用 C99
寫出進位轉換程式已經是很大的讓步了，那也只是單純想讓自己多熟悉 C99 而
不是搞不清楚 C89/90 和 C++98/03 間的關係。所以這次，我真的是一點意願也沒了。

不過這個題目要求一直讓我想到以前在看 spirit 時的事。短短的百來行，
居然就把以前寫得很辛苦的四則運算機幹掉了。功能更強，擴充性更棒的四則運算機。
所以我一直在想，一直在想，如果這個也能用 spirit 解決掉的話，那真的是太棒了。
可是呢，為了這一個小小的作業，我有必要拿出 spirit 這種巨怪來研究嗎？
那實在是很花時間的一件事，想以前只為了增加指數運算，就花去了我相當的時間。
雖然其實我也只是在 trial & error, 以致於花掉的時間大部份是白費的。畢竟，
spirit 這種巨怪沒下狠心來仔細看一下的話，實在是沒辦法看懂的。

再次拿出懶人集團團員證，何苦如此呢？乾脆就寫下大概的概念就好了，就算因此
拿不到此題的分數，甚至被批藐視課堂作業，whatever, 沒學分也沒什麼大不了的。
於是，我就著手開始寫概念…。

寫著寫著，心就不禁癢了起來。嗯，這樣寫下去會是對的嗎？四處翻查了資料，
自己試著畫 abstract syntax tree, 用幾個各案試了幾次發現都正確後，變得
更加想要證實這種做法是對的。那麼，就試試看吧！

嗯，寫完了。 XD

過程暫時省略，我很意外的是，沒想到這麼順利，只花了一天就全部解決了。
雖然中間碰到了點困難，很多到最後證實都只是我自己耍蠢，算是程式小 bug.
最大的困難恐怕是 postfix notation 的 parser (generator) 一直寫不出來。
或是該說，寫出來了可是一點效果也沒有。前後驗證了幾次，不覺得 EBNF 有
哪裡寫錯…。翻了翻 LL parser, (LA)LR parser 的各個資料，再思索一下 parser
到底要怎麼 parse? 就覺得，這恐怕是 LL parser 的先天問題。由於預先就會
找到符合條件的 symbol(術語我還搞不太清楚，有錯請指正謝謝), 以致於後面的
規則發揮不了作用…。

anyway, 最後還是用 prefix notation parser 兜出 postfix notation parser 來。
雖然這樣好像失去 LL parser「可能」可以用 stream 形式的 input, 而需要一個
大 buffer 來吃下所有的 input（才有辦法反轉 input）... 管他的，這裡只求解題。

詳細實作暫時留待下次再說（雖然不知道會是幾時），因為我又開始感到疲倦了。
這裡就先附繳交作業時所附的簡短文字說明，還有交出時的程式碼。（後來改了一點）

==

well, 我實在很懶得寫這種吃力又不討好的程式。
吃力？用 C 語言寫當然吃力，類似的東西用 yacc 或 bison
之類的工具來寫，絕對會省力得多。而 C++ 寫慣又不熟 C 的我，
則會傾向於用 boost.spirit 來寫。可惜的是我跟 spirit 其實也沒很熟，
也懶得研究之後再寫下本 C++ 程式，所以就稍微講一下該怎麼做就好了。

不過有趣的是，就在我稍微思索究竟該怎麼做的同時，
也讓我心癢到非得試試看，驗證自己的推測是正確的。
於是我大概花了一天的時間，試著把 spirit 範例的四則運算機
改寫成各種 fix 間互相轉換的 parser. 雖然 postfix notation parser
我做不出來，恐怕是因為這是 LL parser 的極限，而 spirit 本來就
只是 LL parser generator. 所以 postfix notation parser 的部份，
我做了點手腳，利用字串反轉等方式由 prefix notation parser 模擬出
postfix notation parser.

anyway, 大概的做法就是先寫 EBNF 來描述語法規則，接著由 spirit 的
parser 建立 abstract syntax tree, 而有了 abstract syntax tree 之後，
幾乎可以說要做什麼都很簡單了。prefix notation 就是 preorder traversal 的
結果。infix notation 就是 inorder traversal 的結果，postfix notation 就是
postorder traversal 的結果。

理論上 spirit 本身在做 parsing 時，會產生出一份自己的 abstract syntax tree,
可惜上面提過了，我跟 spirit 本身並不熟，不知道怎麼去存取他背後的 AST,
所以我自己很簡單地寫了一個 SimpleTree, 反正四則運算本身就是很簡單的語法
結構，一個很單純的 tree 就可以符合要求，並不需要很 flexible.

概觀來說，做法大概就只是這樣而已。EBNF 描述語法，spirit 建 AST, 建好之後
所有的答案就都出來了。只是 prefix notation 我想不到簡單的 EBNF 描述，
所以寫起來大概只是 BNF. 而 postfix notation 我試了很久，總覺得是 LL parser
的問題，那就不是我在 EBNF 描述上可以改變得了的。於是只好藉由 hack prefix
notation 來使得 postfix notation parser 變得可能。

其實很久沒有把注意力放在 C++ 上了（最近 Ruby 跟 Haskell 碰比較多），
昨天在查資料時才發現 spirit 要出 2 了，還有個 boost.fusion 整合 STL 與 MPL,
使得 compile-time 跟 runtime 更緊密地結合。老實講，boost.mpl 我一直覺得不是
很好用，因為有點複雜難以理解。不過如果 fusion 真的能好好地整合 STL 與 MPL,
相信 C++... 會變得越來越 powerful. 也許要說這是走火入魔也不為過吧，哈哈。
只是 imperative language 本來就有極限，發展到最後，總有一天也會走入
functional language. OCaml 據說是個整合得還不錯的語言，C++ 恐怕哪一天也會
走到這條路上？也許在 C++1x 或 C++2x 上吧…？

最後再提一下的是，infix notaion 因為有先天的 seperator, 也就是 operator,
所以可以使用數字或是字串當元素。而 prefix/postfix notation 沒有 seperator,
修改輸入格式增加 seperator 也有些麻煩，所以我只寫支援單一字元或數字。
例如：AB+B 是合法 infix notation. 而 +ABB 和 ABB+ 都不是合法的。
122+ 是 1 2+2, 沒辦法表達 12 2 +, 需要用空白當 seperator. 當然這要寫不是
不行，只是就不能很順暢地寫 ABCDE-+$*EF*- 這種東西囉。所以我還是寫僅支援
單一字元或數字的做法。詳細請見 EBNF notation.

==

整篇作業的連結（含當時尚未修改完畢的程式碼）：
http://ymcom.ym.edu.tw/~godfat/network....htm
http://www.godfat.idv.tw/other/network....htm（連上率低）

下篇我們來看詳細實作，含修正完畢的程式碼。

2007.04.09 godfat 真常