Re: [情報] C++大師認證 (PA6)

[LPH66 (f0VMRgEBA)]

※ 引述《d8888 (Don)》之銘言：
: 昨日奮鬥到3:30AM，總算看到「ALL TEST PASSED」三個字。功力是新手
: ，身體卻是接近30歲的大叔。爆肝解bug真的有點受不了啊。
我也來分享一下好了XD

原本我是要把中秋假期丟進這裡來的

因為在上上週六才發生我沒收到我用的學校工作站要清暫存空間 /tmp2 的信

結果最新進度跟著放水流的慘劇

(我們工作站為了在多部機器上同步個人空間所以個人目錄是在 NFS 上

 但這種會大量讀寫檔案的用 NFS 會有速度上的悲劇

 所以我才放到位置在機器本身磁碟上的 /tmp2

 沒想到一個不注意就放水流了...)

好在我在慘劇發生前數天有做了本地備份

(其實就只是個另外放的 git repo 拉回自己的電腦

 只是那一週改的比較勤快所以忘了拉回來而已)

雖然那個 git repo 也跟著放水流了所以有兩個 issue 跟一個大結構改動要重做

好在都還記得要做些什麼所以沒幾天就改回來

順道把放水流之前碰到的 issue 也解掉之後發現已經 ALL TEST PASSED

所以就把 ambiguity 放一邊先交卷然後快樂回家過中秋了 XD

最後是在收假前 (= 昨晚) 花了 40 分鐘解決 ambiguity 這樣

然後前幾天才發現它的截止時間是美西時間 9/22 11:59pm

差不多是台灣時間今天下午四點左右所以昨天才放心到晚上才來解這個問題 XD

: 個人心得：
: 1. 強烈建議使用parser generator：
: 理由除了前面許多大大指出的：
:  a. Parser generator可以一次產生幾千幾萬行的code ，節省很多時間
:  b. generator的bug會比分散在手寫parser 200個不同地方的bug好處理
: 這些理由之外。我認為還要加上
:  c. 好修改。
: 舉個grammar為例：
: A:
:    B     //production 1
:    B C   //production 2
: 正確的Parser應該要先match production 2，不行才去match production
: 1。如果一律先match production 1，會導致多出來的C可能無法被match。
: 導致最後結果的錯誤。如果用Parser generator，以我寫的來說，只要把
: grammar中production 1, 2上下兩行互換再重新產生parser，bug就解決了。
: 手寫parser就要跳進茫茫code海裡面改code。改code即使再容易，反覆下
: 來我相信出錯的機會會比改grammar多。萬一手寫parser裡面相關的code
: 有一些「特化」，那修改難度更高，而且有的bug會埋在grammar中很深
: 的地方，可能一次要處理好幾個non-terminal
:  symbol的production，改錯的機會更高了。這種需要修改production
:  match順序的情況，在test suite裡面就非常多。
這邊我是參考了前面 azureblaze 提到的先試 match 最長的 rule

把大部份的這種狀況給自動解掉了

例如 operator new / operator new []
     if(){} / if(){}else{}
     等等

少部份也是只要如上所說手動調換順序就能解

只有一個例外是在解 ambiguity 時要先 match declaration

但是 expression-statement 那條 rule 有 attribute* 所以比較長

昨晚我是直接硬把有 attribute* 的拆開成另一個 nonterminal 把它解掉

其實應該可以學 yacc 用一個類似 %prec 的東西指定優先度的

(或許之後就會改了...)

