syntax highlight/parser/compiler 的難度

看板CSSE (電腦科學及軟體工程)作者yllan (藍永倫)時間14年前 (2010/12/30 01:42)推噓1(1推 0噓 9→)

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

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