从零开始的正则解析器-05-极简parser

make the galaxy great again!

前情提要：
从零开始的正则解析器-01-从子字符串查找开始
 从零开始的正则解析器-02-从正则到ε-NFA
从零开始的正则解析器-03-一个ε-NFA实例
 从零开始的正则解析器-04-ε-NFA->NFA

用正则识别正则？

正则常常被我们用来识别邮箱地址，电话号码，网址是否合法。那有没有这的一个正则表达式，它能否识别正则表达式是否合法，听起来有点绕。可能规范化的描述是这样的

记全体合法正则表达式构成的集合为 R ,是否一个这样的正则表达式 r_o∈R ,使得对于任一的合法正则表达式 ∀r∈R ， ro.match(r) 的结果均为为真。否则为否。

这能做到吗，遗憾的是不能。不能的原因是正则没法做到递归，仅采用正则的话我们连简单的有效括号识别都无法做到（ leetcode 第20题），更不用说识别合法的正则表示式了。注意这道leetcode 题，标准的解法是采用栈这种数据结构，采用栈和正则，我们解出了这道题。而我们知道 递归实际上就是采用栈实现的 ，也就是说，如果我们有一种能实现递归的正则语言，那我们就可以解决这道leetcode题，也可以实现识别合法的正则表达式。

递归+正则=BNF

幸运的是，存在这样的语言（当然存在了，不然正则引擎怎么做的），称为BNF语言。BNF与正则语法大致出现在同一时期（20世纪50年代），也正好是计算理论飞速发展的年代。BNF语言的表述能力是乔姆斯基范式中的2型文法（上下文无关法）。这是一种很重要的文法规则，因为几乎所有编程语言的语法都可由BNF描述。

BNF的基本符号有：

::= ：等效于，例如 <exp1> ::= <exp2> ，即代表所有出现 exp1 的地方都可以替换为 exp2 。也用写成 -> 的。
< > ： < > 内包含的为必选项。某些写法里省去了。
: 串联选项，用在 ::= 右边，表示表达式串联
| ：并列选项，只能选一个
{ } ： { } 内包含项可重复0次或者无数次,也有写成 * 的

此外还有一些拓展语法，例如表示可重复0次或1次的 [] ( ? )，基本上和正则很像。那递归表现在哪里呢，以一个具体例子作说明

这是一个描述带括号的四则运算的BNF例子

exp -> exp opt exp| "(" exp ")"| number
opt -> + | - | * | /
number -> singlenum | number singlenum
singlenum -> 0|1|2|3|4|5|6|7|8|9

ps：这个例子里没有考虑到*和/算符应该优先于+和-

以上的每一行都是一个BNF产生式，四个产生式组成了一BNF组。

在这个BNF中，仅出现在 ::= 右边的符号称为 终结符 ，也可以称为该BNF的最小单元，在这个例子中终结符是 +,-,*,/ 这四个算符, () 括号和 0-9 数组，这也是符合直觉的。

其他符号称为 非终结符 ，每个产生式的左边都仅有一个非终结符。并且非终结符经过不断的替换，最终总可以被替换为终结符的组合。

递归在BNF中则表现为，每一条语法规则都可以调用，而非终结符可以出现在 ::= 左边或者右边，这意味着可以不断将左边非终结符的用右边替换解构，这一过程便是递归。

下面看一下正则语法的BNF表示

exp -> term | term "|" exp      ;// "|" 并联 或规则
term -> factor | factor term    ;// 串联 与规则
factor -> atom | atom "*"       ;// "*" 重复 可重规则
atom -> char | "(" exp ")"      ;// ()的优先级最高
char -> a|b|c|d....

这里很巧妙地解决了算符优先级的问题，因为按照正则语法， * 优先于串联，串联优先于 | 。按照上面的BNF解析时，我们会优先解析 | ，再解析串联，再解析 * ，再解析 () 。

这样说有点绕，为什么先解析的优先级反倒低，以1+2/3为例，如果优先解析+号，则式子被切割成了1 | + | 2/3，这样能保证2/3是在一起的。

速览AST树

BNF可以让我们拆解一个2型文法的字符串，但拆出来的结构是什么样的？例如对于 1+2 ，按照四则运算的BNF识别，得到的结构应该如下

exp(1+2) -> exp(1) op(+) exp(2)
exp(1) -> num(1) ->singlenum(1)
exp(2) -> num(2) ->singlenum(2)

抽象画一下应该是这样的

exp(1+2)
   /     |    \
