请教一个正则匹配的问题

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.

cjaizss

这个恐怕比较难,regex比较复杂,我能想到的也只有regex形成父子关系:
比如
a~regex1 -> a~regex2
则regex1作为regex2的上层(先检验)

baohuaihuai

这个很复杂吧，得看正则表达式的具体形态了，我觉得有几种可能的方式：
1.如果这些正则表达式几乎没有任何可寻找的规律，那你可以考虑的就是把这些正则表达式合并成一个大DFA。这个是可行的，就是工作量很大，需要的存储空间也很大，关键是针对你的第二个需求，需要记的状态可能太多了（比如一个字符串有1000个a，后面还有1000个b，针对你的regex1，就有一百万种匹配结果组合了），而且因为是DFA所以对正则表达式也有限制。
2.如果正则表达式存在一些层次逻辑的联系，那可以考虑把这200-2000个正则表达式组织成树形结构（可能和楼上cjaizss的说法是一个意思？）
3.如果这些正则表达式主要都是一些字串匹配类型的，那就考虑用AC等多字符串匹配算法吧。

[ 本帖最后由 baohuaihuai 于 2008-11-13 13:42 编辑 ]

cjaizss

一般应该没有什么没有太高效率的匹配手段,regex的结构还是千奇百怪,一般没啥可比性.

cjaizss

1. a.*b
2. b.*c
3. c.*d
不过如果真的都像LZ这么简明的regex,应该是有效率相对高的手段的

flw2

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

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

cjaizss

是不是都是x.*y这样的regex?
x,y为任意字符。
那么可以先为所有的x.*y建一个表，等我下班回去详细再说

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

cjaizss

lex编译器编译完lex语言之后的C代码里,是找不到正则表达式的.没有研究过lex编译器具体是怎么写的,但是我猜想过程应该是为每个正则表达式生成一个接受的状态机,然后把这些状态机合并,拼成一个大的状态机.