syntax highlight/parser/compiler 的難度

[yllan (藍永倫)]

    最近想要自己寫個簡單的 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
→ tinlans:這麼容易給你學起來我要吃啥飯 XD
→ tinlans:說笑的，不過 parser 只是 compiler 的 10% 而已。
→ tinlans:其實這內文主軸跟 compiler 還扯不太上邊。
→ tinlans:這年頭做這行的，普遍比較重視編譯出來的程式執行效率，
→ tinlans:對 parsing 速度這東西反應相當冷淡，討論也頗有限。
→ tinlans:這其實比較偏 editor 跟 UI 設計的那一塊。
→ yllan:是的，可能是我標題有寫 compiler 不太恰當
→ yllan:本文只是想問問看有沒有這方面的資料可以參考
→ airzone:有看過 http://www.scintilla.org/ 嗎?
推 PCIT:可以考慮一下，實做在cloud9ide :)