在撰写了《构造可配置词法分析器》之后，我陆续收到了不少读者的来信，不过大多数都是要求源代码的。这篇文章原先是发布在自己的百度空间的，不过现在那个地方已经不打算写技术相关的东西了。而且由于cppblog的一些用户也转载了那篇文章，因此不打算再在这里重复贴了。

    由于大多数读者都向我发邮件要求源代码，因此我想到，上一篇文章虽然把所有的原理都说明白了，不过关于实现相关的数据结构的那些细节却都没说出来。对与那些真的想实现自己的正则表达式引擎的人来说，可能还不能从文章中得到所有问题的解决方法。不过鉴于本人一贯来不想把所有的细节问题都说得太过于繁琐（留点问题给读者想也是好的，不然文章就没起到带动学习的作用了），因此作出决定：接下来的几天如果有空的话还要撰写一篇新的文章。

    新的文章将着眼于【如何实现正则表达式引擎】这个话题，续《构造可配置词法分析器》的内容继续讨论。在这篇文章之中，我打算把使用DFA构造的正则表达式引擎的实现方法稍微描述一下（因为实际上难度不大），然后再花比较大的篇幅来讲述实现正向预查、反向预查、匿名获取、命名获取和子表达式引用的方法。文章中还会描述这篇文章中所提及的优化正则表达式的方法（招太多口水了，看来不写也会有很多人不高兴的，这是文化问题）。

    敬请等待。

    因为最近观察到一些很奇怪的现象，因此在此提出调查。不知道是我不会用cppblog还是cppblog没这个功能，总之我没找到【投票】的工具，因此只好手写。

    1：大家在学习数据结构的时候，实践的方法通过（多选）
        A：做习题
        B：学习STL和Boost等
        C：尝试自己开发一套模板库

    2：大家在学习编译原理的时候，实践的方法通过（多选）
        A：做习题
        B：学习flex、yacc/bison和ANTLR等
        C：尝试自己开发过编译器（特别指字符串处理部分，指令部分不在本题目考虑范围内）
        D：尝试自己开发与flex、yacc/bison或ANTLR等价的工具（不拘泥于形式）

    3：如果上面的题目选择了C或者D，那么（单选，自己独立开发程序而不是在团队中开发时）
        A：自己需要的时候使用自己的库
        B：自己需要的时候使用别人的库

    4：如果第一题选择了B，那么（单选，自己独立开发程序而不是在团队中开发时）
        A：选择编译器或IDE推荐的库（MFC或其他，跟STL或Boost有交集的库）
        B：选择STL、Boost等

    注意：
        本人不倾向于向别人建议上面的任何观点，仅作调查。
        勿人身攻击，欢迎评论。 
        写出自己的答案的同时请写出自己开发的时候经常使用的操作系统和编译器等工具。

    今天经营着世界最大的搜索业务的某公司在位于广州市海珠区珠江河畔的某著名大学开了一次招聘会，申请实习软件工程师的都要笔试。于是我也去写了，虽然我不是位于广州市海珠区珠江河畔的某著名大学的学生，反正人人都能去。

    第一道题，把字符串中相连的重复字符处理成一个。例如aaabbcddcc处理成abcdc。因为寒假的时候才往Vczh Free Script 2.0中添加了一个Mark-Compact Collector，因此算法也就模仿了一下Mark-Compact Collector，也就是把所有该删掉的字符换成'\0'，依次读取并跟右边最近的非'\0'字符置换一直到完。

    第二道题，已知数列中有1、2、3三种数字，并且可以两两置换。求最小置换次数的方法让数列递增。

    我用了这样的方法：
    ·找到并保存每一个位置中应该存放的数字，也就是一1、2、3的数目都跟数列相同的递增数列bi。
    ·遍历ai，找到ai≠bi的i并做如下处理：
        ·寻找aj使得j>i且bi＝aj且bi≠bj
        ·在这些j中寻找k使得bk＝ai
        ·如果k非空则让m∈k，否则让m∈j并让下一步的k的势最大
        ·置换ai和am

    一个好像很和谐但是事实上不知道和谐不和谐的证明：
        j>i且bi＝aj且bi≠bj这个条件是必定满足的。如果不满足，则很容易证明ai和bi中1、2、3的数目不完全相同。
        k非空使得一次置换产生了两个正确的结果。
        对于每一次置换，如果让m1∈j且{m1}∩k为空，m2∈k，则有
            选择m1而不是m2有可能减少、保持或增大下一次置换中k的势；
            选择m2则下一次置换中k的势不变。
        这样的话，选择m1最好的结果就是让这次置换不影响全部的置换，最坏的结果是增加了置换的次数；
        选择m2则不会影响全部的置换。
        因此只需每一次都尽量选择m2中的值，对于k∩j为空的情况，则计算所有j得到的下一步的k的势dj，选择最大的j即可。

    第三道题，华容道解谜器。只好弄了个宽度优先搜索。

    以上纯属YY。

    P.S.
    ·选择题里面有一道问ABCDEFGHIJ的全排列中满足A在B前面的数量有多少？答案：因为A和B是对称的，因此对于任意一个确定的A和B的位置的集合，A在B前的概率是0.5，因此答案为10!/2。

    ·同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司的招聘活动我也参加了一次，结果发现经营着世界最大的搜索业务的某公司和同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司【好像】有一个特点。经营着世界最大的搜索业务的某公司喜欢出最优解题目，同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司喜欢出最高速题目。而且经营着世界最大的搜索业务的某公司很喜欢去在位于广州市海珠区珠江河畔的某著名大学，而同时拥有操作系统、开发工具、数据库引擎、办公软件、游戏平台等多项业务的某著名软件公司则很喜欢去位于广州市五山的某著名理工大学。

     摘要: 今天上完课回来继续把昨天晚上剩下的using字句完成。使用Syngram写编译器真是舒服啊，直接在代码里面加两条推导式就完成了。昨天发现了InsertEnv指令的bug以后，改过来了。不过InsertEnv不能用在using身上，只好另外写了一个UsingEnv指令，把环境以及上游的链表而不是多个环境插进当前的环境中。这里展示了class和namespace是如何通过闭包（函数）来实现的，以及他们的构造过程。

