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

[d8888 (Don)]

昨日奮鬥到3:30AM，總算看到「ALL TEST PASSED」三個字。功力是新手
，身體卻是接近30歲的大叔。爆肝解bug真的有點受不了啊。


個人心得：

1. 強烈建議使用parser generator：

理由除了前面許多大大指出的：
 a. Parser generator可以一次產生幾千幾萬行的code ，節省很多時間
 b. generator的bug會比分散在手寫parser 200個不同地方的bug好處理

這些理由之外。我認為還要加上
 c. 好修改。
   （修訂：寫PA7的時候還有可能大改 parser好幾次，至少我是這樣）

舉個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裡面就非常多。


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整個改掉都相對容易。容易應付特殊狀況，這是第二個理由。

b. recursive descent parser的roll-back問題

我的recursive descent parser還是會參照First, follow。要match
grammar的時候就檢查production左手邊symbol的first，follow跟當
下處理的位置符不符合，不合就跳過production。

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

d. 不產生parse tree or AST

這明顯是偷懶，之後都要還。但PA6只要OK,BAD的答案。如果真的想
取巧。這題可以先暫時把parse tree，AST全部都省掉，還是可以過
。只是這是註定要還的。

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裡面。

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。


這是睡眠不足的情況下寫出來的。個人不是本科系，功力也很淺。如
果說錯還請各位板大高手指正，謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 77.247.181.164
※ 編輯: d8888           來自: 74.120.15.150        (09/23 12:14)
推 azureblaze:我覺得不生AST出來比對非常危險 PA6的答案太寬鬆了
→ azureblaze:或者說沒有ast根本不知道bug出在哪
→ azureblaze:哇 deadline剛好到了
→ d8888:不生AST其實是錯誤做法。當初這樣做純粹是搶時間。
→ d8888:至於parse正確與否我是進出function的時候log頂著。
→ d8888:哪幾個symbol「吃掉」哪幾個token還是看的到的。
→ d8888:對了。我的ParserGenerator還不支援 ( ) * ?
→ d8888:所以grammar被我大修過XDDDDDD。
→ d8888:用了一堆怪招總算在deadline當天3AM搞定啊，o桀o桀o桀o桀o桀
※ 編輯: d8888           來自: 220.143.177.147      (02/01 22:05)