如何构造一个正则表达式解析引擎？

基于LR自底向上语法分析构建正则表达式解析引擎

开篇

本篇文章将介绍如何通过NFA(不确定有穷自动机)与自底向上语法分析去构造一个简单的正则表达式解析引擎。 这里我们会先简单描述一下文章后面会用到的一些技术用语，以便更好的理解文章。

什么是NFA(不确定有穷自动机)？

有穷自动机是识别器的一种，他们只能对每个简单的输入回答“是”或“否”，自动机是一种有向图结构， 他们有且离开该状态、以该符合为标号仅有一条边。一个不确定的有穷自动机包括至少下面几个部分：

  • 有穷的状态集合S

  • 一个输入集合集合∈

  • 状态转换函数fn，以及起始状态α0

有穷自动机从起始状态开始经过N次判断转换必定会达到终点。

语法分析器

一个简单的语法分析器包括下面几个部分：

  • 语法定义 对于语法定义而言首先需要确定的是文法，何为文法，文法是一个符号集合, 他是一个分析器所需要的最为基本的全部符号。 在这个正则表达式解析器中，他们是TESQF()|\.*，这也是最为简单的正则表达式引擎所需的基本符号。 在得到了基本的文法词汇之后，我们开始对文法进行推导，构建语法分析树🌲，确定语法的二义性和优先级。

  • 语法制导翻译 当我们拥有了语法的定义之后，我们如何对输入的正则表达式，例如：\d+将其转换成上述定义的语法。 这便是语法制导翻译负责的事情了，首先我们需要确定表达式expr，也就是如何将字符串转换成文法。例如：

    expr -> expr1 + term

翻译 expr1;
翻译 term；
处理 +;

    然后对之前得到的语法分析树🌲进行前序遍历，得到语法表达式集合，从而完成语法的制导翻译。

  • 语法分析 语法分析是对字符串\d+进行文法分析并判断其何时该进入语法翻译、何时该结束的过程。而这也是我们整个解析器的实际代码的开始。

    例如：

void stmt() {
  switch (lookahead) {
    case expr:
      match(expr);
      match(';');
      break;
    case if:
      match(if);
      match('(');
      match('expr');
      match(')');
      stmt();
      break;
    case for:
      match(for);
      match('(');
      opterpr();
      match(')');
      opterpr();
      stmt();  
  }
}

    此时我们便会结合之前已经构建好的有穷自动机与语法分析树，对语法进行自顶向下的分析， 执行语法制导翻译，从而完成对于整个字符的解析。

正篇：Regex-Resolver

在简单介绍了一些基本的技术用语之后，我们正式开始了构建基于NFA(不确定有穷自动机)与自底向上语法分析构造的正则表达式解析器。

Regex-Resolver流程构造剖析:

基本原理

首先将正则表达式理解为由某些字符串所组成的一种语言的集合, 进而对字符串的组成进行分析, 将其分割成基本的字符串、连接、或、乘积这几种基本的运算组合。 从而得到对于正则表达式本质的基本理解(即由某些特定的字符串及其通过连接、或、幂运算所构成的语言集的集合)。

正则表达式的NFA(不确定有穷自动机)

在继上面所得到的对于正则表达式的基本理解之后, 我们发现对于正则表达式的验证流程即从左至右依次验证的流程。 于是我们便可将其视作为一种状态转换的流程，由此我们便可将上面所述的基本运算将其转换为NFA自动机的构建。

对于每一个基本符号(a)构建如下图的自动机:

然后对于字符的连接、或、幂运算分别构造如下图所示的自动机(手动绘图, 有所粗糙见谅):

由此得到了基本的NFA自动机的模型。

自底向上的语法分析

首先根据上面的NFA自动机，我们得到了正则表达式的自动机模型，在验证之后确认此自动机可以被用来对于正则表达式的验证。 由此我们剩下的便是对于正则表达式的语法进行解析，何时根据正则表达式的内容构建上面所述的NFA自动机模型。 首先对于此正则表达式我们定义其可支持的数据类型以及操作如下:

数据类型:

  • . : 匹配任意一个非换行符符号

  • \d: 匹配0~9的数字

  • \t: 匹配制表符

  • \s: 匹配一个空白字符，包括空格、制表符、换页符和换行符

  • \w: 匹配一个单字字符（字母、数字或者下划线）等价于[A-Za-z0-9_]

运算类型:

  • (a): 创建一个子正则表达式a

  • a* : 匹配多次或零次

  • a? : 匹配一次或零次

  • a|b: 匹配a或者b

由此我们便可设计一个增强文法Q如下来代表此正则表达式规则的语法:

正则表达式文法:

  • Q -> S 对文法S的增强文法

  • S -> S or T | T (用字母or替代|避免与文法分隔符"|"冲突)

  • T -> TE | E

  • E -> E* | E? | F

  • F -> id | (S)

由此我们便可同样将自底向上的文法的匹配转换成自动机状态的转换, 从而构造出如下图所示的DFA(确定有穷自动机)语法分析表:

词法转换与语法制导翻译:

最后将正则表达式符号串先转换成词法单元队列，再依照语法分析自动机对正则表达式进行移入-归约的匹配,便可完成语法的匹配。 从而依照语法制导翻译构建最开始所述的正则NFA自动机, 便可完成整个正则表达式自动机的构建。

总结:

关于正则表达式解析器，一路走来，遇过诸多迷惘。幸得坚持，终得以拨开云雾见青天。 无论是正则自动机还是语法、文法的分析匹配等都让我受益良多，感触颇深。

完整项目地址：https://github.com/Panda-Hope/Regex-Resolver

Previous正则表达式解析引擎构造之路Next正则表达式引擎详解

Last updated