class以及namespace都是通过在return的跳转目标后添加指令而保证return结束但是不修改class和namespace表达式的返回值。

class函数的参数是父类的构造子，class函数在所有代码之前首先构造好一个父类的链表，然后通过InsertEnv将这个表引用到自己身上，从而实现了正确的scope。然后让constructor为空函数。ClassName.new()的时候首先运行class函数（使用callctor而不是invoke来自动找到父类并添加到参数中），然后复制堆栈，获取construct  阅读全文      摘要: 今天抓到了一个隐藏了3个月的bug。这个bug以前一直没有被找到，因为以前写的用于测试脚本的代码都没有出现类成员函数使用非全局的外部对象的情况。Vampire.Kiss用我的Vczh Free Script代替PHP开发了一个网站，过程中也向我提了不少要求。其中有一套就是想在脚本中加入namespace。其实这是相当合理的，只是我没想到脚本第一次应用就会被用来开发库。因此今晚就加上了namespace。

实际上在目前的结构中添加namespace并不复杂，因为namespace也可以用闭包来模拟。其实闭包不仅仅是函数，而是一段带了上下文的指令表。因为namespace本身也是用于控制符号在上下文中解释方法工具，因此使用闭包来做也就是十分合适的了。想到以前是用闭包模拟class的时候，曾经实现了一个把一堆环境链接到上下文中的指令。类的继承实际上也是控制符号在类成员函数的符号在上下文解释方法的工具，因此我使用了如下方法来让闭包可以顺利地模拟class的继承：  阅读全文

     摘要: 有个同学近来一直在做一个魔兽世界战况分析（名字好像叫DeusCraft），说是很火。只是用C#觉得不是很爽，想移植到C++上面来。但是那个东西在分析的时候用了好多正则表达式，于是只好找了些正则表达式引擎来测。

