最近想要自己寫個簡單的 code editor 來玩玩看，想做這些功能： * syntax highlighting * auto-completion * code indent 想了幾天，有些粗淺的心得和疑問，先從看起來最簡單的 syntax highlighting 來談起。 查了像 TextMate 以及 Espresso 這種可以自定義語法的 editor， 他們的作法基本上都是用 regex 為基礎的 match rule 替各字串 加上 tag (TextMate 中稱為 scope, sugar 中稱為 zone)。 這些 rule 可以互相或自我參照，做出成對括號批配之類、原本用 regex 做不到的事情。 http://manual.macromates.com/en/language_grammars http://blog.macromates.com/2005/introduction-to-scopes/ http://wiki.macrabbit.com/index/Syntaxes/ 雖然這只能處理某 CFG 的子集，某些極端狀況無法處理，但就實用 上來說這方法表現得還不錯。 如果要真正得到完美的 syntax highlighting，就得去 parse 整份 文件… http://tinyurl.com/22y36h (js2-mode: a new JavaScript mode for Emacs) 然而現在面臨的問題並非只是靜態的 parsing，而是要面對 coder 隨時改 code，你必須即時將變動中的 code 給 parse 好！ Steve Yegge 採用兩種方法，一種是 incremental parse，然而太難 失敗了。所以他只好採用 async parse，每次都重新 parse 整份文件。 若 parse 完之前 code 有任何修改，就放棄這次 parse 成果，重新 再來。（似乎這也是 Eclipse 或 IDEA 的作法？） Auto-Complete 則一定要去 parse code 得到 AST。然而麻煩的是， 通常程式打到一半並不合文法，要怎麼 parse 呢？例如： System.o_ 要怎麼得到 System.out 呢？也許有個作法就是把目前游標前面的 token 給刪掉，加上 ; 強制結尾形成有效的 statement，再分析 AST。 不過仍然終端 case 百百種。對不同語句要怎麼有效補完也是個問題。 在設計 IDE 所需要用到的功能時必須假設 code 變動頻繁、 syntax 長時間不正確的情況。傳統教科書裡的靜態演算法可能不敷需求，不 知道有沒有比較新穎的方法可以處理這種問題？ 另外分享一下 survey parsing approach 時看到的一些資料。 傳統的作法是用 lex/yacc, flex/bison 之類的工具，寫文法產生出 一堆 automata 表格。有效率，但是門檻很高，而且產生的 parser 根本看不懂。 XD 之前有篇論文標題是 "yacc is dead," http://arxiv.org/abs/1010.5023 利用 parser combinator 實作易懂的 parser。效率號稱不太糟。 然後有人寫了篇 yacc is not dead 反駁說這效率是 exponential。 http://research.swtch.com/2010/12/yacc-is-not-dead.html 作者又反駁雖然這 exponential，但一般情況下還挺快的： http://matt.might.net/articles/parsing-with-derivatives/ 其實現在的 scala standard library 就有 parser combinator， 雖然好像速度不快，但是易讀性上真的好很多。 http://www.codecommit.com/blog/scala/the-magic-behind-parser-combinators 我還滿好奇的，現在號稱 compiler 界最先進的 open source project LLVM，其 subproject -- clang 的部分好像也是自己手打 parser 的。 為什麼不用 yacc 呢？ 話說回來，llvm 似乎很值得學一學。不知道有沒有好的 compiler 課本 是拿 llvm 當範例的？市面上連 llvm 的書都很難找到。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.167.202