: 2. Parser generator的design choice
: 當初為了讓parser generator好寫，做了幾個design上的重大決定，事後
: 證明對PA6都是有幫助的。當然所謂好壞都是對我個人而言，充滿主觀，
: 僅供參考。我的功力也只是新手層級，觀念錯誤就請大大們痛鞭吧，
: 不要讓我污染別人XD
: a. 用Recursive descent parser而不是標準table-driven LL(1)
:    parser：
: 書上說Recursive descent parser對人類來說會比table-driven LL(1)
: parser來的直觀。對PA6的影響就是寫Parser generator也變的直觀。我
: 寫Parser generator是先寫個grammar很小的Recursive descent
: parser。能動以後把code弄到Parser generator裡面當樣板。而
: Parser generator就讀取PA6 grammar後，把樣板裡面的function name，
: symbol name換一換寫到檔案去，最終版PA6Parser就弄出來了。事後證明
: 產生出來的code對我非常直覺（當然醜不醜，冗長不冗長是一回事），
: debug的時候也容易看出Parsing哪裡出問題。好寫，好懂，好debug，這
: 是第一個理由。
: 更重要的理由是：C++的grammar syntax analysis和sematic
: analysis有時必須相互夾雜，不能完全套context free grammar的觀念
: 處理，這讓我非常擔心。
: 以PA6來舉例，class-name要match TT_IDENTIFIER之前還得確定
: TT_IDENTIFIER是class name。decl-specifier-seq還要確定非const，
: volatile的type-specifier最多只能有一個....。我不知道會不會讓標
: 準table-driven LL(1) parser變的更難寫，或是根本不能用，而用
: Recursive descent parser讓我感覺相對安全。在Recursive descent
: parser偷插東西應付C++ grammar的特殊需求，或是直接把某個matching
: function整個改掉都相對容易。容易應付特殊狀況，這是第二個理由。
這個 design choice 在我的 PA6 寫作過程中做過兩次重大改革 (讀音: 砍掉重練)

一開始就有想到用 parser generator

最初寫的是比較醜一點的 recursive descent parser

用了一堆 template 想試著用 yard 的方式來做省點功

