手摸手，带你实现简易版正则引擎

章节序言

功能介绍：

入口方法介绍：我们要提供一个方法，testReg，参数有两个，一个是待验证的字符串str，另一个是正则表达式reg，返回一个布尔值，即是否匹配

正则表达式规则介绍：

这个正则表达式要以 ^ 开头，以 $ 结尾

[] 表示匹配字符集合中的一个字符，[] 后可以接 * 或者 +

* 表示匹配 0 个或者 0 个以上多个

+ 表示匹配 1 个或者 1 个以上的多个

// 正则表达式举例
^[123]*mn[ab]+cd$
^a[ab]+$
...

仓库地址：js-regular

思路解析

我们遇到一个问题，需要先思考，有了思路之后再进行编码，避免重复修改导致代码的混乱以及时间的浪费。

那么，我们首先要思考我们的目标是啥，既然我们本篇文章的主题是自动机，也没必要卖关子，我们第一步想到的肯定是， 把正则表达式转换成自动机，之后借助这个正则匹配的自动机去匹配我们的字符串。

那么我们如何把一个正则表达式转换成一个自动机呢？

我的思路是这样的：

正则表达式

具有匹配含义的独立单元序列

正则匹配自动机

复制代码

我来简单解读一下，我会把这个问题分成两部分，首先我需要解析字符串，之后转换成具有匹配含义的独立单元序列，即 TOKEN 序列。什么叫做具有匹配含义的独立单元序列呢？

我举个例子：

正则表达式是 ^[123]+[a]*3$ ，那么其它可以分成三个独立单元即：

[123]+
[a]*
3

但是我肯定不会只是拆成三个字符串，我还是会变成三个具有含义的对象(便于生成自动机)，但是这都是后话了。

之后我们要把 具有匹配含义的独立单元序列（我真的是起名鬼才🐶）转换成自动机，既然我们都说了我会用对象表示每个独立单元，那最简单的方法就是在这个对象中加入 next 属性，当然 next 可能是一个数组，存储着所有可能的分支。

之后我们再写一个方法，让自动机跑起来就好了。

ok，说干就干，下面我们将进入代码分步骤展示与解读环节，请大家跟着我一起思考。

入口方法 - testReg

// the entry function
const testReg = (str, reg) => {
    if (!reg.startsWith('^') || !reg.endsWith('$')){
        // it's not a right reg string
        throw Error('format mismatch！');
    }
    const generator = getGeneratorStart(reg);
    return isMatch(str, generator);
    //console.log(matchStructure)
}

入口方法很直白，大家看我这里接受两个参数，第一个 str 是待匹配的字符串，第二个 reg 是正则表达式。

首先我对正则表达式做了验证，如果正则表达式不以 ^ 开头，以 $ 结尾，表示这个表达式是无效的，是不合法的。之后我们调用了 getGeneratorStart 方法获取了自动机的开始状态，之后调用 isMatch 方法对字符串进行一个匹配。

获取自动机方法 - getGeneratorStart

// use reg to get generator and return start Pattern Object
const getGeneratorStart = (reg) => {
    const regStr = reg.slice(1, reg.length - 1);
    const patternObjList = getPatternObjList(regStr);
    const generator = getGenerator(patternObjList);
    return generator;
}

又是一个很短很直白的方法，第一步我们对正则表达式做了一个截取，掐头去尾（去掉开头的 ^ 和结尾的 $ ），留下真正有效的部分。之后我们又调用了两个方法 getPatternObjList 和 getGenerator 。这两个方法和之前我在思路解析中表达的一致:

getPatternObjList: 输入是 regStr ，即正则表达式字符串，输出是 具有匹配含义的独立单元序列
getGenerator: 输入是前一步的输出，即具有匹配含义的独立单元序列，输出是自动机的起始状态。

获取单元序列方法 - getPatternObjList

// change reg String to Pattern Ojects and return list
const getPatternObjList = (regStr) => {
    const len = regStr.length;
    let patternObjlist = [];
    let isInCollection = false;
    let collection = []; // used to store current collection
    for (let i = 0; i < len; i++) {
        const char = regStr[i];
        if (!isInCollection) {
            // 
            if (char != '[') {
                // single char object
                patternObjlist.push({
                    isCollection: false,
                    pattern: [char],
                    next: []
                })
            } else {
                // char === [ we need to change isInCollection to true
                isInCollection = true;
            }
        } else {
            if (char != ']') {
                collection.push(char);
            } else {
                // ] is the sign end of collection
                isInCollection = false;
                // collectionSign maybe * or + 
                let collectionSign = regStr[i + 1];
                let collectionType = 'COMMON';
                if( collectionSign && collectionTypes.includes(collectionSign) ){
                    collectionType = collectionSign
                    i++;
                }
                patternObjlist.push({
                    isCollection: true,
                    pattern: collection,
                    collectionType,
                    next: []
                })
                collection = [];
            }
        }
    }
    return patternObjlist;
}

