2003
01 02 03 04 05 06 07 08 09 10 11 12
2006
01 02 03 04 05 06 07 08 09 10 11 12
2007
01 02 03 04 05 06 07 08 09 10 11 12
2008
01 02 03 04 05 06 07 08 09 10 11 12
2009
01 02 03 04 05 06 07 08 09 10 11 12
2010
01 02 03 04 05 06 07 08 09 10 11 12
2011
01 02 03 04 05 06 07 08 09 10 11 12
2017
01 02 03 04 05 06 07 08 09 10 11 12
 
Jun
27
2011

Parsing Code

最近在 survey 一些 code editor 的相關資料,想達到這些功能:

  • syntax highlighting
  • auto-completion
  • code indent

想了幾天,有些粗淺的心得和疑問,先從看起來最簡單的 syntax highlighting 來談起。

查了像 TextMate 以及 Espresso 這種可以自定義語法的 editor,他們的作法基本上都是用 regex 為基礎的 match rule 替各字串加上 tag (TextMate 中稱為 scope, sugar 中稱為 zone)。這些 rule 可以互相或自我參照,做出成對括號批配之類、原本用 regex 做不到的事情。雖然這只能處理某 CFG 的子集,某些極端狀況無法處理,但就實用上來說這方法表現得還不錯。

如果要真正得到完美的 syntax highlighting,就得去 parse 整份文件。

然而現在面臨的問題並非只是靜態的 parsing,而是要面對隨時更改的 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,” 利用 parser combinator 實作易懂的 parser。效率號稱不太糟。

然後有人寫了篇 yacc is not dead 反駁說這效率是 exponential。

作者又反駁雖然這 exponential,但一般情況下還挺快的:

其實現在的 scala standard library 就有 parser combinator,雖然好像速度不快,但是易讀性上真的好很多。不過對 right-recursive 的狀況也要想辦法用 list 等改寫語法克服。

我還滿好奇的,現在號稱 compiler 界最先進的 open source project LLVM,其 subproject — clang 的部分好像也是自己手打 parser 的。為什麼不用 lex/yacc or flex/bison 呢?

話說回來,llvm 似乎很值得學一學。不知道有沒有好的 compiler 課本是拿 llvm 當範例的?市面上連 llvm 的書都很難找到。

 
 

Write Concisely