推 Fenikso:b. 開gdb. 或是麻煩一點的backtrace()不知道有沒有禁用 01/31 23:51
→ Fenikso:c. 我那時候是(舊的)死線快到了 想說先過了再說 01/31 23:53
推 Fenikso: testcase來一個殺一個就過了 01/31 23:56
就在剛剛，PA7終於通過了
（謎之音：PA8你一個字都沒動....）
PA7的特色就是事情又多又雜。如果PA6像是要你解一個大任務（如：寫出parser
generator），PA7就像是要你解一個大任務加上一百個小任務，所以你的bug會分散在100
個不同的地方。一邊流眼淚解Segmentation fault，一邊流鼻涕解你output跟答案不同的
地方，還要順便再翻已經翻過N次的C++ standard。而C++ standard我坦白說沒有看完，
但實際上就是看完了，還是會有小東西記不住，要等segmentation fault或是答案不對，
再去翻書才會發現「淦林老師，還有這句話.....」
因為PA7實在是 真 他 喵 的 雜，可能這次心得分享要分好幾次寫吧。一樣，個人
的功力不是頂尖，越寫越發現自己像個新手。如果有高手版大願意不吝指正，末學感激不
盡（這也是寫文目的之一，高手都愛裝弱，一定要讓他們發現我比他們更弱還敢寫垃圾文
，高手才會願意發文）
1. 先把test case看完
把各個case資測和正確答案都看過。坦白說這是取巧。但PA7實在太難。我看了五六遍以
上吧。
2. 關於standard閱讀的部分
PA7，PA8是在一起的，我基本上讀完了CH3，CH7-1全部，CH7-3全部，CH8-3全部。
寫PA7，只要standard重點少看一句話，都有可能造成design error然後gg。所以重要
chapter全部都要精讀。個人強烈建議用個可以畫線的pdf reader。遇到不熟的，預計會
忘記實作的，全部畫紅線。第一次就把東西弄對，比寫了老半天發現少看一句話，結果全
部得砍掉重練來的快樂多了。
3. 寫作習慣
PA7我強烈建議幾個寫作小習慣，雖然大家應該都會吧...
a. 任何function，一進去就對所有參數檢查一遍，看跟你腦中的假設合不合，不合馬上
丟個uncaught exception。這個方式幫我抓到了無數bug，一個莫名其妙但至少有內容的
exception，比一個"segmentation fault"或是程式沒報錯，但算出來就是不對好太多了
.....
b. 用記事本或更好的東西當tracker，上面紀載你想到但還沒寫或做的東西。PA7你要處
理的問題非常多，不這樣做常常做了左邊忘了右邊。
4. 張老師專線關心您：珍惜生命，從PA6開始使用Parser generator！Recursive
descend parser是你的好朋友。
我寫PA7的過程，Parse tree和AST的產生方式大改了無數次。用Parser generator，只要
改樣板，改generator本身，重跑一次grammar，又是一條好漢。要是當初Parser是手寫的
，以我的功力這次就是直接GG。
我Parse tree發生甚麼狀況呢？
假設grammar
S: A
A: B
B: C
D
我原來的parser一定要到D也被match完，才會把D的parse tree node(後稱PTN)加入B的
PTN，然後把B的PTN加入A的PTN，A的PTN再加入S的PTN。在PA6只要決定東西合不合
grammar，對class name，typename....等等的判定都是mock function所以這樣做沒問題
。
但PA7 parse tree和AST的產生都是動態的，隨著parse的過程不停變化。很多時候，在
match PTN的時候都需要「當下全部」Parse Tree和AST Tree的資訊。比如決定一個token
是不是namespace-name。一定要把整個AST翻出來，做個name lookup看看某token到底存
不存在，存在的話是不是namespace的名字？才能決定你眼前這個TOKEN到底是不是
namespace-name，又譬如某expression（舉例，PA7還不會碰到）：
x * y
這個expression可能是y is a pointer to x，x is a type。也可能是「X乘Y」，一切都
看parse的當下X是甚麼而決定。所以Parse tree不能match完再建，match甚麼東西的時候
，parse tree就要包甚麼東西，以剛剛範例grammar來說，假設我現在在決定眼前的東西
是不是C，我的parse tree、AST當下就要有S-A-C的tree。這樣萬一你要match的東西要翻
AST才有東西可以翻。光是為了這個東西，我就改->除錯->改->除錯...了好幾個循環。我
不能想像如果我之前PA6的parser 20000+行都用手寫，每次重改都要看20000行code，會
是甚麼悲劇。
另外一個例子是我first follow計算方式不正確，因為我念的教科書沒考慮*?+對first
follow的影響，我自己搞就搞錯了。用Parser generator，我把計算的code改好，重跑
generator就搞定。用手寫，你要把所有symbol的first follow都全部手算驗證，不但麻
煩，而且一個地方寫錯，就會埋下一個不會馬上爆炸的bug，然後說不定你在寫最後一題
的時候才爆發出來，沒有錯誤訊息沒有exception可是你的input就是會被你的compiler讀
錯，阿這時候你額外寫了那麼多東西你是要怎麼debug？你想的到是在first follow的地
方算錯出bug嗎？所以，強烈建議使用parser generator。
4. Event-based programming、DOM-like behavior
個人這次把parser實作出類似DOM選擇器的東西。code裡面常常有類似
target->Children("type-name")->Children("TT_IDENTIFIER")的東西。個人感覺至少
對我而言使用起來很方便，而且好實作。
另外就是我的parser generator加入類似發event的機制。我在grammer之中可以指定某個
symbol要有event。然後parser在match的時候，就會在剛開始match，每match
production中一個symbol，match完整條production，發現不match要fallback的時候自動
去呼叫特定function，我就在那些function中放入類似event handler的東西。所以我的
parser可以做到類似「成功match simple-declaration的時候自動呼叫XXX function」的
功能。這樣做個人以為好處有幾個
a. Parser很乾淨，不用動到generator產生出來的code。我實際上讀/寫AST的code可以跟
generated code完全分開。隨時可以改grammar然後重跑generator，新的generated code
可以一行不用改就沿用原本讀/寫AST的code。
b. grammar可以很乾淨，我這次根本沒用PA6的grammar，直接PA7 grammar照之前PA6的經
驗（那些要先後match等）小改以後，就generate code了。grammar很乾淨，代表我要在
generated code裡面插東西抓bug很快，我handle AST的code不用顧慮到一堆根本沒有實
作的symbol，code清爽解bug就會快。缺點是我不同題的parser會不相容....
5. Complicated type
typedef int CC(char, char);
typedef CC *K(int,double);
寫之前必須先搞懂類似這些複雜的type到底要怎麼分析解讀，這是比較困難的地方之一，
但不是最難的，資測裡面有更噁心的sample
6. Cache mechanism
我的event base programming導致我原來的cache mechanism必須要改。我原本cache是存
整個parse tree的sub tree。但是把subtree整個存起來、拿出來會導致原本應該觸發的
side effect不會被觸發：比如發出event呼叫AST handling function... 所以我的cache
改成存「在nth token的時候，X symbol可以用第i個production match」的資訊。變成少
try一些不必要的production，然後該觸發的side effect還是會觸發。
7. AST
我其實沒有建獨立的AST。我每個AST的node都附屬於某個parse tree的node。所以若
Parse tree node A為node B的parent，對應的AST node A一定也是node B的parent。更
動parse tree的時候就等於同時更動AST。就不用煩惱parse tree改的時候，AST的哪個
node parent要改誰之類的問題。AST node一律當成parse tree某node的member處理。
這個方法使用愉快，但是遇到extended namespace會有小問題，但可以在AST node裡面多
擺幾個指標，然後在AST namespace match/unmatch function中去維護這些指標來解決。
8. 寫作順序
PA7大概可以分成幾個component：name lookup和建樹。name lookup 我分成幾個小東西
做
a. 基本版lookup：只看single scope，甚麼using directive全部不考慮。可以加filter
指定要搜哪些名字（搜全部，搜namespace....）。會把look up結果，發現的using
directive傳回去。可以用參數決定遇到alias declaration這些東西，要回傳declaration
本身還是傳他指向的目標。
b. Unqualified lookup：會呼叫基本版lookup，然後根據傳回來的using directive再搜
新scope。scope內找不到就向外面一層找etc.
c. Qualified lookup：遇到A::B::C，會先在當下的scope用unqualified lookup找A，然
後把找到的結果在single scope中找B找C。
有了lookup以後，才有辦法順順建AST，因為產生parse tree和AST，過程中都要一直
lookup。但實際上會兩者交替做，做一點lookup做一點建樹，做一點建樹再做一點look
up.....
9. 結尾
a. 我這題還是用printf來解bug，只是debug資訊丟clog，真output丟cout，然後全部導
向到檔案。很多時候我必須知道某個錯誤是parse tree建到哪個地方發生的。有完整的
parse log對我很有幫助。
b. 請問有板友有「方方便便看stack dump」之類的方法嗎？不然看到exception常常還要
猜從哪裡丟出來。我預計這個需求在後來會越來越強，我自己也在找。
c. 更重要的，有沒有強者有PA8解題心得的分享啊。我PA8除了某些檢查東西合不合規矩
（有無重複declaration，有沒有array of function, etc.）以外，還是白的啊啊啊啊啊
啊啊啊。
（謎之音：你這篇文章其實最想表達的是這句吧....）
我review我PA7的code以後，想到甚麼東西再作補充，謝謝各位的收看以及指教<(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.143.79.143
※ 編輯: d8888 來自: 220.143.79.143 (01/31 22:35)