正则表达式算法悬赏 1000分

Perlvim

有创意的代码均会被转账1000积分

要求：实现 ^ $ * 的功能：

先发布一段 C 实现的代码：

1. /* match */
   
2. int match(char *regexp, char *text) {
   
3.     if (regexp[0] == '^') {
   
4.         return matchhere(regexp+1, text);
   
5.     }
   
6.     do {
   
7.         if (matchere(regexp, text)) {
   
8.             return 1;
   
9.         }
   
10.     } while (*text++ != '\0');
    
11.     return 0;
    
12. }
    
13. 
    
14. /* mtchhere: */
    
15. int matchhere(char *regexp, char *text) {
    
16.     if (regexp[0] == '\0') {
    
17.         return 1;
    
18.     }
    
19.     if (regexp[1] == '*') {
    
20.         return matchstar(regexp[0], regexp+2, text);
    
21.     }
    
22.     if (regexp[0] == "$" && regexp[1] == '\0') {
    
23.         return *text == '\0';
    
24.     }
    
25.     if (*text != '\0' && regexp[1] == '\0') {
    
26.         return matchhere(regexp+1, text+1);
    
27.     }
    
28.     return 0;
    
29. }
    
30. 
    
31. int matchstar(int c, char *regexp, char *text) {
    
32.     do {
    
33.         if matchhere(regexp, text) {
    
34.             return 1;
    
35.         } while (*text != '\0' && (*text++ == c || c == '.'));
    
36.         return 0;
    
37.     }
    
38. }

复制代码

以上代码抄自《代码之美》

我正尝试用Perl实现一个具有基本正则能力的匹配算法。稍后会发布上来。可能超过 500 行

q1208c

perl内置了 正则, 你再重新来搞一下, 何必呢?

Perlvim

只是学习一下而已

mcshell

围观答案。。。

wxlfh

不懂楼主什么意思。

Perlvim

正则表达式虽然是一种广泛存在于各种编程语言中的一种基本能力，但实现各不相同，功能也有强有弱，还有一些语言，没有正则的扩展，例如asm, Lua的正则库非常简单。

许多基础的算法，都大量的使用正则匹配功能，如果有明白简单的实现算法，那么就可以在一些没有正则算法环境中快速建立这种能力。

zhlong8

《精通正则表达式》里面应该有C代码吧，写个 Perl 版的练手应该很不错。

Perlvim

没有找到代码实现，主要是原理性阐述。

Monox

也可以去读读 Perl 6 的正则是怎么实现的，这个肯定比 C 语言的代码实现读起来容易多了。Perl 6 的正则除了 rakudo/nqp 里的实现外还有 masak 的 gge 是用纯 Perl 6 写的 Perl 6 grammar engine，只是 gge 好像有两年没更新了，不知道它的实现到什么程度了，但是我相信它对一般的正则支持肯定是有了。

Monox

Perlvim 发表于 2012-12-31 08:49
正则表达式虽然是一种广泛存在于各种编程语言中的一种基本能力，但实现各不相同，功能也有强有弱，还有一些语言，没有正则的扩展，例如asm, Lua的正则库非常简单。

许多基础的算法，都大量的使用正则匹配功能，如果有明白简单的实现算法，那么就可以在一些没有正则算法环境中快速建立这种能力。

这是完全没有必要的，因为大多数语言都支持 C 库的链接，而 C 有一个著名的 PCRE 库实现的就是 Perl 5 兼容的正则表达式，比如 R 语言直接支持好几种正则表达式引擎，其中有一个就是对 PCRE 的封装。你举的例子里的 Lua，其语言本身就有一个相当显著的特性，就是极易与 C 交互，因此即使你不喜欢 Lua 提供的正则表达式，也不喜欢 Lua 强大的 lpeg 库的话，你仍旧可以对 PCRE 的 C 库进行封装，而且我相信这样的封装甚至其实已经存在了。而且近来的趋势是尽量不使用正则表达式，因为正则表达式用于小问题还行，用于稍微复杂一点的问题就显示出了它本身的 ugly，所以 Lua 才有了 lpeg，很多其它语言也有了 peg 的实现，除了 Lua 外还有C, Ruby 等，Perl 6 也借鉴 Haskell 的 Parserc 模块而提供了 Grammar 解析的功能。而且，虽然 Haskell 提供了很多语法解析用的模块，仍旧也有正则表达式模块对 C 的 PCRE 库进行封装。要自己临时写一个功能完整，又效率可以接受的正则表达式引擎还是得花不少时间的，所以个人认为如果不是为了研究正则表达式的实现并对它进行扩展或者纯粹只是为了好玩（或者向别人炫耀）之类的就完全没有自己写的必要。