Re: [請益]請問PARSER

看板Programming作者halajohn (Wei Hu)時間18年前 (2007/03/10 02:09)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串3/4 (看更多)

※ 引述《horngsh.bbs@bbs.nchu.edu.tw (itsoho.myweb.hinet.net)》之銘言： : 弟想寫一個PARSER, 如可以剖析ANSI BBS圖片, 還有HTML的PARSER, : 該用什麼樣的演算法較利落呢? : 感恩您! 你要寫一個 parser, 就必須先有 grammar, 你要分析 ANSI BBS image, 就必須要找到或自己想出他的 grammar, 你要分析 HTML 程式碼, 就要有 HTML programming language 的 grammar. 這是第一步. 要說容易也很容易, HTML 的 grammar 是標準的, 應該不難找. 要說難也很難, ANSI BBS image 的 grammar 我想應該沒有, 你可能得自己想一個. 有了第一步之後, 你就可以開始分析你的 grammar. 所以在分析 ANSI BBS image 或 HTML codes 之前, 你得先分析你的 grammar. 分析 grammar 這一步... 到目前來說, 都還是黑魔術. 分析主要的目的, 是要移除 grammar 中模零兩可的部份 (ambiguity). 當 grammar 大的時候, 要怎麼看出所有的 ambiguities, 還真是非常的不容易. 縱使把所有的都看出來了, 要解決他們也是非常的不容易. Ok, 假設你現在已經 "正確" 的分析完了, 要開始寫你的 parser. 一個 parser 的架構大概可以分為兩大類, LL 及 LR. LL 比較直覺, 可以用 table-driver 或 recursive-descent 的方法, LR 比較不直覺, 但就理論上來看比 LL 強大, 但他只能用 table-driven 的方法. 而且 LR 比較難以寫出容易 debug 的 parser. 我個人 perfer recursive-descent parser. LL 的缺陷在於 grammar 本身不能有 left-recursion, 目前有制式的 algorithm 可以 remove grammar 裡面的 left-recursion, 比方說 Paull's algorithm 或 left-corner transform, 然而這又會引發其他的問題. 比方說數學運算子通常是 left-associativity, 這在 grammar 裡面是用 left-recursion 來表示. 當你把 left-recursion 移除而改用 right-recursion 時, 該運算子的 associativity 已經變為 right-assiciativity. 當然這也有另外的 trick 可以解決它. 縱使這些你都了解了, 通常你需要寫的是一個 LL(k) 的 parser, 除非你的 grammar 夠簡單到可以是 LL(1). 但要寫一個 LL(k) 的 parser, 最簡單的方式是找出最多 k 個 lookahead symbol. 這.... 很花時間或空間. 除非你當初設定的 k 是 1 或 2 這種小數目. 大的數目來說就不容易了. 拉哩啦匝說這麼多, 你可以想見 parser 這玩意還真是不容易. 其實就 compiler 來說, front-end 端的 parser 不比 backend 簡單, 裡面的黑魔術還多著, 目前也沒有啥完整的 total-solution 存在. 想要寫一個 parser, 建議你先念念一些 programming language 或 compiler 的說, 然後再來考慮看看你要不要寫一個 parser 或者就用某個已經有現成的 parser generator, 比方說 ANTLR, JavaCC, Yacc(Bison), SLK...etc 來產生你的 parser, 但不管怎麼說, 有適當的 background knowledge 都是必須的, 只是 parser 這門領域所需要的 background knowledge 還真是不少. 祝好運. -- http://www.csie.ntu.edu.tw/~r88052/main/tw/frame.html -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.216.61