很好很强大的矬人，哇咔咔  回复  更多评论
  

果然经典哈 最后对学习方法的见解对我很有帮助  回复  更多评论
  

向您学习喽  回复  更多评论
  

词法分析部分写好了，不过扩展正则表达式部分懒的写，想先写语法分析器了。
用正则表达式的引擎提供了一套接口给词法分析器。测试了下
测试的内容如下，然后自己把一份代码粘帖了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]*" );
  回复  更多评论
  

日哦，我写了N多的评论，一下就没了。
正则表达式的引擎的扩展部分，我还是没写```，人懒没办法。过几天最后几门考试考完了后开始看看语法分析部分了。

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

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

算了不写了```，小v的文章简单易懂，大家该多看看。
  回复  更多评论
  

设计模式里面的类和接口都是C语言里面没有的概念，模拟起来也比直接支持类的语言麻烦。  回复  更多评论
  

仔细拜读，简单易懂。多谢  回复  更多评论
  

<b>sad</b>  回复  更多评论
  

不错，建议跟libpcre对测一下~  回复  更多评论
  

谢谢楼主这样的精品文章。  回复  更多评论
  

跟大侠请教一个问题：如果让引擎支持unicode的话，只能用分类压缩法。
例如如果只有一个字符单元为：a-z,
那么，内部字符集将被分割为：
编号1、0-96,
编号2、97-122,
编号3、123-65535,
但是有一个问题是在搜索的时候，如何才能快速的得到字符到字符集编号的转换呢？如果用您提到的一张65535个字符的大表来映射的话，也太粗鲁，太耗内存了吧?有没有什么更好的算法呢？那些有名的引擎是怎么做的呢，翻遍了internet没有这方面的任何资料。不知道大侠有什么好的建议？  回复  更多评论
  

@林林
65535*2不就128k，哪里粗鲁，哪里太耗内存了？其实一个程序同时存在的正则表达式是不多的。当然这是O(1)，如果你实在想减少内存，那就没有这么快了，传说中有一种数据结构叫线段树。  回复  更多评论
  

线段树! 谢谢大侠的指点！
之所以觉得耗内存是因为，我认为自己做正则引擎主要并不是用来做单纯的词法搜索的。因为现在正则引擎这么多，自己去做吃力又不讨好。自己做的主要目的在于做词法分析。现在的词法分析引擎还非常难用的，象flex等，生成出来的代码，看了想吐！完全不能接受这种风格的代码入侵到我的工程中。而词法分析是难于避免一个程序有多个分析引擎的。所以才会觉得耗费内存。  回复  更多评论
  

@ooseven
如果是自己的脚本引擎，完全可以手写一个此法分析，简单明了。
  回复  更多评论
  

楼主，我悲剧啊，我毕业两年了还要参考你在大学时期的文档来进行正则引擎的实现。。  回复  更多评论
  

@aho
你这个名字……  回复  更多评论
  

@陈梓瀚(vczh)
写得真好，让师兄很汗颜啊~~不太敢相信你是大三时候写的，特别是贪婪匹配算法那部分，补充了龙书的不足，正为怎么较优雅地设计正则的扩展功能而发愁呢.

话说你推荐的那本《Parsing Techniques》真的这么好吗~~？  回复  更多评论
  

@aho
嗯，真的那么好。  回复  更多评论
  

<<构造可配置词法分析器>>(词法分析.doc)
"在处理这种有冲突的规则的时候，既可以报错，也可以根据指定的优先级进行挑选。"
能否解释下"根据指定的优先级进行挑选"?
在这例子里,
状态AB读入[^a-z]则识别出if,
读入[a-z]则继续识别标识符.
难道这就是"根据指定的优先级进行挑选"?

还有, 字符转字符类,有个问题.
举一简单例子, 就识别标识符和十六进制数的状态图.
识别标识符用到的字符集: [a-z]、[A-Z]、_、[0-9]
识别十六进制数(0x????)用到的字符集: [0-9]、[a-f]、[A-F]、x
当字符转字符类的时候, 若当前字符为a, 那么该判定它属于字符集[a-f],
还是判定它属于字符集[a-z]?
请问怎么处理?

