syntax highlight/parser/compiler 的难度

楼主: yllan (蓝永伦)   2010-12-30 01:42:33
最近想要自己写个简单的 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
作者: tinlans ( )   2009-01-05 16:58:00
这么容易给你学起来我要吃啥饭 XD说笑的,不过 parser 只是 compiler 的 10% 而已。其实这内文主轴跟 compiler 还扯不太上边。这年头做这行的,普遍比较重视编译出来的程式执行效率,对 parsing 速度这东西反应相当冷淡,讨论也颇有限。这其实比较偏 editor 跟 UI 设计的那一块。
楼主: yllan (蓝永伦)   2009-01-06 21:03:00
是的,可能是我标题有写 compiler 不太恰当本文只是想问问看有没有这方面的资料可以参考
作者: airzone   2009-01-11 08:19:00
作者: PCIT (冈山的火车￾  N￾ I
可以考虑一下,实做在cloud9ide :)

Links booklink

Contact Us: admin [ a t ] ucptt.com