表示“不含某个字符串”的正则表达式

bankrock · #1 (**permalink**) 2008-09-22

表示不含某个字符的正则表达式很简单，问题是如何在正则表达式中表示“不含有某个字符串”。
比如一种可能的表示不含ab的正则表达式如下：

引用:

([^a]|a[^b])*

这个正则表达式无法判定b前含有偶数个a的字符串（如aaaab）。改为

引用:

([^a]|a*[^b])*

可以解决上述问题。但是表示其他字符串，如“不含abc"或者不含"aabb"的字符串，的方法可能更加复杂。例如这个查找C/C++的注释语句的正则表达式(Finding Comments in Source Code Using Regular Expressions
对于这类问题有没有通用的解法？

cat · #2 (**permalink**) 2008-09-23

这个是不是超过了正则语言的表述范围了啊？？
不过话说当今能用得正则表达式库早就超过正则语言了……

bankrock · #3 (**permalink**) 2008-09-24

Dragonbook上也有这种问题，C/C++编译器做Lexical analysis时也会碰到这类问题吧，有经验的来说说。

liuxinyu · #4 (**permalink**) 2008-10-09

我个人的意见是不用正则表达式，而用状态机扫描。反而简单
lexer/parser不就是这么干的么？

GENESIS · #5 (**permalink**) 2008-11-28

呵呵怎么看怎么像SQL语句

bankrock · #6 (**permalink**) 2008-12-04

引用:

作者: liuxinyu

我个人的意见是不用正则表达式，而用状态机扫描。反而简单
lexer/parser不就是这么干的么？

这个应该做不到吧，lexer处理Not的方法是将所有不属于集合的代表都列举出来，如果是>1的字符串的话这可是指数增长的。状态机一般也没有表示非某个值得方法。