exp(1) opt(+) exp(1)
num(1)        num(2)
singlenum(1)  singlenum(1)

经过BNF规则解析后表达式拆成了一种树形结构，同时我们可以看到一个有意思的现象，树的叶子节点（没有子节点的终端节点）都是终结符，非终结符则充当了非终端节点。形如这样的按照BNF规则对字符串进行解构生成的树便是AST树，也叫做抽象语法树。

由字符串经一定的BNF规则解析成AST的这一步骤一般称为编译过程的前端，由AST到机器码的过程称为编译过程的后端
一个BNF解析规则应当保证，由某一特定字符串生成的AST是固定不变的。上述四则运算的BNF并未做到这一点，因为其未规定算符优先级

自顶向下解析

有递归的地方就有递归的终止条件，BNF的终止条件便是所有的非终止符全被替换为终止符。当然事情没这么简单，可能在某些情况下，我们递归结束不了。

思考如下BNF

A -> Ab|a

其含义是匹配以 a 开头，之后有0至无数个 b 的字符串，但是程序没这么智能，在每一个 | 出现的地方，它都要作分支判断，那它可能就 Ab->Abb->Abbb->Abbbb->Abbbbb->Abbbbbb->... 一直循环下去了，这显然不是我们希望看到的，要避免这样，我们可以把BNF改造成如下形式：

A -> a|aB
B -> bB|ε

ε 代表空字符串。改写后的语法避免了无穷分支，它主要是避免了非终结符出现在 ::= 右边的第一个位置，在消除了左递归（即刚才出现的无穷分支）和二义性（即算符优先级未确定）后的BNF集合，我们称为 LL(1) 文法，如果要手写一个语法分析器，那我们最好保证我们要手写的语法规则是LL(1)的。

与之对应的，有很多由程序完成语法分析的手段，可以直接由BNF产生parser程序，最出名的便是 yacc

回顾一下上述正则的BNF，其规则实际上是LL(1)的，如果不是我们需要先改写BNF使其称为LL(1)文法才能进行下一步手写parser。

语法分析器的前一步应该是词法分析，也就是tokenizer，负责将parser能识别的最小单元拆出来，不过，我们这使用的正则规则非常简单，最小单元都是单个字符，故可以省去tokenizer。

下面开始构造解析程序：

定义AST的节点

