10 2009 档案
Vczh Library++3.0之正则表达式引擎（Epsilon-NFA到NFA）
摘要: 这篇文章的代码所描述的算法在这里有详细的说明。
Epsilon-NFA到NFA的目标主要是产生一个没有Epsilon边的，跟原状态图等价的新状态图。过程不复杂，首先从起始状态开始，寻找所有Epsilons边到达的对象的集合，然后复制这个集合的所有状态包含的非Epsilon状态。其实状态做完之后，寻找所有能够产生非Epsilon边的状态然后重复这个过程，最后NFA就出来了。代码如下：
阅读全文
posted @
2009-10-28 04:34 陈梓瀚(vczh) 阅读(2444) |
评论 (7) 编辑
Vczh Library++3.0之正则表达式引擎（生成epsilon-NFA）
摘要: 不知道什么是epsilon-NFA的话先看这里。
从正则表达式生成epsilon-NFA其实跟将一棵树变换成另一棵树是类似的。epsilon转换提供了一种工具让我们可以把一个图表达成漂亮的形式，看起来就有典型的递归结构。因此这个工作依然可以用RegexExpressionAlgorithm这个visitor模式的产物来解决：
阅读全文
posted @
2009-10-24 00:23 陈梓瀚(vczh) 阅读(2341) |
评论 (5) 编辑
Vczh Library++3.0之正则表达式引擎（解引用）
摘要: 解引用指的是对命名表达式的处理。这跟C++的宏差不多，留个名字在那里，然后就扩展它。举个例子，我们写一个正则表达式判断一个字符串是否ip地址。判断一个字符串是否小于256的数字还是很麻烦的：\d|[1-9]\d|1\d{2}|2[0-4]\d|25[0-5]。但是如果要判断是否X.X.X.X就要将这个表达式复制四次（至少两次），这会导致正则表达式很长。如何解决呢？
阅读全文
posted @
2009-10-20 06:36 陈梓瀚(vczh) 阅读(2082) |
评论 (2) 编辑
Vczh Library++3.0之正则表达式引擎（字符集正规化）
摘要: 字符集的正规化指的是让正则表达式的表达式树的所有节点中记录的字符集合的最小单元都是互不交叉的。举个例子，[a-g][h-n]没有交叉，但是[a-g][g-n]就交叉了。所以对[a-g][g-n]做字符集正规化的结果就是将表达式修改为([a-f]|g)(g|[h-n])。这样表达式里面出现的字符集合的最小单元[a-f]、g和[h-n]就没有交叉了。下面是正规化的代码：
阅读全文
posted @
2009-10-17 20:43 陈梓瀚(vczh) 阅读(1927) |
评论 (1) 编辑
Vczh Library++3.0之正则表达式引擎（使用Visitor模式访问语法树）
摘要: 虽然说分析语法树依赖于递归，但是你真的去写递归那是一件很烦的事情，个人觉得烦事烦在你每次都要去RegexExpression.h里面声明所有的虚函数之后复制过来一一运行。有没有办法仅编辑.cpp文件就能做到呢？也就是说，在如何不修改Expression一系列类的接口的情况下给Expression添加算法？一般来说对付树形结构都是使用Visitor模式的。
（内附代码）
阅读全文
posted @
2009-10-17 17:34 陈梓瀚(vczh) 阅读(2042) |
评论 (0) 编辑
Vczh Library++3.0之正则表达式引擎（语法分析）
摘要: 这几天正在着手开发一个基于Vczh Library++ 3.0基础之上的新的正则表达式引擎。这个东西跟以前的功能没什么大变化，只是最基础的那一层被全部改了，而且还不兼容，所以要重写。不过都是自己的东西，无所谓了，不兼容也没什么问题。
下面介绍正则表达式引擎的语法分析过程。
阅读全文
posted @
2009-10-15 05:53 陈梓瀚(vczh) 阅读(3186) |
评论 (4) 编辑
回来了（VL++3.0计划）
摘要: 之前因为非常忙，加上无聊开发什么类似WCF和WPF的东西，最近终于找到了新的目标了，于是之前那些就不做了。隔了这么久没法文章主要是因为最近没写出什么完整的东西。国庆玩了9天，之前在计划VL++3.0。
VL++3.0被定位为一个为了数据处理而开发的C++库。这个库不的特点在于“其他语言的味道很浓”。C++的库用起来不爽主要是因为老是要我按下划线，而且大量应用非OOP特性导致IDE的自动补全无法发挥作用。所以为了弥补这个缺陷我做了一个很不一样的东西，也就是VL++了。经过了三年多的开发，1.0和2.0已经相继出炉，每一次打翻新都解决了一些前一个版本解决不了的问题。
阅读全文
posted @
2009-10-09 07:17 陈梓瀚(vczh) 阅读(3553) |
评论 (11) 编辑