(關於 yard 可以參考 yoco 的介紹文 #19U8iWOo )

弄到一半發覺這些個 template 真是難搞所以砍掉重寫 LR

可是寫好了用在 PA6 文法上發現怎麼 conflict 這麼多  根本解不完

才又重回 recursive descent parser 的懷抱

只不過這次不搞 template  直接用普通的方式來寫

這段時間的心得是: meta-meta-programming 真的不是人在做的 = ="

(用 codegen 生出大量使用 template 的這種 meta-programming

 只好把它叫做 meta-meta-programming 了 (大誤))

semantic action 的部份我非常同意

做成這種樣子的 parser 之後插入一些動作就變成單純把適當的動作插在適當的地方

比較大的困難反而是為了搞定 * + ?

試過把這些 * + ? 展開在 rule 本體裡但發現要跳出變得很複雜

加上為了下面提的 rollback 加了不少狀態儲存的程式碼  整個亂七八糟

(特別是我的 PA1~PA5 的結果是個 token stream 而不是 token array

 這讓狀態儲存更難搞...當初為什麼要選這種方式呢 (眼神死))

最後是乾脆把所有 * + ? 當成特別的 nonterminal 來弄才總算有個比較清爽的結果

: b. recursive descent parser的roll-back問題
: 我的recursive descent parser還是會參照First, follow。要match
: grammar的時候就檢查production左手邊symbol的first，follow跟當
: 下處理的位置符不符合，不合就跳過production。
還好當初 compiler 上課時有學到所謂的 predict set

它可以拿來選擇看到這個 terminal 時要去哪個 rule

(一個 rule A→rhs 的 predict set 定義是 first(rhs),

 或當空字串在 first(rhs) 裡時是 (first(rhs)-空字串)∪follow(A)

 這樣當看到一個 terminal 在某 rule 的 predict set 就表示可以選它

 這個應該就相當於你的「檢查 first 跟 follow 符不符合」了)

不過因為這份文法顯然不是 LL(1)  在要不要做左分解的方面考慮了好一陣子

(最初的那份 template 版時有先做了左分解結果發現出了一大堆新的 nonterminal

 這也是當初我會放棄 template 版的原因之一)

中途也考慮過要不要改 LL(2) 或什麼  不過這樣就要改寫 first & follow 只好放棄

最後我做的是只聰明一些些的方法:

如果候選 rule 有一個以上時  先看有沒有大家都有的 token

有的話就先 match 掉再來用 partial predict 挑 rule

(實際上做的是將所有候選 rule 的第一 token 集合起來

 然後每次就試試這個 token 行不行  不行就下一個 token

 第一 token match 掉後面還有共同 token 的話

 在 codegen 裡遞迴地產生 match 第二、第三等等 token 的程式碼)

相對的 rule 的部份就多了一個參數表示跳到第幾個 token 繼續

方法是這樣: (這是 gen 出來的程式)

bool MatchRuleXX(int skip)
{
  //local declaration + save point
  switch(skip)
  {
  case -1: //沒有跳過
    //some initialization
  case 0:  //有因為多選一而先做掉上面的初始化
    //token 1
  case 1:
    //token 2
  ...
  case N-1:
    //token N
  case N: //有時進來時 rule 已經全部 match 了就會跳來這
          //例如 operator new / operator new []
    //finalization if matched
    return true;
  }
  //finalization if not matched
  return false;
}

中間沒有 break 所以跳下去後會一直做下去

如果要不給 match 就 break 出來

所以做到 //finalization if matched 就表示 match 成功這樣

然後因為會不給 match 總是某個條件成立了  所以弄了個巨集

產生的程式跟自己加的 action 都用這個巨集來表示若這條件成立就不給 match 這樣

: c. Parser generator的其他功能。
: 我的Parser generator支援插hook和Unmatch。在grammar檔用某些方
: 法標註一下，match function就會去呼叫我指定的hook。production
: match失敗的時候也會自動呼叫Unmatch，如此一來萬一match的symbol
: 有side effect（比如堆疊存取）可以把side effect處理掉。這主要
: 用來處理<，>配對堆疊。
: 至於太特殊的狀況，如decl-specifier-seq。我的parser generator
: 可以產生match function之後再整個自動comment掉。我再把comment
: 掉的code複製出來用手大幅修改，處理特殊需求（如非const，
: volatile的type-specifier最多只能有一個）。為什麼要產生出來然
: 後comment掉，不乾脆不產生就好？因為這樣我才有東西可以拷貝來
: 改啊XDDDDD
這個部份我的解法是拼命產生狀態儲存點

差不多是每進一條 rule 就存一次 XD

同時聯想到 java 的 stream 有所謂 mark 的功能就借名字來用了

不過為了這個功能也是忙乎了好一陣子

有時還因為對應的儲存點沒放出來要在上一層自動放出來弄得亂七八糟...

hook 倒是沒想到過

這應該可以把我目前為了蓋 AST 碰到的一個問題給解掉  之後來試試看好了

< > 的配對我是照 design note 建議的用一個內部堆疊  跟著狀態儲存點一起存

當 terminal 要拿出 ( [ { 時推一個 false 進去
            要拿出 ) ] } 時彈一個值出來

然後在需要 close 的 < 推 true 進去  在 close-angle-bracket 彈出來

這樣平常的 > 跟 >> 就只要看堆疊頂是不是 true  是就不給 match 就行了

decl-specifier-seq 或之類的部份我是照著 PA6 說明先放著

之後要弄的時候再寫起來就好  (或許在蓋 AST 時就得處理也說不定)

: d. 不產生parse tree or AST
: 這明顯是偷懶，之後都要還。但PA6只要OK,BAD的答案。如果真的想
: 取巧。這題可以先暫時把parse tree，AST全部都省掉，還是可以過
: 。只是這是註定要還的。
偷懶+1 (所以我的程式有大量的 memory leak (笑))

我已經打算在寫 PA7 前先把這個債還掉了

不過相對的這會造成一些東西不容易除錯

我這一陣子解 issue 都是盯著數十 K 的 parse 過程紀錄

看到底是哪個地方走錯路了  實在是頗累...

: 3. 用Parser generator不會造成對grammar不熟？grammar怎麼弄熟？
: CPPGM官方說用寫的會比較容易熟grammar。但我認為手寫parser勢必
: 讓專注力放在寫程式，而不是弄熟grammar。一次做的事情太多反而會
: 無法專注在grammar上。
: 我讀grammar的方法，是遇到看不懂的symbol一律丟Google。有的
: symbol牽涉到c++ 11的new feature，如lambda function。那就直接
: 把feature稍微搞懂，再回頭來看grammar就容易領會。至少就我個人
: 而言，這比直接跳進spec念那些像盧恩符文的東西好懂，更容易看懂
: 「背後的意思」
: 除了Google之外。要弄懂grammar中哪個symbol展開會變哪個symbol。
: 哪些symbol之間互相有關...這種問題。我是直接唸PA6.gram。反覆
: 看個三四遍，就有了大概的印象。直接讀官方給的那些html，我個人
: 會容易迷失在局部的grammar裡面。
我反而在那些 html 裡追得很愉快...

也許是因為我是拿著我的 parse 過程紀錄跟 html 對著跑

並沒有從頭走過一遍

所以感覺還滿有用的

C++11 feature 則是因為打 PA1 開始我的程式就是在預設支援 C++11 的環境下寫

所以一些 feature 邊寫就會邊熟起來

像 raw string 在這次作業幫助超大  寫起來幾乎就像是 heredoc 了 XD

(相對的我的 codegen 程式的縮排就很糟糕

 因為 codegen 的 code 跟要輸出的 raw string code 混在一起

 偏偏我找到的 vim 對 C++11 的 syntax highlight 檔不支援 raw string

 所以 codegen 那段的縮排看起來就是徹底的亂七八糟 XD)

cppreference.com 在這方面很方便  有什麼 feature 上去查就有

好些個東西也是看到裡面有才學到的

而 first 跟 follow set 我是自己求  反正之前修課有學到怎麼做

那些 html 在這裡頂多就是做完後抽樣對答案而已

這一段是最早的 template 版時就已經做好的事

可以算是第一版程式碼對最終版本的貢獻 XD

(後來的版本都是砍掉 codegen 部份重寫而已

 first 跟 follow 都沒有動到過)

: 3. 其他雜七雜八問題
: a. ambiguity：其實對PA6沒有影響。因為PA6只要知道OK, BAD，而
: spec上那些grammar ambiguity不影響「能不能parse」的結論。只對
: 未來的assignment和最終compiler有影響。
: 我處理的方式是直接去問官方給的recog-ref。把ambiguity丟進去
: 跑跑看。然後調我自己grammar production的順序，讓它可以跑出
: 跟recog-ref一樣的parse tree。
: 舉例：在S的情況下，input P1可以match A, B，spec指定要當成
: A。input P2類似P1但只能Match B。我就把P1, P2都丟入recog-ref。
: P1結果：
:   S
:      X
:             A
: P2結果：
:   S
:      B
: 回頭翻grammar：
:  S:
:     B //production 1
:     X //production 2
: 看到這樣，我就知道要把 production 1,2 互換。這樣能match A,
: B的東西就會優先match A。
官方的 recog-ref 是好東西 XD

靠它我才能在不用盯著 parse 紀錄之下 40 分鐘解掉 ambiguity XDD

: 這是睡眠不足的情況下寫出來的。個人不是本科系，功力也很淺。如
: 果說錯還請各位板大高手指正，謝謝！
會有這一篇也是因為我最後的做法跟你的竟然有七成的相似度

所以就也寫一下我的方式做個交流 :D

--
1985/01/12 三嶋鳴海 1989/02/22 優希堂悟 1990/02/22 冬川こころ 1993/07/05 小町
つぐみ 歡迎來到 1994/05/21 高江ミュウ 1997/03/24 守野いづみ 1997/03/24 伊野瀬
チサト 1998/06/18 守野くるみ 打越鋼太郎的 1999/10/19 楠田ゆに 2000/02/15 樋口遙
2002/12/17 八神ココ 2011/01/11 HAL18於朱倉岳墜機 ∞與∫的世界 2011/04/02 茜崎空
啟動 2012/05/21 第貮日蝕計畫預定 2017/05/01~07 LeMU崩壞 2019/04/01~07 某大學合宿

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 210.69.49.38
→ purincess:我有收到/tmp2要清的信說@@ 該不會是因為我沒*畢*業*
推 d8888:好文推一下，內文有不少東西我得Google一下XDDD
→ d8888:話說LPH66大大您有考慮用bitbucket嗎？
→ d8888:我用bitbucket把repo設成private目前使用愉快中XD
→ d8888:code存bitbucket不怕水煙火焚或是強盜搶走電腦，蠻方便的XDD
→ LPH66:主要是怕跟 honor code 條款衝到...不過現在我把 git repo
→ LPH66:放到 NFS 去了 (畢竟 repo 本身讀寫不可能太頻繁)
→ LPH66:所以應該是不用怕再次發生同樣的狀況了 XD
→ purincess:看來可以開放出租我的VPS (?
→ purincess:^給大家放repo
→ suhorng:bitbucket有免費private repository, 會衝突到嗎?
→ suhorng:就別人都看不到
推 damody:推
推 yoco315:我是用 bitbucket 喔，有免費的 private
→ yoco315:open source 我都放 github, 不能公開的我都放 bitbucket
→ yoco315:現在 bitbucket 也支援 git 了，推薦一下 XD
→ LPH66:感謝大家推薦，這個週末來試用看看 XD