刚才遇见了LV

好久没见到LV同学了，倒是每个周末都见到室友跟LV连魔兽。他这个星期也是回来参加期末考试，正好昨天我和他都考完了最后一门，今天一早出门进城就碰上了。他可快活，出来陪女朋友逛街，而我则是到师兄住处待几天准备星期天的考试。

这么一段时间没见，牛人就更牛了。不愧是在大公司里工作，感觉又不同了呢。之前跟去了阿里巴巴的HC同学聊天也有这样的感觉，像Oracle的数据库和IBM的应用服务器那些，我们平时在学院又怎么玩得出规模呢。

然后我坏习惯又来了，一遇着牛人就要抓着讨论技术话题。这回还真碰对了，LV同学正在负责的工作居然是一个编译器 \o/
一听说是在做编译器我就两眼放光啊…… =_=||
那是一个用于解析XML文件的编译器。说真的我从来没关心过XML文件在底层是如何处理的，因为遇到要处理XML文件的时候，我用的语言总是提供了标准的解决方案去应对XML的解析。但这个公司就有这样的产品，将XML编译为内部数据结构（没听清楚，不过貌似是AST？），可以方便的在路由器上使用XML形式来传输数据。这个XML编译器项目包括XML的编译，Schema验证，XPath编译和XSLT编译等几部分。

如果没听错，是把XML文件编译为AST，然这个AST指的是abstract syntax tree的话……那这个AST应该有什么特别之处能使它与DOM有所不同吧。嘛，详细的技术资料LV显然是不能告诉我的，这就只能猜猜了。

然后，这个编译器项目的前端果然还是用工具来生成的——改进的Flex和Bison。貌似是说因为原本的Flex支持的token数不够多，而UTF-8的一些转换需要特别的操作？我以前甚至不知道Flex的token数有限制……刚才查了下也没查到什么有用的资料，GNU的Flex官网说明也没提到，而Google搜索到一堆都是Adobe Flex的结果 T T

也聊到了些别的，例如聊起了正则表达式的一些实现。我问LV所谓“编译一个正则表达式”到底编译成了什么。答曰：DFA。我一想：“对诶！完了，刚问了个超级愚蠢的问题。不是DFA或者NFA还能是什么”。
于是查阅了一下Java中java.util.regex.Pattern的实现，内部的所谓“编译”是将正则表达式转换成了一个NFA，以内部的Node类来表示。Node本身只能形成一个单链（其中的成员变量只有Node next），但它的一些派生类有附加的Node成员，所以Pattern里的私有成员变量Node root和Node matchRoot上的注释说它们指向的是object tree。
虽然问了个愚蠢的问题，却带来了意外的收获：LV提到了一个用于DFA的优化算法。DFA的转换可以用一张表来表示，但对于一个比较大的DFA，那张状态转换表也可能比较大，从而增加了高速缓存不命中的可能。因此可以在运行中将经常发生跳转的项之间在表里的距离缩短，以提高高速缓存的命中率；也就是不断交换表中各项的位置吧。这真是有趣的做法，虽然可能是业内的常规做法了，但我毕竟还是第一次听说，忍不住要赞叹一番……XD
LV是提到他参与的XPath部分就是这样，把XPath编译成DFA来实现高速查询/访问。强悍啊……

==================================================

突然想起，他还提到了他们内部用的一个虚拟机，也是用基于栈的指令集。貌似是有98条指令，正好也是bytecode...

评论

3 楼 lwwin 2007-11-30  

先不要完美嘛。。。
不知道关注IMPL的人多不多，
偶只是希望有技术支持，以前找了几个C的脚本语言，不是用起来麻烦就怎么怎么……

主要偶不会用GCC系列，通常希望是纯C的代码，自己慢慢配的

MAKEFILE大部分也不是适合NMAKE的，比较郁闷……

预祝能够看到有趣的东西XD，偶要求不是很高，只是每次写的时候总不知道从哪里开始，于是就不肯干了XD

2 楼 RednaxelaFX 2007-11-29  

如果你说的是类似C-Minus那样功能的语言，外加并不“复杂”“前沿”的实现的话……下个月说不定还真会做一个。下个月一整个月都是实训，白天写的代码肯定有聊不到哪里去 =_=|| 晚上还有没有心情写代码真难说。
从简单的开始写点笔记吧。
本来就想在这weblog上写些编译/脚本相关的主题，现在其实还没怎么切入主题呢。看书的时候做的笔记都在纸上，一想到要敲到电脑上就总想写完整点，但那样就弄不完了。说到底还是水平太差，根本还不行啊……

1 楼 lwwin 2007-11-29  

怎么说，如果FX大弄一个可以模拟C语言的脚本，偶会很乐意用，当然主要是有技术支持XDD