※ 引述《[email protected] (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