让"神"费心了, 谢谢.
  回复  更多评论
  

词法分析.doc 中的图用什么画啊?

"按照规则构造出四个DFA并将它们组合起来："
按那图, 标识符的长度岂不是只能为2?
1不行, 3 也不行?

  回复  更多评论
  

"这个其实跟正则表达式本身有关。至于什么正则表达式可以达到这个效果这里就不深究了。"
能否说下"什么正则表达式可以达到这个效果"?
不想深究, 只想知道什么样正则表达式, 就可以了.
  回复  更多评论
  

"123.ABC"
识别到"A"那里, 已经说明输入的字符串不合法, 直接报错说"expected digit but alpha encountered."就得, 为何还要继续分析"BC"?  回复  更多评论
  

"我们都要做一些额外的工作"
与
"我们将无从知道一个记号被识别出来的确切时间"
有何矛盾?
能否详细说明下?
  回复  更多评论
  

"行代表字符，列代表DFA的状态"

c代字
s代当前态
t代目标态
下述的,哪个对?
s1 s2
c1 t1 t2
c2 t3 t4
----------
c1 c2
s1 t1 t2
s2 t3 t4  回复  更多评论
  

"吞吐速度高达46万记号/秒","只有10%的时间花在了DFA上，90%的时间花在了处理结果的工作上"
统计本身没有代价(因统计而增加的开销)?
不统计的话, 程序应该跑得更快吧?

另:
请问用什么工具或代码来统计一个程序或代码段的各种开销(时、空)?
  回复  更多评论
  

正则 ==> ε-NFA ==> NFA ==> DFA
貌似文章没有讲如何"(E)BNF ==> 正则"?

(E)BNF ==> 正则 ==> ε-NFA ==> NFA ==> DFA
步骤太多!
能不能少点?比如
(E)BNF ==> DFA
  回复  更多评论
  

有些图的结束状态是粗边
有些图的结束状态是双边
一样吗?  回复  更多评论
  

@thircese
1：如果您仔细看文章就会发现，如果[a-f]存在，那么[a-z]是不存在的，存在
的只有[g-z]。
2：ENFA到DFA的步骤只能这么多，减少的话会让一个算法变得非常复杂。
3：只要记录一下开始跟结束的时间就可以记录时间了，自己写代码做。
4：词法分析那一节说的是一个中介状态可以包含旧的若干个DFA的若干个终结状态，因此会有那些结论。
5：其他问题，请自行阅读文章。所有与开发无关的问题我一概不解释，请利用您的智商和您的数学水平自行推导，譬如说哪个正则表达式可以用来深究的问题。BTW，我画图用的是微软公司伟大的照耀我们前进方向的全银河系唯一一个不需要看帮助就可以绘制专业图形的visio软件。还有，如何从状态机反着做出正则表达式不在这篇文章的讨论范围内。  回复  更多评论
  

谢谢您为我的"弱智"问题费神.
不过,
"貌似文章没有讲如何"(E)BNF ==> 正则"?"
中的"(E)BNF"是指"(扩展)巴斯克范式"
而不是指状态机ENFA哦!  回复  更多评论
  

@thircese
有一些EBNF无法被转换为正则，所以当然不存在EBNF到正则的转换了。倘若这是一个可以被转换为正则的EBNF，那那些非终结符肯定没有递归引用，那么你可以逐个消除他们。譬如说a=b "."; b = "+"消除b的结果就是a="+" "."。最后剩下一条，就是正则表达式了。  回复  更多评论
  

有幸拜读阁下两篇文章，受益匪浅，谢过！  回复  更多评论
  

两个链接都失效了，可以重新链接下？  回复  更多评论
  

@steven
估计是bug，我发邮件给cppblog了  回复  更多评论
  

下不了  回复  更多评论
  

师兄啊  回复  更多评论
  

最近一直在学习python，刚好做爬虫的时候涉及到了正则表达式这一块？。想弱弱的问一句有没有可能用python来实现这个正则表达式引擎呢？ 非常谢谢你。（不是不想用c++，而是想暂时先专注于python。）  回复  更多评论