这个方法比较长，但其实就是字符串的一遍遍历，其实看上去比较简单，但是值得注意的是我把具有匹配含义的独立单元序列转换成的数据结构：

[] 集合对应的数据结构

{
    isCollection: Boolean,
    pattern: Array,
    collectionType: emun,
    next: Array
}

正常字符串对应的数据结构

{
    isCollection: Boolean,
    pattern: Array,
    next: Array
}

其中

pattern 存储着所有可能的匹配，比如 [123]+ 这个 pattern 就是 [1, 2, 3]
collectionType 存储着是 * 还是 + 还是 COMMON，方便后续生成自动机时处理

我给大家演示一下方法的输入输出：

输入：
^[123]+[a]*3$
输出：
[
  {
    isCollection: true,
    pattern: [ '1', '2', '3' ],
    collectionType: '+',
    next: []
  },
  {
    isCollection: true,
    pattern: [ 'a' ],
    collectionType: '*',
    next: []
  },
  { 
    isCollection: false, 
    pattern: [ '3' ], 
    next: [] 
   }
]

单元序列转换为自动机方法 - getGenerator

// change pattern list to regular generator
const getGenerator = (patternObjList) => {
    patternObjList.push({
        isEnd: true,
    }) // the end signal of generator
    let start = {
        isStart: true,
        next:[]
    }; // generator need a 'start' to start valid
    const len = patternObjList.length;
    start.next = getNext(patternObjList, -1);
    for(let i = 0; i < len; i++ ){
        const curPattern = patternObjList[i];
        curPattern.next = getNext(patternObjList, i)
        if(collectionTypes.includes(curPattern.collectionType)){
            curPattern.next.push(curPattern);
        }
    }
    return start;
}

我们先给 getPatternObjList 方法返回值数组加入起始状态和结束状态。之后我们给起始状态的 next 初始化，之后循环遍历数组，为数组的每一项的 next 初始化，这样就通过 next 中存储的指针将自动机的各个状态串联起来了。

注意：这里 next 数组的每一项都是 patternObjList 数组中对象的引用。以及最后如果 collectionType 是 * 或者 + 还要把自己追加进去，这类的节点可以自循环

之后我们看一下其中的子方法 getNext ，我就不单独开一个章节了，因为这两个方法关联性很强。

// get PatternObj's next
const getNext = (patternObjList, index) => {
    let next = [];
    const len = patternObjList.length;
    for(let i = index + 1; i < len; i++){
        const nextPattern = patternObjList[i]
        next.push(nextPattern)
        if(nextPattern.collectionType != '*'){
            // * need to handle, * is possible no
            break;
        }
    }  
    return next;
}

其实最关键就是处理 * ，因为 * 表示 0 个或者 0 个以上的多个，就要继续往后遍历。

比如 a[b]*c 这样的正则表达式，a 后面跟的可能是 b 也可能是 b 后面的 c

最后我们可以看一下这个自动机的输出

输入：
^[123]+[a]*3$
输出：
// 这里因为可能有循环引用的关系，所以输出会有问题，但是大家也可以通过这个结构一窥究竟
{
  isStart: true,
  next: [
    {
      isCollection: true,
      pattern: [Array],
      collectionType: '+',
      next: [Array]
    }
  ]
}

自动机图例展示

输入：^[123]+[a]*3$

图例：

网络异常，图片无法展示

验证匹配方法 - isMatch

// use generator to test string
const isMatch = (str, generator) => {
    if(generator.isStart){
        // the start of recursive
        for(const nextGen of generator.next){
            if(isMatch(str, nextGen)) return true;
        }
        return false;
    } else if(generator.isEnd){
        // if generator is end but str is not end return false
        return str.length ? false : true;
    } else {
        if(!str.length){
            return false;
        }
        if(!generator.pattern.includes(str[0])) {
            return false;
        } else {
            const restStr = str.slice(1);
            for(const nextGen of generator.next){
                if(isMatch(restStr, nextGen)) return true;
            }
            return false;
        }
    }
}

这里其实就是一个递归程序：

如果自动机的当前处于起始状态：不进行匹配，循环匹配 next，只要有一条分支匹配成功，就是合法字符串
如果自动机的当前处于结束状态：判断方法传入的 str 长度是否是 0 ，如果是 0 则表示待匹配字符串也匹配完成了，是合法字符串，反之不合法。
其他情况：匹配当前字符是否在 pattern 数组中，如果在就表示当前字符匹配，继续循环匹配 next，只要有一条分支匹配成功，就是合法字符串

于是

这样我们的代码就完成了！

输出演示

网络异常，图片无法展示

结果正确🌟

完整代码

方便大家复制粘贴或者完整回顾，是不是很贴心❤️

