最近想要自己寫個簡單的 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