练习：判断字符串是否与给定的正规式匹配

汀洲杜若 / 2023-05-07 / 原文

代码写完后应该是这个效果：控制台键入“./a.exe 'a(b|c)*d' acbcd<回车>”，可以看到控制台显示“True”。

大致流程：

判断参数个数，参数不够就给出提示。
分析正规式的正确性。合法字符是数字、英文字母大小写、下划线、左右小括号、竖线“|”和星号“*”。
用树结构存储正规式。
对于每个树节点，计算当前位置的字串是否符合当前节点的匹配规则。
显示结果，结束。

节点就四种：基本单词节点、闭包节点、连接节点和分支节点，用 struct node{int type; union{......};}; 这样的结构存储就行。连接节点和分支节点的存储结构相同。

enum/*节点类型*/{ ND_WORD, ND_CAT, ND_CLOSURE, ND_BRANCH };
struct word_node{
    const char *str;
    int nchar;
};
struct list_node{
    struct node **pp;//指向一堆指针
    int nitem;
    int nalloc;
};
struct node{
    int type;
    union{
        struct word_node word;
        struct list_node list;//ND_CAT,ND_BRANCH节点用此结构
        struct node *closure;
    };
};

树的构建过程就用递归下降的方法吧，比较直观。仔细想想正规式串的文法其实挺简单，大概是：<B>:=<C>，<B>:=<C>'|'<B>，<C>:=<Q><C>，<C>:=ε，<Q>:=<W>，<Q>:=<W> '*'，<W>:=<L><W>，<W>:=ε，<L>:='a'|'b'|...'z'|'_'。B分支，C连接，Q闭包，W单词，L字母。

下面伪代码的作用是尝试构建对应于“连接操作”的树节点。其它节点的构造方式差不多，反正就是递归下降分析法，废话不多讲。

struct node *concat() {
　　 if(!(t = closure()))//降到closure一级
        return NULL;
    if(!canbe_firstof_simple(*cursor))
        //后面没有可用内容就不新建连接节点了，直接把t返回就行
        return t;
    w ← 新建连接节点, goto err if failed;
    add t to w->list, goto err if failed;
    do{
        if(!(t = closure())) goto err;
        add t to w->list, goto err if failed;
    }while(canbe_firstof_simple(*cursor));
    return w;
err:
    destroy node t and w;
    return NULL;
}

下面的代码检查给定字符串是否和正规式匹配。执行之前cursor指向字符串开头。

test(struct node *x) {
    if(!x) return false;
    switch (x->type) {
    case ND_WORD:
        if(!memcmp(cursor, x->word.str, x->word.nchar)){
            cursor += x->word.nchar;
            return true;
        }
        return false;
    case ND_CLOSURE:
        while(test(x->closure));
        return true;
    case ND_CAT:
        for(int i = 0; i < x->list.nitem; i++)
            if(!test(x->list.pp[i]))
                return false;
        return true;
    case ND_BRANCH:
        for(int i = 0; i < x->list.nitem; i++)
            if(test(x->list.pp[i]))
                return true;
        return false;
    }
    return false;
}

上层驱动的逻辑是：

match(str,pat) {
    if(!str) return false;
    cursor = pat;
    struct node *t = branch();//使用递归下降方法构建一棵树
    if(*cursor != ENDMARK) {
        puts("wrong pattern");//分析完了但cursor没走到头
        destroy_node(t);
        return false;
    }
    cursor = str;
    bool r = test(t) && *cursor == ENDMARK;
    destroy_node(t);
    return r;
}