sin(x)

Page 5 of 10

正则表达式匹配:运行

测试

为了测试引擎的正确性以及评估效率,测试程序(TestRunner)是必须的。

手工创建一个测试数据集是不现实的,项目的测试程序需要一个正则表达式的集合,对于每一个正则表达式,程序使用Generex根据正则表达式生成指定数量的随机字符串,同时,程序对得到的字符串进行随机替换字符、增加字符、删除字符来获得“错误字符串”的测试数据。程序使用String类的match方法来验证匹配结果的正确性,使用System的nanoTime方法来计时。

运行

NFA

编译得到了NFA,那么可以直接运行NFA(Pattern)。

Continue reading

正则表达式实现:编译

Thompson在他1968年的论文当中介绍了多重状态的模拟。在他的设想当中,NFA由短小精悍的机器码表示,状态的变化只是指令的调用。实际上,Thompson把正则表达式编译成了机器码。四十年之后,计算机速度变快了,机器码运行不再必要。原文使用C语言实现,并且只能编译显式连接的后缀正则表达式,而本文实现了标准的简单正则表达式的编译。

表示

本项目(SimpleRegex)采用Java语言编写,Java的两个重要特性大大方便了正则表达式引擎的实现:

  • Unicode:原生支持Unicode支持,不必额外考虑Unicode字符匹配

  • 垃圾回收:可以免去复杂的NFA链接结构的内存管理

首先需要使用特定的数据结构来表示NFA,我们把NFA表示为关于状态的链接集合。

状态

NFA由状态(AbstractState)链接而成,其中可以分为三类状态:

Continue reading

30天自制操作系统:时钟和标准I/O

《30天自制操作系统》到30天结束了,但是操作系统还有很多地方可以完善。本文将给“纸娃娃操作系统”增加获取时钟的API以及标准I/O接口

获取时钟

时钟无论是对于人来说还是计算机来说都非常重要,但是“纸娃娃操作系统”还不能获取当前的计算机时钟,所以需要增加获取时钟这个API。

实现原理

在之前实现操作系统计时器的时候,已经接触过了PIT,PIT会在一定时间内产生信号,操作系统通过PIT的信号来进行计时,从而实现任务调度等依赖于计时的功能。除了PIT之外,计算机中还存在着一个RTC,用来维持计算机的时钟,具体的时钟信息被保存在了一个CMOS RAM中,寄存器地址选择端口号为0x70,寄存器数据读取端口号为0x71,而RAM中具体时钟信息对应的寄存器如下。

Continue reading

算法导论:计算几何

对于几何相关的计算,中学的数学已经涉及了一部分。对于两个有向线段a和b,如何判断线段a在线段b的顺时针方向还是逆时针方向,两个线段是否相交。我们可以通过计算两个线段的斜率来判断它们之间的相对方向,使用方程组来求解两个线段是否有交点。这些方法计算机也可以使用,但是计算机计算很大的特点就是精度有限,计算斜率和解方程组都会有除法运算,这样的方法是不够好的。

除了中学接触的几何问题,还有线段集合的相交判断,以及寻找凸包等问题。完整代码以及测试代码位于Gist

Continue reading

算法导论:van Emde Boas树

对于一组取值范围已知的关键字,如何进行快速插入、删除、获取最值、获取前驱和后继、判断是否存在等操作?红黑树是一个选择,这些操作都要花费O(lgn)的时间复杂度。红黑树没有使用取值范围已知这个性质,直接寻址表倒是使用了取值范围已知这个性质。直接寻址表的插入、删除、判断是否存在的操作只需要常数时间,但是获取前驱和后继需要O(n)的时间。一种解决方案就是将直接寻址和二叉树结合,对于每一个节点,如果子树中存在一个以上的元素,那么置为1,否则置为0:

Continue reading

« Older posts Newer posts »

Copyright © 2019 sin(x)

Theme by Anders Noren, host by Coding PagesUp ↑