const collectionTypes = ['*', '+'];
// change reg String to Pattern Ojects and return list
const getPatternObjList = (regStr) => {
    const len = regStr.length;
    let patternObjlist = [];
    let isInCollection = false;
    let collection = []; // used to store current collection
    for (let i = 0; i < len; i++) {
        const char = regStr[i];
        if (!isInCollection) {
            // 
            if (char != '[') {
                // single char object
                patternObjlist.push({
                    isCollection: false,
                    pattern: [char],
                    next: []
                })
            } else {
                // char === [ we need to change isInCollection to true
                isInCollection = true;
            }
        } else {
            if (char != ']') {
                collection.push(char);
            } else {
                // ] is the sign end of collection
                isInCollection = false;
                // collectionSign maybe * or + 
                let collectionSign = regStr[i + 1];
                let collectionType = 'COMMON';
                if( collectionSign && collectionTypes.includes(collectionSign) ){
                    collectionType = collectionSign
                    i++;
                }
                patternObjlist.push({
                    isCollection: true,
                    pattern: collection,
                    collectionType,
                    next: []
                })
                collection = [];
            }
        }
    }
    return patternObjlist;
}
// get PatternObj's next
const getNext = (patternObjList, index) => {
    let next = [];
    const len = patternObjList.length;
    for(let i = index + 1; i < len; i++){
        const nextPattern = patternObjList[i]
        next.push(nextPattern)
        if(nextPattern.collectionType != '*'){
            // * need to handle, * is possible no
            break;
        }
    }  
    return next;
}
// change pattern list to regular generator
const getGenerator = (patternObjList) => {
    patternObjList.push({
        isEnd: true,
    }) // the end signal of generator
    let start = {
        isStart: true,
        next:[]
    }; // generator need a 'start' to start valid
    const len = patternObjList.length;
    start.next = getNext(patternObjList, -1);
    for(let i = 0; i < len; i++ ){
        const curPattern = patternObjList[i];
        curPattern.next = getNext(patternObjList, i)
        if(collectionTypes.includes(curPattern.collectionType)){
            curPattern.next.push(curPattern);
        }
    }
    return start;
}
// use reg to get generator and return start Pattern Object
const getGeneratorStart = (reg) => {
    const regStr = reg.slice(1, reg.length - 1);
    const patternObjList = getPatternObjList(regStr);
    const generator = getGenerator(patternObjList);
    return generator;
}
// use generator to test string
const isMatch = (str, generator) => {
    if(generator.isStart){
        // the start of recursive
        for(const nextGen of generator.next){
            if(isMatch(str, nextGen)) return true;
        }
        return false;
    } else if(generator.isEnd){
        // if generator is end but str is not end return false
        return str.length ? false : true;
    } else {
        if(!str.length){
            return false;
        }
        if(!generator.pattern.includes(str[0])) {
            return false;
        } else {
            const restStr = str.slice(1);
            for(const nextGen of generator.next){
                if(isMatch(restStr, nextGen)) return true;
            }
            return false;
        }
    }
}
// the entry function
const testReg = (str, reg) => {
    if (!reg.startsWith('^') || !reg.endsWith('$')){
        // it's not a right reg string
        throw Error('format mismatch！');
    }
    const generator = getGeneratorStart(reg);
    return isMatch(str, generator);
    //console.log(matchStructure)
}
console.log(testReg('2131aa3', '^[123]+[a]*3$'));

章节小结

本章我们用前面几章所学的知识实现了一个简易的正则🌟，当热真正的正则引擎要复杂的多的多，也会有预编译等我还没有接触过的流程。但是文章领进门，修行还是在个人的，相信大家与我一同完成这个简易的正则匹配之后也会获得一些解决问题的思路，或者多了一些思考，感谢大家与我一起体验这个过程，不妨点个赞呀👍 ，或者关注➕ 给我更大的动力，与你们一起学习成长。

结束语

网络异常，图片无法展示

正则原理浅析章节部分内容参考：正则表达式引擎执行原理——从未如此清晰！感谢前辈的分享。

感谢母校吉林大学的教材课件～

感谢作者大佬洛竹有关某些特殊内容🐶的经验分享～

感谢运营姐姐少女骑士的抱枕，让我战斗力满满～

最后，我是寒草，一只草系码猿🐒，，大家喜欢我的文章不妨关注➕ ，点赞👍 。你们的支持是我最大最大最大的动力～

乾坤未定，你我皆是黑马🔥

葱鸭🦆

草系前端手摸手带你实现正则引擎，点燃夏日最热情的烟火（三）🔥

手摸手，带你实现简易版正则引擎

章节序言

思路解析

入口方法 - testReg

获取自动机方法 - getGeneratorStart

获取单元序列方法 - getPatternObjList

单元序列转换为自动机方法 - getGenerator

自动机图例展示

验证匹配方法 - isMatch

输出演示

完整代码

章节小结

结束语

热门文章

最新文章

相关课程

相关电子书

相关实验场景