简单的基于DFA的正则表达式引擎

最近做了一个很简单的正则表达式引擎,能支持*,|和字符连接,目的是动手写点东西熟悉一下编译里面的一些原理.

龙书中将解析正则表达式库分为两种办法:
1)将正则转换为NFA,然后NFA再转换成对应的DFA
2)将正则转换为抽象语法树,再将抽象语法书转换成DFA.

我这里用的第2种方式,第1种等我有空了再补上吧.

大体说一下流程,分为以下几步:
1)自下而上的构建抽象语法树

Lua的一个问题

最近对qnode进行压力测试,结果很不理想.前期只顾着赶功能,没有进行单元测试,只是简单的进行一些测试,所以现在打算回过头来对一些基础模块写测试用例.

这是本篇的题外话了,在压力测试qnode的时候,由于qnode是使用的actor模型,每个actor会有一个lua协程,但是在做压测的时候,会创建出很多actor这样就出了问题,来看看lua_newthread这个用来创建协程的函数:

LUA_API lua_State *lua_newthread (lua_State *L)

Lua5.1.4代码分析(二十四)-Lua GC原理

到了Lua GC部分,先简单介绍Lua GC的原理,后面再针对一些细节展开讨论。

Lua的GC算法使用的所谓“Mark And Sweep”算法。简单的理解,这个算法将GC分为两个阶段,一个是标记(mark)阶段,这一阶段将所有系统中引用的对象都逐一标记;而在清理(sweep)阶段,将把在mark阶段中没有被标记的数据删除。

在Lua中,使用几种颜色来区分不同的结点:
1)

自己动手实现Lua调试器

这段时间在qnode项目中新增了一个叫ldb的子项目,它的作用是使用C语言实现了一个lua调试器,后面将会在qnode中嵌入对调试lua脚本的支持。

先来简单提一下ldb的用法,在ldb目录的子目录test中,有一个main.c文件,其中使用ldb库提供的API实现对lua脚本的调试演示:

#include 
#include "ldb.h"

ldb_t *ldb;

static int
c_break(lua_State *state) {
 

关于调试的一些想法

这几天一直忙于跟同事联调测试,其中有一些关于这些的思考,整理一下记录在这里吧。

先从最简单的说起,如何调试和分析问题?这里不涉及具体的应用场景,也不讲工具比如gdb,printf打日志的使用,仅谈方法。我想最能描述如何分析查找问题的思路应该是二分法:遇到了问题A,那么首先将这个问题依次分解为几个小问题a,b,c等,然后再把这些问题再次的分解,直到不能再分解为止。然后开始针对最小的问题开始逐步定位。逐步定位时又有技巧,如果问题A由几个可能会变化的环境影响,那么要想办法在某次查找时只留下一个变量,这样可以确保被影响的因素少,否则出问题的时候你不能确定到底是哪里出了问题。就按照这样的思路,一层一层将问题的封装层剥离开,直到还原到问题的本质。

这个方法的思路,其实反过来可以算是写代码的思路。你写一个功能,首先也要将它分解成几个小功能,每个小功能写完了,也要有针对性的测试用例保证它们根据某些输入可以有相应的输出。

OK,前面提到了分析和查找问题的思路。看上去是很简单的,但是很多时候仅知道方法还是不够的。

我这两天遇到的一个在联调时出现的问题就是,出现问题的时候,对方同学总是认为自己是没有错误的,而他给我提供的他认为正确的证据在我看来又是不那么站得住脚的,于是最后发现确实是他的问题。

比如某个检验值,需要的是使用两个数据根据一个算法产生,然后C端生成之后发给S端,由S端再根据这个校验值将数据还原回来。我做为S端的,拿到这个数据之后发现不能还原,于是大家对了一个生成这个值的时候调用函数时的一些flag是不是一样的,发现都是一样的之后还是没发现问题。于是C端这位同学就认为是这个算法库出了问题。

到这一步,我也不能确定是哪里的问题。但是根据上面的讲过的思路,我希望做的是,将这个问题还原到最简单情况,于是我写了一个单独的,除了这个库之外不依赖其他库的简单程序,它做的事情很简单:从文件读入数据,然后再使用那个算法生成校验值。发现我自己生成的数据,是可以正常还原回来的。于是我要求C端的同学也要这样将这个问题最简化,在C端也仅使用最简单的读文件,然后还原看看行不行。

这个时候问题就来了,C端的同学很不情愿–他的理由仍然是:我的代码是没有问题的,这么做是没有意义的。于是软磨硬泡,将我的理由说给他,告诉他我希望能有这样一个最简化的环境来测试这个算法库是不是对的。甚至为了节省他的时间,我把我的测试代码给他,因为这本身就是很简单的代码嘛,只是看你想不想写罢了,与其讨论有没有意义这些扯皮的问题,不如老老实实的查证问题。最后他终于发现是自己使用的字符串类,在读取数据的时候出了问题,导致了生成的校验值失败。

这个过程,我体会到的是几点:

Lua5.1.4代码分析(二十三)-如何实现Lua代码的热更新

能很好的支持代码热更新机制,是大部分选择要嵌入脚本语言的原因之一。好处很简单,脚本代码可以热更新的话,调试和线上解决问题都可以不用重启程序了,对开发效率有很大的帮助。

今天就来谈谈Lua代码如何实现热更新。

先简单回顾之前提过的模块和require机制。Lua内部提供了一个require函数,来实现模块的加载,它做的事情主要是以下几个:
1)

