摘要： 上一篇文章對大部分文法都構造出了一個使用的狀態機了，這次主要來講右遞歸的情況。右遞歸不像左遞歸那么麻煩，因為大部分右遞歸寫成循環也不會過分的讓語法樹變得難以操作，不過仍然有少數情況是我們仍然希望保留遞歸的語法樹形狀，譬如C++的連等操作，因此這里就來講一下這個問題。 右遞歸是怎么形成的呢？在這里我們先不想這個問題，我們來看一個普通的文法。在上一篇文章我們已經說過了，如果一條文法有一個非終結符引用... 閱讀全文

摘要： 一、 這篇文章是應之前在微博上爆過的下個周末某出版社的線下活動而寫的。回顧我和C++在這個世紀的第二個春天開始發生過的種種事情，我發現我并不是用一個正常的方法來學會如何正常使用C++的。我的C++學習伴隨著很多其他流行或者不流行的語言。現在手中掌握的很多淫蕩的技巧正是因為學習了很多編程語言的緣故，不過這并不妨礙我正常地使用C++來在合理的時間內完成我的目標。 學習C++是一個艱難的過程。如果從... 閱讀全文

摘要： 本來每年都要寫一篇年經帖來提高一下知名度的，但是最近因為做GacUI太興奮，竟然把這件事情給忘了，實在是罪過。如果要說我2012年做過的什么事情最重要，那當然要屬開發了GacUI（Home Page, Codeplex, Github）和創建了粉絲群（啊哈哈）了吧。博客到現在還有三個坑沒填完，分別是那個已經坑了好久、大家都要看、但是我卻不知道要寫什么的《C++使用技巧》，還有兩個大家不怎么想看的《可配置語法分析器開發紀事》和《GacUI與設計模式》。關于GacUI，我已經在微博上做了許多廣告，也有一些人開始嘗試使用它了。目前GacUI還處于一個湊合著能用的beta狀態，我在接下來的很長一段時間 閱讀全文

摘要： 上一篇博客寫到了如何給一個非終結符的文法規則構造出一個壓縮過的下推狀態機，那么今天說的就是如何把所有的文法都連接起來。其實主要的idea在（三）和他的勘誤（三點五）里面已經說得差不多了。但是今天我們要處理的是帶信息的transition，所以還有一些地方要注意。所以在這里我們先把幾條文法的最后的狀態機都列出來（大圖）：接下來的這一步，就是要對所有靠非終結符（Exp啊Term這些）進行跳轉的transition都執行上一篇文章所說的傳說中的交叉鏈接。在產生鏈接的時候，我們給shift和reduce的邊分別加上shift和reduce。而shift和reduce是有參數的——就是被shift走的狀 閱讀全文

摘要： 本來說這一篇文章要把構造確定性狀態機和look ahead講完的，當我真正要寫的時候發現東西太多，只好分成兩篇了。上一篇文章說道一個基本的狀態機是如何構造出來的，但是根據第一篇文章的說法，這一次設計的文法是為了直接構造出語法樹服務的，所以必然在執行狀態機的時候就要獲得構造語法樹的一切信息。如果自己開發過類似的東西就會知道，類似LALR這種東西，你可以很容易的把整個字符串分析完判斷他是不是屬于這個LALR狀態機描述的這個集合，但是你卻不能拿到語法分析所走的路徑，也就是說你很難直接拿到那顆分析樹。沒有分析樹肯定是做不出語法樹的。因此我們得把一些信息插入到狀態機里面，才能最終把分析樹（并不一定真的要 閱讀全文

摘要： 剛剛發了上一篇文章之后就發現狀態機畫錯了。雖然LiveWriter有打開博客并修改文章的功能，不過為了讓我留下一個教訓，我還是決定發一篇勘誤。這個教訓就是，作分析的時候不要隨便“跳步”，該一步一步來就一步一步來。其實人呢，就是很容易忘掉以前的教訓的了。第一個告訴我不能這么干的人其實是小學三年級的數學老師。當時我因為懶得寫字，所以計算應用題的時候省了幾步，被批評了。故事就從狀態機開始。文法我就不重復了，見上一篇文章。現在我們從狀態機開始。第一個狀態機是直接從文法變過來的：然后我們把所有的非終結符跳轉都通過Shift和Reduce連接到該非終結符所代表的狀態機的狀態上面，就會變成下面的圖。具體的做 閱讀全文

摘要： 上一篇博客講到了構造符號表的事情。構造完符號表之后，就要進入語義分析的后一個階段了：構造狀態機。跟我以前寫的如何實現正則表達式引擎的兩篇文章講的一樣，自動機先從Epsilon Nondeterministic Automaton開始，然后一步一步構造成Deterministic Automaton。但是語法分析和正則表達式有很大不同，那么這個自動機是什么樣子的呢？（對學術感興趣的人可以去wiki一下“下推自動機”）下推自動機和有限自動機的區別是，下推自動機擴展成普通的自動機的時候，他的狀態的數目是無限的（廢話）。但是無限的東西是沒辦法用編程來表達的，那怎么辦呢？那就加入一個不定長度的“狀態描述 閱讀全文

摘要： 群號：31724825 在最近這幾年里，一起討論編譯器的人也不多，一般都是ooseven、@裝配腦袋、@空明流轉(<--高手，要跪)、@belleveinvis等這幾個人。而且也零星有一些我也不記得叫什么名字的在我的評論里面提出過一些很好的建議，讓我得到了充分的學習。因此我想，如果有興趣的人可以加進來一起討論的話，應該不僅對我，對大家也是有好處的。而且我本人喜歡的領域也比較分散，譬如圖形界面、軟... 閱讀全文

摘要： 上一篇博客講到了構造語法樹的問題。有朋友在留言問我，為什么一定要讓語法分析器產生語法樹，而不是讓用戶自己決定要怎么辦呢？在這里我先解答這個問題。 1、大部分情況下都是真的需要有語法樹 2、如果要直接返回計算結果之類的事情的話，只需要寫一個visitor運行一下語法樹就好了，除去自動生成的代碼以外（反正這不用人寫，不計入代價），代碼量基本上沒什么區別 3、加入語法樹可以讓文法本身描述... 閱讀全文

摘要： 就像之前的博客文章所說的，（主要還是）因為GacUI的原因，我決定開發一個更好的可配置輕量級語法分析器來代替之前的落后的版本。在說這個文章之前，我還是想在此向大家推薦一本《編程語言實現模式》，這的確是一本好書，讓我相見恨晚。 其實說到開發語法分析器，我從2007年就已經開始在思考類似的問題了。當時C++還處于用的不太熟練的時候，難免會做出一些傻逼的事情，不過總的來說當年的idea還是能用的。從那... 閱讀全文