测试的文件一共有27万多行，首先通过一个检查时间的正则表达式。如果成功，则在接下来的20几条正则表达式中验证字符串命中哪一条，然后开始做剩余的工作。原先在C#上花了12秒分析，后来换了boost的正则表达式花费40秒，然后从MSR上找了一个号称比boost快4倍的正则表达式引擎，结果还是40秒（都是微软的，咋差距这么大……）。于是同学用他自己做的正则表达式引擎花了23秒（此数据不太记得），我用我以前那个东西花费108秒（-_-|||）。

于是我们这几天就在优化正则表达式引擎，到了今天同学那个花费13秒，我那个12秒。Visual Studio 2008 Team System上有一个Performance Wizard，用于在程序执行的过程中统计各个函数所占用的时间，可以方便定位，看出效率瓶颈，非常好用。
阅读全文

posted @ 2008-05-07 21:21 陈梓瀚(vczh) 阅读(1241) | 评论 (12) | 编辑 收藏

     摘要: 华南理工大学软件学院本科05级3班，陈梓瀚（vczh）

游戏规则：
1：地图上可以建立三种炮塔塔，游戏有上、左两个敌人的起始点，两个起始点的敌人分别到下、右两个终止点。
2：每一盘有1000个等级分别从1-200的敌人从起始点出发自动寻路前往终止点。如果有10个敌人到达了终止点的话则游戏结束，玩家输。如果所有的敌人都被消灭或到达终止点之后，到达终止点的敌人没有10个的话则游戏结束，玩家赢。
3：建立炮塔的方格敌人不能通过。在建立一个炮塔的时候，如果程序发现这个炮塔的建立会导致敌人找不到任何路径前往各自的终止点的话，则建立被禁止。
4：炮塔可以是用金钱建立或升级，可以卖出货的金钱。消灭敌人能够获得金钱。
5：三种炮塔分别是
·升级后数量变多，射程变长，攻击力变强
·升级后速度变快，射程变长，攻击力变强
·升级后一次爆炸伤害的范围变大，射程变长，攻击力变强
·升级一次后减速范围变大，减速因子变大
6：炮弹在  阅读全文

     摘要: 第一次用C#写游戏。在C#上写算法果然是一个挑战，时间复杂度太大的话造成的后果比C++明显好多，于是总是尽量把东西做成O(n)或者O(nlogn)。这次就在上面实现了一个寻路算法。

这个寻路算法是这样的：在16×16的方格上有一些终点，东西在格子上只能上下左右行动。每一个格子需要记录到其中一个终点的最近的路的第一个方向（就像三层循环的寻路算法一样，最后给出矩阵的那个）。  阅读全文

     摘要: Lazy Compile使用Syngram动态创建语法分析器的代码实在是太慢了，debug竟然需要8秒钟来处理91条比较长的文法。于是我打开了Visual Studio 2008的Performance Wizard查看运行时消耗的资源，结果发现竟然都消耗在自己那个array类的operator[]里面了。那一段代码是用来检查文法的左递归引用关系是否出现环的。结果就把用到的四个array全部换成bool*了，当时只是为了创建二维数组方便使用了array类。

过后，debug的时间立刻降为2秒钟不到，于是我又打开Performance Wizard看了一次，这次消耗的瓶颈终于转移到一个合理的地方了。

结果：array竟然比指针慢了无穷多倍，得找个时候重新写一次。不过这段代码好象是去年写的，也没经过什么性能测试，也难怪发现不了问题。在此帖上代码，等Lazy Script写完了重新审查一下自己的那套模板库（NTL，Non-standard Template Library，娃哈哈）。   阅读全文      摘要: 这几天一直在忙学校的比赛，到了今天终于有空了。

Lazy Script的语法实在是很复杂，因此不得不在进行第一步的名字检查之后把原本的语言转换为内部使用的一种元语言。这种元语言设计的原则是尽量简单。譬如列表构造和do-end语句就需要被转换掉。进行了转换以后，就需要对元语言进行一个类型方程组的建立。这一步暂时还没有建模好，而且实际工作需不需要真的构造出一组方程组还不知道。目前还比较没有头绪的就是如何对模板函数的类型方程建模。

举个例子，譬如我们对上一篇文章中提到的代码进行类型方程组的构造：  阅读全文