简易正则表达式匹配器

最近在读《代码之美》，这边把阅读过程中的感悟记录下来。

第一章实现了一个简易的正则表达式匹配器，用来处理以下的模型。

字符	含义
c	匹配任意的字母c
.(句点)	匹配任意的单个字符
^	匹配输入字符串的开头
$	匹配输入字符串的结尾
*	匹配前一个字符的零个或者多个出现

原文用c语言实现了一个最小的正则表达式代码块，它可以很好地诠释正则表达式的基本思想，并且能够识别出一组有用的并且重要的模式，而且它的代码长度很短。

Rob给出的实现本身就是漂亮代码的一个极佳示例：紧凑、优雅、高效并且实用。这是我所见过的最佳的递归示例之一，在这段代码中还展示了C指针的强大功能。虽然当时我们最关心的是如何通过使程序更易于使用（同时也更易于编写）来体现良好记法的重要性，但正则表达式代码同样也是说明算法、数据结构、测试、性能增强以及其他重要主题的最好方式。

以下是匹配算法的代码：

/* match：在text中查找regexp */
int match(char *regexp, char *text)
{
    if (regexp[0] == '^')
        return matchhere(regexp+1, text);
    do { /* 即使字符串为空时也必须检查 */
        if (matchhere(regexp, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

/* matchhere：在text的开头查找regexp */
int matchhere(char *regexp, char *text)
{
    if (regexp[0] == '\0')
        return 1;
    if (regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
        return matchhere(regexp+1, text+1);
    return 0;
}

/* matchstar：在text的开头查找c*regexp */
int matchstar(int c, char *regexp, char *text)
{
    do { /* 通配符 * 匹配零个或多个实例 */
        if (matchhere(regexp, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}

下面是我用Python重构的：

def match(regexp, text):
    if not regexp:
        return True
    if regexp[0] == '^':
        return matchhere(regexp[1:], text)
    for i in range(len(text)):
        if matchhere(regexp, text[i:]):
            return True
    return False

def matchhere(regexp, text):
    if not regexp:
        return True
    if len(regexp) > 1 and regexp[1] == '*':
        return matchstar(regexp[0], regexp[2:], text)
    if len(regexp) == 1 and regexp[0] == '$':
        return True if not text else False
    if text and (regexp[0] == text[0] or regexp[0] == '.'):
        return matchhere(regexp[1:], text[1:])
    return False

def matchstar(c, regexp, text):
    for i in range(len(text)):
        if matchhere(regexp, text[i:]) and matchhere(c*i, text[:i]):
            return True
    return False

讨论

函数match(regexp, text)用来判断文本中是否出现正则表达式，如果找到了一个匹配的实例则返回True，否则返回False。如果有多个匹配的实例，那么函数将找到文本中最左边的并且最短的匹配实例。

match函数中的基本操作简单明了。如果正则表达式给了空字符串，那么始终返回True；如果正则表达式中第一个字符是^，那么匹配实例就一定要出现在字符串的开头。如果第一个字符不是^，那么正则表达式就可以在字符串中的任意位置上进行匹配。

大部分的匹配工作都是在matchhere(regexp, text)函数中完成的，这个函数将判断正则表达式与文本的开头部分是否匹配。函数matchhere把正则表达式的第一个字符与文本的第一个字符进行匹配。如果匹配失败，那么在这个文本位置上就不存在匹配，因此将返回False。然而，如果匹配成功了，函数将递进到正则表达式的下一个字符和文本的下一个字符继续进行匹配。这是通过递归地调用matchhere函数来实现的。

由于可能存在着一些特殊的情况，以及需要设置终止递归的条件，因此实际的处理过程要更为复杂些。最简单的情况就是，当正则表达式递进到末尾时（not regexp），所有之前的判断都成功了，那么这个正则表达式就与文本匹配。

如果正则表达式是一个字符后面跟着一个*，那么将会调用matchstar来判断闭包是否匹配。函数matchstar(c, regexp, text)将尝试递进地在text中匹配*后面的部分，如果发现可以使用matchhere匹配成功，并且此时text除去匹配成功的部分，其余部分能和都是字符c的正则表达式匹配时，函数返回True。

如果在正则表达式的末尾包含了一个$，那么仅当text位于末尾时才会匹配成功：

if len(regexp) == 1 and regexp[0] == '$':
        return True if not text else False

如果没有包含$，并且当前不是处于text字符串的末尾（if text），并且text字符串的第一个字符与正则表达式的第一个字符相匹配（regexp[0] == text[0] or regexp[0] == '.'），那么到现在为止都是没有问题的，我们将接着判断正则表达式的下一个字符是否匹配text的下一个字符，这是通过递归调用matchhere函数来实现的。这个递归调用不仅是本算法的核心，也是这段代码如此紧凑和整洁的原因。

如果所有这些匹配尝试都失败了，那么正则表达式和text在这个位置上就不存在匹配，因此函数matchhere将返回0。

其他的方法

上述代码实现的是最短匹配，考虑这个正则表达式（.*），它将匹配任意长度的text，假设给定的text如下：123abc，那么matchstar('.', '', '123abc')在运行到text中的第一个字符时就已经结束了，为了实现最长匹配，我们必须对matchstar函数进行改造，使其在匹配成功后也能继续递进一直进行到不能匹配为止：

def matchstar(c, regexp, text):
    flag = False
    for i in range(len(text)):
        if matchhere(regexp, text[i:]) and matchhere(c*i, text[:i]):
            flag = True
        else:
            if flag:
                break
    return flag