随笔-76  评论-412  文章-0  trackbacks-0
    各位读者们,《构造正则表达式引擎》新鲜出炉啦!

    《构造正则表达式引擎》
    这篇文章描述了纯匹配正则表达式和具有高级功能(正向预查,反向预查,匿名捕获,命名捕获,命名检查和贪婪循环等)的正则表达式各自用来匹配正则表达式的算法。如果大家在书写好的正则表达式的时候出现了麻烦,或者在开发自己的正则表达式的时候遇到障碍,那不妨读一读这篇文章。不过对于没读过下面这篇文章的朋友,如果不是很熟悉编译原理关于DFA和NFA的知识,那么建议首先阅读下面这篇文章。

    《构造可配置词法分析器》
    这篇文章描述了如何从简单的正则表达式构造ε-NFA,并且一步一步转换到DFA的算法,而且还提出了一种可配置词法分析器的可能的实现方法。学习《编译原理》的朋友们,如果在状态机那里遇到什么问题的话,那么不妨读一读这篇文章。

    上面这两篇文章是我在学习《编译原理》之后开发正则表达式引擎的心得体会,在这里与大家分享,共同进步。
posted on 2008-05-22 15:06 陈梓瀚(vczh) 阅读(2151) 评论(7)  编辑 收藏 引用 所属分类: 作品

评论:
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-05-22 15:30 | 空明流转
很好很强大的矬人,哇咔咔  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-05-22 16:15 | foxtail
果然经典哈 最后对学习方法的见解对我很有帮助  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-05-22 21:16 | Gohan
向您学习喽  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-07-01 16:35 | 白开水
词法分析部分写好了,不过扩展正则表达式部分懒的写,想先写语法分析器了。
用正则表达式的引擎提供了一套接口给词法分析器。测试了下
测试的内容如下,然后自己把一份代码粘帖了10几次,扩充到3MB,然后分析了下。大约44W标记每秒

AddMoreType( scanner, L"ID", L"[_a-zA-Z][a-zA-Z0-9_]*" );
AddMoreType( scanner, L"ID.IF", L"if" );
AddMoreType( scanner, L"ID.BOOL", L"true|false" );
AddMoreType( scanner, L"ID.ELSE", L"else" );
AddMoreType( scanner, L"ID.WHILE", L"while" );
AddMoreType( scanner, L"ID.DO", L"do" );
AddMoreType( scanner, L"ID.BREAK", L"break" );
AddMoreType( scanner, L"ID.CONTINUE", L"continue" );
AddMoreType( scanner, L"ID.FOR", L"for" );
AddMoreType( scanner, L"OPERATOR", L"\\+|\\-|\\*|/|%|<|>|=|<=|>=|==|!=|!|&&|\\|\\||\\^|;|\\(|\\)|\\{|\\}|,|\\[|\\]" );
AddMoreType( scanner, L"OPERATOR.NOT", L"!" );
AddMoreType( scanner, L"OPERATOR.ADDMINUS", L"\\+|\\-" );
AddMoreType( scanner, L"OPERATOR.MULDIVMOD", L"\\*|/|%" );
AddMoreType( scanner, L"OPERATOR.COMPARE", L"<|>|<=|>=|==|!=" );
AddMoreType( scanner, L"OPERATOR.ASSIGN", L"=" );
AddMoreType( scanner, L"OPERATOR.AND", L"&&" );
AddMoreType( scanner, L"OPERATOR.OR", L"\\|\\|" );
AddMoreType( scanner, L"OPERATOR.XOR", L"\\^" );
AddMoreType( scanner, L"OPERATOR.LEFT", L"\\(" );
AddMoreType( scanner, L"OPERATOR.RIGHT", L"\\)" );
AddMoreType( scanner, L"OPERATOR.BEGIN", L"\\{" );
AddMoreType( scanner, L"OPERATOR.END", L"\\}" );
AddMoreType( scanner, L"OPERATOR.SPLITER", L"," );
AddMoreType( scanner, L"OPERATOR.ARRBEGIN", L"\\[" );
AddMoreType( scanner, L"OPERATOR.ARREND", L"\\]" );
AddMoreType( scanner, L"OPERATOR.FINISH", L";" );
AddMoreType( scanner, L"NUM", L"[0-9]+" );
AddMoreType( scanner, L"REAL", L"([0-9]+\\.[0-9]*)|([0-9]*\\.[0-9]+)" );
AddMoreType( scanner, L"STRING", L"\"([^\\\\\"]|\\\\\\.)*\"" );
AddMoreType( scanner, L"COMMENT.discard", L"#[^\\n]*" );
  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-07-01 16:53 | 白开水
日哦,我写了N多的评论,一下就没了。
正则表达式的引擎的扩展部分,我还是没写```,人懒没办法。过几天最后几门考试考完了后开始看看语法分析部分了。

写这份代码总出过一个大BUG,一个小BUG,大BUG是自己一边调试一边想别的,结果一开始调试了6个小时,后来又调试3个小时总算搞定``,出错的地方很简单就是使用iterator的时候,next到下一个元素的时候,数组变长用了realloc后,指针变了```。哎,我郁闷到了。后来看设计模式的书,发现就讲了这点,删除和重新分配必须得保证那iterator一直正确才行```,羡慕用c++的,我用C,发现设计模式有些地方看不懂,特别是代码部分。

小BUG是昨天晚上出的,结果虽然都出来了,突然发现标记都错了。```,花了两个小时左右搞定。

算了不写了```,小v的文章简单易懂,大家该多看看。
  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-07-01 21:10 | 陈梓瀚(vczh)
设计模式里面的类和接口都是C语言里面没有的概念,模拟起来也比直接支持类的语言麻烦。  回复  更多评论
  
# re: 《构造正则表达式引擎》新鲜出炉啦! 2008-10-03 22:14 | 免费小说
仔细拜读,简单易懂。多谢  回复  更多评论
  

标题  
姓名  
主页
验证码 *
内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
[使用Ctrl+Enter键可以直接提交]
相关链接:
网站导航: