DIY一个正则匹配引擎

网上看过不少代码的教程，有些按照步骤来一段段代码解读 （篇幅会很长） ，有些会简化代码来讲解，然后逐步扩展 （篇幅也会很长） ，有些干脆直接源代码放出来，在上面注解。

我自己也一直在思考如何把代码讲解这件事表达得更好、更容易理解。

代码的组织其实是个 非线性 的过程，各种调用穿插，如果按照写文章的逻辑呈现 （线性） ，讲解过程中总会碰到读者突然不明白的情况。

可视化的图解 是一个比较好的讲解形态，但是又不适合文章的形态，所以今天我采用了一种， 在文章里只讲解构建的原理，着重方法，然后读者带着方法去读源代码 （注解过的） 。

我们考虑DIY一个正则匹配的引擎，采用 JavaScript ，为了代码的美观，可维护，我们采用 单例模式 来编写我们的代码。

class MyRegex {
    static getInstance(...arg) {
        if (!MyRegex.instance) MyRegex.instance = new MyRegex(arg);
        return MyRegex.instance;
    }
    constructor() {
        console.log('运行一次')
    }
    test(){}
}

使用的时候，是这么调用的：

MyRegex.getInstance().test();

我们接下来只要修改test方法，或者类似于test方法的方式不断地扩展我们的代码就行啦~

- 简化

首先我们把引擎简化下，只考虑匹配一个字符的情况。

编写一个函数matchOne，该函数的输入是一个pattern和一个text，输出是一个布尔值，表示它们是否匹配。

matchOne(pattern, text) {
  return pattern === text;
}

- 递归

递归是非常好的解决方案。我们将要重复调用 matchOne 。现在，我们要添加对更长长度的pattern和text字符串的支持。同样的，我们需要把问题简化下，暂时让我们仅考虑相同长度的pattern-text对。

match(pattern, text) {
  return (
      this.matchOne(pattern[0], text[0]) && this.match(pattern.slice(1), text.slice(1))
    );
}

递归函数有个明显特征，函数内部继续调用自身：

function match(){
    ...
    match()
}

-考虑各种分支

当我们完成了基本的骨架之后，接下来，要考虑各种情况，比如pattern可能是个空值，text也可能是个空字符串，还有当pattern是特殊字符（比如*?.）等等。

举个例子：

matchOne(pattern, text) {
// 当pattern为空的时候，任意文字都是匹配的
  if (!pattern) return true; 
// 当pattern不为空，但是text为空，返回false
  if (!text) return false; 
// 当pattern为.时，任意文字都是匹配的
  if (pattern === ".") return true; 
  return pattern === text;
}

-适当地剥离函数

当函数里的代码过多，或者可以复用的时候，需要把函数剥离出来，让其可读性更强。

match(pattern, text) {
  if (pattern === "") {
    return true;
  } else if (pattern === "$" && text === "") {
    return true;
  } else if (pattern[1] === "?") {
    return this.matchQuestion(pattern, text);
  } else if (pattern[1] === "*") {
    return this.matchStar(pattern, text);
  } else {
    return (
      this.matchOne(pattern[0], text[0]) && this.match(pattern.slice(1), text.slice(1))
    );
  }
}

详细的我们可以直接阅读代码了解 （阅读原文） 。

相关推荐

设计模式

超用户预期？AR+多屏协同的技术与体验

shadow的实验记录

shadow的实验记录 ，主要记录一些 智能产品架构相关的知识跟经验 ，比如智能设计、智能写作、短视频技术、代码上的设计模式，一些前沿的产品， 人工智能技术的实践经验，人机交互设计的思考 ， 商业化的思考 ； 全栈开发技术、设计方法论 ； 还有在做的一些 实验、workshop ，提供 答疑、咨询 。

欢迎跟我交流