最近想要自己写个简单的 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