请教一个正则匹配的问题

flw2

Hi, all

pattern seems like \(subregexp1\) \| \(subregexp2)\ \| ....

I want to know if there is some way to dicide which subregexp(S) match the text when the whole regexp(dfa) says it matches;

This is my original problem:
There are about 200-2000 regexp, given a text, how to match _quickly_(so not an for(;statements)

e.g.

1. a.*b
2. b.*c
3. c.*d
text is "abce"

then result is "regexp 1 and 2 match"
I also want to know 1 and 2 matches which part of the text respectively。
Any help is  greatly appreciated.

flw2

说的好， 我就是要让n 个dfa的states 和ac类似

感觉是能可以做到， 正在朝这方面想

flw2

我的问题能得到解决

flex应该不是一个一个一个匹配， 不过 flex的代码没来得及看
龙书上确实指明了方向（今天下午去按摩的时候想起的）， 3.8节， 只是flex执行最长匹配， 我不需要，任何时候匹配都符合我的要求， 这个不难做到，grep有现成的，真爽
改动不会太大，不到100行代码。
贴一下核心结构，  以防忘记，  我看来应该是没问题的

/* A state of the dfa consists of a set of positions, some flags,
   and the token value of the lowest-numbered position of the state that
   contains an END token. */
typedef struct
{
  int hash;                        /* Hash of the positions of this state. */
  position_set elems;                /* Positions this state could match. */
  char newline;                        /* True if previous state matched newline. */
  char letter;                        /* True if previous state matched a letter. */
  char backref;                        /* True if this state matches a \<digit>. */
  unsigned char constraint;        /* Constraint for this state to accept. */
  int first_end;                /* Token value of the first END in elems. */
  char *regexp;
} dfa_state;


first_end是反查用的
first_end在grep-2.0 里面(我看的代码)里确实没有用到， 它是用来反查的， 和龙书上写的情况类似。
我加了一些代码， 实现了！

第一次自己解决难题， 庆祝一下

flw2

问题来了, 还得请大家帮助

并在一起后内存消耗太大了, 不知道flex怎么做的
flex的代码实在邪恶, 而且不是直接构造dfa

flw2

今天大致看了一下，flex-2.5.3
基本和 cjaizss 说的类似
合并成一个自动机
a[^b]{30000} {}
(a|b)[^b]{30000} {}
直接就挂了， flex没有延迟生成状态，不像grep， 所以它只能限制状态的大小
最后转换表使用的是龙书上说的方法进行的压缩

我的规则就是太多了， 并在一起太大了，听说flex是并行的所以想看看它怎么做的
现在看来和grep做的除了表压缩和延迟生成state之外基本类似， 不过我要解决的问题本来也是没解的问题。 规则一大内存指数上升，没有办法

多谢几位

flw2

原帖由 cjaizss 于 2008-12-5 16:48 发表
对于这个问题,我突然觉得直接用LEX也可以做出来

像grep flex典型的比较好的实现也没有考虑到规则太多太复杂的情况
比如 flex 使用bubble， 理由是状态不会太多， grep 进行state生成时对postion集合操作使用一个大数组， 理由类似
至于flex优先匹配这些都很容易改动
不过flex不行， 因为flex实现的是match,不是search， flex本身不需要search

我的问题已经没有高度了， 只是工程问题了