qnode 0.1发布

大概半年前提到的qnode项目,实际上我在这半年里一直不停的ci代码。不过最近改变思路,决定时不时发布一个小版本,包含几个新的特性,有点类似互联网产品中的快速发布敏捷迭代。这样的好处是,其他人能看到这个项目的进度,我也有一个比较明确的短期目标去开发。

0.1版本主要做的是这几件事情:

shared_ptr和对象管理

异步的分布式编程常遇到一个问题。比如某个客户端连接上来之后,发送的请求业务逻辑处理是需要服务器再连接到另外一个服务器做查询的,那么有可能出现的情况是,这个回复的时间太长或者各种其他原因,客户端在处理完毕之前主动关闭连接了,导致从另一台服务器处理完毕的时候,该连接指针已经失效。

这个问题很常见,尤其在业务复杂,异步的环境下更容易出现了。

简单的来理解,需要一个机制,在处理完毕的时候查询到该连接指针是不是有效的。

我想的第一个策略是使用shared_ptr管理这个连接,然后用一个该shared_ptr的weak_ptr来观察该指针是否还有效。然而shared_ptr是一种具备传染性的策略:某个指针一旦某处使用shared_ptr管理,那么所有该指针出现的地方也需要使用shared_ptr了。我不认为这是一个好办法。

咨询了另一个我比较信服的朋友,给的方法是不再传递指针,而是使用ID。换言之,ID和这个指针是一一对应的关系,处理完毕之后要向该连接回复的时候,首先根据ID来查询该连接是不是还有效,然后再做后面的事情。

这个思路我认同。不过细化起来还有几点需要考虑的。ID如何分配,是使用连接的FD么?这样带来的问题是,操作系统实际上会很快复用刚才关闭的FD,会有一定的风险。我最后使用的策略是分配ID的地方保存一个计数,每次加一,使用STL的map来管理ID和指针的对应关系,在新分配一个ID之前,虽然将原来的计数器加一了,但是也要判断是不是原来这个ID已经有对应的指针与之绑定了。

第二个问题是,管理ID对应关系的管理器是全局只有一个吗?如果只有一个,那么在多线程环境下势必需要加锁操作。由于我现在做的这个服务器是多线程,每个线程绑定了一个epoll,所以策略变为每个线程一个ID管理器,同时ID中带上线程的信息,比如使用低两位保存线程的ID,这样就可以根据ID识别出来这个ID属于哪个线程管理的。于是由于给线程发消息的消息队列有先后顺序,比如前一个消息说删除这个ID,后一个消息给这个ID发送消息,那么后一个消息就不会被处理,因为ID已经被删除了。

我个人觉得这种方案,比直接在各种线程里使用指针,同时使用shared_ptr来管理的方案,要好的多。

Lua5.1.4代码分析(二十二)-表的赋值和查询

这里涉及到的两个OPCODE,SETTABLE和GETTABLE,由名字可以知道,分别用于表的赋值和查询。
两个OPCODE指令格式如下:

OP_SETTABLE,/*  A B C R(A)[RK(B)] := RK(C)        */
OP_GETTABLE,/*  A B C R(A) := R(B)[RK(C)]      

Lua5.1.4代码分析(二十一)-表的创建和初始化

在讲解之前,先来简单回顾一下Lua表的初始化语法。

在Lua中,表是唯一的数据结构,可以使用它,模拟hash表,数组,链表,树等一切常用的数据结构。Lua表分为数组部分和hash部分。比如:

local t = {1,2,3,4,5}

以上分配一个Lua数组,依次为1到5.

而如果要初始化hash部分,则需要指定key,有两种方式:

local t = {a="test"}
local t =

Pages: Prev 1 2 3 4 5 6 7 8 9 Next