class ASTNode {
    id: number = 0;
    label: string;
    child: ASTNode[];
    constructor(label = "", child: ASTNode[] = []) {
    this.label = label;
    this.child = child;

AST节点的定义很简单，就是一个常规的树节点

2. 辅助函数

let pos = 0;
// 返回当前token
const current = () => str[pos];
// 是否到达了终点
const isEnd = () => pos >= str.length;
// 返回当前的token并前进一步
const next = ()=>{
    let ch = current();
    pos++;
    return ch;
// match(ch)的含义是下一个token应当是ch，如果不是则报错退出，如果是前进一步
const match = (ch: string) => {
    if (current() !== ch) {
    throw new Error(`Unexpected symbol ${ch} at position:${pos}`);
    pos++;

这些辅助函数的功能都比较简单，不用作太多介绍

3. 匹配函数

先从最简单的开始，匹配识别 char

function char() {
    // "*"不能单独使用
    if (current() == "*"){
        throw new Error(`Unexpected "*" char at position:${pos}`);
    // 返回一个新的ASTNode，ASTNode的子节点仅有一个，即该一般字符，并且pos步进一步
    return new ASTNode("Char", [new ASTNode(next())]);

依葫芦画瓢，写出 atom 的匹配函数。在这里我们需要判断一下，如果当前是 "(" 则是 atom -> "(" exp ")" 这种情况，否则是一般字符，是 atom -> Char 这种情况。这也是LL(1)的含义，只需要一个token即可判断对应的文法。

function atom() {
//atom 开头必为普通字符串或者"("，若为"("，则
    if (current() === "(") {
        match("(");
        const exp = expr();
        match(")");
        return new ASTNode("Atom", [new ASTNode("("), exp, new ASTNode(")")]);
    const ch = char();
    return new ASTNode("Atom", [ch]);

匹配 factor 类似，判断是 atom 还是 atom "*" 也十分简单，直接判断是否有 "*" 即可

function factor() {
    const atm = atom();
    if (current() === "*") {
    let c = next();
    return new ASTNode("Factor", [atm, new ASTNode(c)]);
    return new ASTNode("Factor", [atm]);

之后是 term ，和上面的思路一样.只是我们考虑的不是等于，而是不等于，只要不以 "|" 或者 ")" 开头，就能解析成下一个 term 。因此不以 "|",")" 开头时为 term -> factor term ，否则为 term -> factor term

function term(): ASTNode {
    const factr = factor();
    // term 开头不可能是"|"或者")"
    if (!isEnd() && current() !== "|" && current() !== ")") {
    const trm = term();
    return new ASTNode("Term", [factr, trm]);
    return new ASTNode("Term", [factr]);

最后是 expr ，同样的思路

function expr(): ASTNode {
    const trm = term();
    if (!isEnd() && current() === "|") {
    match("|");
    const exp = expr();
    return new ASTNode("Expr", [trm, new ASTNode("|"), exp]);
    return new ASTNode("Expr", [trm]);
最后包装一下，调用函数
function strtoAST(str:string ){
    let pos = 0;
    // 返回当前token
    const current = () => str[pos];
    const isEnd = () => pos >= str.length;
    function next(){};
    function match(){};
    function char();
    function atom();
    function factor();
    function term();
    function expr();
    return expr()

小结一下，至此AST解析程序就基本写完了，我们实现了一个由正则表达式字符串到AST语法树的程序，由于正则表达式的语法是2型文法，因此我们将正则的规则写成了BNF形式，并依照该BNF完成了语法树解析程序。

AST到eNFA

得到AST并不是我们的目标，实际上我们想做的是由字符串到eNFA(NFA)，因此最后一步是由AST到eNFA。

回顾一下之前我们手动构造eNFA的过程，比如 ab ，我们的做法是 concatE_NFA(creatE_NFA("a"),(creatE_NFA("b")) ，而 ab 在ast中的表示方式大致 (实际套娃层数很多)是 {label:"Term";child:[{"a"},{"b}]} 而我们要做的是识别到 Term , "a" , "b" 这几个信息后调用 concatE_NFA(creatE_NFA("a"),(creatE_NFA("b")) ，所以这是一个后序遍历的算法，扫描了某一个AST节点和其所有子节点后再操作。

AST是树的结构，因此又回到了我们熟悉的遍历树算法环节，这里我们采取的是后续遍历，采用递归实现。代码如下，逻辑十分清晰

function ASTtoENFA(ast: ASTNode): E_NFA {
        switch (ast.label) {
            case "Expr":
                if (ast.child.length === 3) {
                    // 此时为 trem "|" "exp"
                    return BuildE_NFA.unionE_NFA(
                    ASTtoENFA(ast.child[0]),
                    ASTtoENFA(ast.child[2])
                } else {
                    return ASTtoENFA(ast.child[0]);
            case "Term":
                if (ast.child.length === 2) {
                    // 此时为 factor trem
                    return BuildE_NFA.concatE_NFA(
                    ASTtoENFA(ast.child[0]),
                    ASTtoENFA(ast.child[1])
                } else {
                    return ASTtoENFA(ast.child[0]);
            case "Factor":
                if (ast.child.length === 2) {
                    // 此时为 factor "*"
                    return BuildE_NFA.closureE_NFA(ASTtoENFA(ast.child[0]));
                } else {
                    return ASTtoENFA(ast.child[0]);
            case "Atom":
                if (ast.child.length === 3) {
                    // 此时为 "(" exp ")"
                    return ASTtoENFA(ast.child[1]);
                } else {
                    return ASTtoENFA(ast.child[0]);
            case "Char":
                return BuildE_NFA.creatE_NFA(ast.child[0].label);
            default:
                throw new Error("Ast to enfa error");

这里就可以看出为什么我们要先将表达式字符串转化为AST，再由AST到eNFA了，AST的层次结构很方便我们进行后续处理，许多优化也是在AST上完成的，这里我们不作任何优化，直接将AST转化为eNFA。

由AST到目标代码（一般是机器码）的步骤称为编译的后端，后端里最常用的工具为 LLVM

最终实现

最后我们回顾一下我们为了实现正则到底做了什么，我们 1. 引入了自动机概念 2. 将正则表达式和eNFA自动机对应起来 3. 实现了由eNFA到NFA的化简和NFA的运行模拟 4. 构建了正则语法对应的BNF，实现了由正则表达式到AST 5. 实现了由AST到eNFA的转化

接下来做一下排序题，如果由一个正则表达式 pat 和待识别字符串 str ，我们的步骤应该是：

由 pat 构建AST
AST转化为eNFA
eNFA转化为NFA
NFA识别 str

写出代码形式如下：

function match(pat: string, str: string) {
  let ast = strtoAST(pat);
  let enfa = ASTtoENFA(ast);