手写一个解析器

作者：jolamjiang，腾讯 WXG 前端开发工程师

前言

最近工作中有一些同学在做一些效能 工具 的时候遇到需要写一门领域相关语言（DSL）及其解析器的场景，笔者恰好有相关的经验向大家指一下北。

首先请问一下大家有没有想过这个功能怎么做？

点击播放视频

本文将围绕如何实现类似于 Excel 中 =C1+C2+"123" 这样子的表达式的功能这一例子，在不需要编译原理的相关知识的前提下，用写正则表达式作为类比，借助一个工具库，讲述实现一个领域相关语言的解析器的一般步骤，让你能够快速实现一个解析器。同时，文章最后将给出一个将类似 MySQL 里面 Where 表达式转化成 MongoDB 查询的例子丰富这里的应用。

正则及其限制

在日常工作中，经常会遇到模式匹配的问题，例如你能需要从 0755-8771032 这样的电话号码格式中提取出区号和区号和电话号码，然后保存下来；可能需要判断 test@domain.com.cn 这样的邮箱地址是否合法；又可能你需要实现类似于 Excel 里面表达的功能，例如用户输入 =C1+C2+"123" ，你需要把 C1 的内容和 C2 的内容和字符串 "123" 拼接起来。

我们一般的做法是使用正则表达来做这个事情，以 Python 为例，系统提供的 API 我们可以看做分三步走：

import re
pattern = "^([0-9])-([0-9]+)$" // 1. write regex string of phone number
prog = re.compile(pattern) // 2. compile regex to a matcher
result = prog.match(string) // 3. match string and handle results

目前为止正则表达式都看起来都没问题，以 =C1+C2+"123" 这个需求为例，你可能会觉得我们按照运算符（ + 、 - 、 * 等）分割一下然后再计算就行了，但是考虑下面三个 case：

1. =C1+C2*C3
   =C1*C2+C3
   *
   +
   

2. 字符串里面有运算符，例如 =C1+C2+"=C1+C2" 。
3. 运算有左右括号匹配来改变运算优先级，例如 =(C1+C2)*C3

这个时候光使用正则表达式就比较棘手了。

通用做法

业界通用的做法是先定义这个领域相关的语法，将这个语法形式化描述（就像写正则表达式），然后根据这语法实现一个 Parser 将代码转成抽象语法树（AST），再解析和运行这颗抽象语法树。

上述整个过程听起来就比较复杂，事实上要从 0 开始实现一个 Parser 还是比较费时的，那么有没有工具能够让我们可以像写正则一样生成我们的 Parser，进而产生一颗抽象语法树方便我们处理呢？答案是有的，例如 C 语言有 Bison 框架，JS 上选择就更多了，你可以选择 Jison 、 parsimmon 、 PEG.js 、 Nearley 等，本文则基于使用人数较多的 Nearley 框架。

如何写一个解析器

与使用写正则类似，使用 Nearley 等 Parser 产生器的过程，也是分三步走。

1. 用 BNF 来表示你的 DSL 语法

BNF 的全称是 Backus–Naur form，是一种表示上下文无关语法的表示方式，Nearley 的语法基于 BNF 的扩展 EBNF(Extended Backus–Naur form)，下面是笔者写的关于这个 Excel 中的表达式的 Nearley 语法文件（为了便于理解，这里只实现了运算符的优先级，没有实现左右括号）：

grammar.ne

@builtin "number.ne"
@builtin "whitespace.ne"
@builtin "string.ne"

@{%
    function buildAssignmentExpression(d) {
        return {
            type: "AssignmentExpression",
            op: d[2],
            left: d[0],
            right: d[4]
        };
    }
%}

# Assignment
Exp -> Assignment {% id %}
    | Value {% id %}


Assignment -> "=" _ Expression {% d => {
    return {
        type: "Assignment",
        value: d[2]
    }
} %}

# Expression
Expression -> AddSubExpression {% id %}

# Expression for Add Sub
AddSubExpression -> AddSubExpression _ "+" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | AddSubExpression _ "-" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | MulDivExpression {% id %}

# Expression for Mul Div
MulDivExpression -> Identifier _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | Identifier _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}

    | Value _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | Value _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    
    | Value {% id %}
    | Identifier {% id %}

# Cell Identifier
Identifier -> [A-Z]:+ [0-9]:+ {%
        function(d) {
            return {
                'type': "AssignmentIdentifier",
                'column': d[0].join(""),
                'line': d[1].join("")
            }
        }
    %}

# Values
Value -> _value {%
        function(d) {
            return {
                'type': "Value",
                'value': d[0]
            };
        }
    %}

_value -> int {% id %}
    | unsigned_decimal {% id %}
    | decimal {% id %}
    | dqstring {% id %}
    | sqstring {% id %}
    | btstring {% id %}

1.1 引入语法模块

我们一步步来分析这个文件的内容，首先是头部这段代码：

@builtin "number.ne"
@builtin "whitespace.ne"
@builtin "string.ne"

Nearley 预定义了一些常用的语法，这段代码的意思是引入了 Nearley 预定义的数字语法，空格语法和字符串语法。引入完了之后，生成的 Parser 就可以识别例如 "123" 这样的字符串、 123 这样的数字。

Nearley 内置的语法模块可以在 这里 查看。

1.2 Helper 变量和函数

接着是这段代码：

@{%
    function buildExpression(d) {
        return {
            type: "Expression",
            op: d[2],
            left: d[0],
            right: d[4]
        };
    }
%}

在 Nearley 里面， {% raw %}@{% ... %}{% endraw %} 里面的内容相当于在全局声明了一些变量，这些变量可以在产生式的 Post Processor 里用到。至于什么叫产生式紧接接下来会介绍到。

1.3 书写产生式

我们拿其中一个比较复杂的产生式来讲解一下：

MulDivExpression -> Identifier _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | Identifier _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}

    | Value _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    | Value _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
    
    | Value {% id %}
    | Identifier {% id %}

Nearley 里面 | 这个运算符其实是个语法糖，上面的产生式其实可以表示成多条产生式：

MulDivExpression -> Identifier _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
MulDivExpression -> Identifier _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
MulDivExpression -> Value _ "*" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
MulDivExpression -> Value _ "/" _ MulDivExpression {% d => buildAssignmentExpression(d) %}
MulDivExpression -> Value {% id %}
MulDivExpression -> Identifier {% id %}

在介绍每一个产生式之前，我们先介绍两个概念：

1. 符号 ：它代表代码某一部分，例如 if 语句 if (...) { ... } 整一块可以看做是一个符号，字符串 "123" 可以看做是一个符号，符号是一个递归的概念，符号可以包含其他符号。例如 if (...) { a = "123" } 这个 "if" 符号包含了字符串符号 "123" 。
2. 终结符 ：当一个符号不包含其他符号了，那么它就是终结符。例如字符串符号 "123" 中的 1 这是个终结符，因为它不能细分其它符号了。

具体到每一条产生式，可分三个部分：

1. -> 的左边是非终结符符号，它代表父级的概念，它可以包含多个符号或者终结符。
2. -> 右边内容是左边符号的展开表达式，它代表符号能够如何被展开，它可以包含多个符号或终结符。

3. 最后部分是 Nearley 的 Post Processor，它会在应用完这条产生式后执行，它也是一段 JS 代码，它可以使用我们之前定义的 Helper 变量和函数。它的运行结果将会作为整条产生式的运行结果。

至此如何书写 BNF 就介绍完了，你可以已经发现了，正则表达式也可以用 BNF 来表示，事实上正则也是上下文无关的问题，自然也就可以用 BNF 来表示。

2. 生成 Parser

生成 Parser 会用到我们之前介绍到的 Nearley 框架，首先我们将上面给出的 BNF 语法定义保存到 grammar.ne 文件里。

1. 我们先运行 npm install --save nearley 来为项目安装 Nearley 依赖，然后运行 npm install -g nearley 来安装 Nearley 相关命令的全局依赖。
2. 运行 nearleyc grammar.ne -o grammar.js 生成 Parser 相关文件 grammar.js 。

3. 运行下面的代码即可对 DSL 代码进行解析了：

const nearley = require("nearley");
const grammar = require("./grammar.js");

// Create a Parser object from our grammar.
const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar));

// Parse something!
parser.feed("=C1+C2*C3");

// parser.results is an array of possible parsings.
console.log(parser.results);

3. 解析 Parser 结果

步骤 2 完成了之后，我们就可以得到 DSL 代码对应的抽象语法树，所谓的抽象语法树其实就是一个 JSON 对象，例如 =C1+D1*E1 这个代码对应的 JSON 对象的结构就如下图所示

那么下一步就是怎么解析这个树状结构的对象，然后得到它对应的结果。这里我们用最简单的 自循环解析器 来对这棵树进行求值。自循环解析器的原理很简单，我们将得到的 AST 树进行从底往上地求值，整个过程是对树进行深度遍历完成的。

求值之前，我们先对数的非叶子节点定义一些原子操作：

1. Identifier : 在 Excel 中拿到对应的行列将其作为 Identifier 节点的值返回。

2. Expression
   Expression
   *
   Expression
   

3. Assignment
   Assignment
   Expression
   

有了上述原子操作之后，就可以开始我们的求值了，最开始深度遍历到 D1 和 E1 对应的 Identifier 之后，我们根据上述的原子操作对 Identifier 的值进行替换，假设 D1 和 E1 对应的值分别是 11 和 12 ，则第一次递归求值后，树就变成了：

下一层的递归则对第二层的 Identifier 和 Expression 节点进行求值，根据上述的原子操作，假设 C1 对应的值是 33 ，树就变成了：

以此类推，我们就可以得到这棵树的最终值 33 + 132 = 165 。

下面给出实现递归的代码和对应的 AST，对于某些同学来说，可能直接看代码更容易理解：

ast.json

{
  "type": "Assignment",
  "value": {
    "type": "AssignmentExpression",
    "op": "+",
    "left": {
      "type": "AssignmentIdentifier",
      "column": "C",
      "line": "1"
    },
    "right": {
      "type": "AssignmentExpression",
      "op": "*",
      "left": {
        "type": "AssignmentIdentifier",
        "column": "D",
        "line": "1"
      },
      "right": {
        "type": "AssignmentIdentifier",
        "column": "E",
        "line": "1"
      }
    }
  }
}

eval.js

function evalAst(exp, rows) {
  if (exp.type == "Assignment") {
    return evalAst(exp.value, rows);
  }
  if (exp.type == "Value") {
    return exp.value;
  }
  if (exp.type == "AssignmentIdentifier") {
    return rows[exp.line][exp.column];
  }
  if (exp.type == "AssignmentExpression") {
    switch(exp.op) {
      case "+":
        return evalAst(exp.left, rows) + evalAst(exp.right, rows);
      case "-":
        return evalAst(exp.left, rows) - evalAst(exp.right, rows);
      case "*":
        return evalAst(exp.left, rows) * evalAst(exp.right, rows);
      case "/":
        return evalAst(exp.left, rows) / evalAst(exp.right, rows);
      default:
        throw new Error("invalid operator");
        break;
    }
  }
  throw new Error("invalid expression type");
}

最后 DEMO 可以在这里查看：

1. 代码： https://stackblitz.com/edit/react-excel-example

2. DEMO： https://react-excel-example.stackblitz.io/

另外一个例子

为了加深理解，这里给出另外一个需求，将 MySQL 类似于 where 转换成云函数里面的 where 筛选的需求，给出 BNF 语法和 Eval JS 代码：

grammar.ne

@builtin "number.ne"
@builtin "whitespace.ne"
@builtin "string.ne"

@{%
    function buildExpression(d) {
        return {
            type: "Expression",
            op: d[2],
            left: d[0],
            right: d[4]
        };
    }
%}

# exp
Exp -> Binop {% id %}

Binop -> ExpOr {% id %}

ExpOr -> ExpOr __ "or" __ ExpAnd {% d => buildExpression(d) %}
  | ExpAnd {% id %}

ExpAnd -> ExpAnd __ "and" __ ExpComparison {% d => buildExpression(d) %}
  | ExpComparison {% id %}

ExpComparison ->
    Name _ "<"  _ Value {% d => buildExpression(d) %}
  | Name _ ">"  _ Value {% d => buildExpression(d) %}
  | Name _ "<=" _ Value {% d => buildExpression(d) %}
  | Name _ ">=" _ Value {% d => buildExpression(d) %}
  | Name _ "~=" _ Value {% d => buildExpression(d) %}
  | Name _ "==" _ Value {% d => buildExpression(d) %}

# variables
Name -> _name {%
    function(d) {
      return {
        'type': "Identifier",
        'name': d[0]
      };
    }
  %}

_name -> [a-zA-Z_] {% id %}
  | _name [\w_] {% function(d) {return d[0] + d[1]; } %}

# values
Value -> _value {%
    function(d) {
      return {
        'type': "Value",
        'value': d[0]
      };
    }
  %}

_value -> int {% id %}
  | unsigned_decimal {% id %}
  | decimal {% id %}
  | dqstring {% id %}
  | sqstring {% id %}
  | btstring {% id %}

eval.ts

type Expression = {
    type: "Expression",
    op: "or" | "and" | "<" | ">" | ">=" | "<=" | "~=" | "==",
    left: Expression | Identifier,
    right: Expression | Value
}

type Identifier = {
    type: "Identifier",
    name: string
}

type Value = {
    type: "Value",
    value: number | string
}

export default function __eval(ast: Expression, _: any) {

    function evalExpression(expression: Expression) {
        switch (expression.op) {
            case "or":
                return _.or([
                    evalExpression((expression as any).left),
                    evalExpression((expression as any).right),
                ]);
                break;
            case "and":
                return _.and([
                    evalExpression((expression as any).left),
                    evalExpression((expression as any).right),
                ]);
                break;
            case "<":
                return {
                    [(expression as any).left.name]: _.lt((expression as any).right.value)
                }
                break;
            case ">":
                return {
                    [(expression as any).left.name]: _.gt((expression as any).right.value)
                }
                break;
            case ">=":
                return {
                    [(expression as any).left.name]: _.gte((expression as any).right.value)
                }
                break;
            case "<=":
                return {
                    [(expression as any).left.name]: _.lte((expression as any).right.value)
                }
                break;
            case "~=":
                return {
                    [(expression as any).left.name]: _.neq((expression as any).right.value)
                }
                break;
            case "==":
                return {
                    [(expression as any).left.name]: _.eq((expression as any).right.value)
                }
                break;
            default:
                throw new Error("invalid expression");
                break;
        }
    }

    return evalExpression(ast)
}

总结

到此为止读者应该具备写自己的 DSL 和解析器的能力了，学会写自己的 DSL 和解析器其实还有别的好处，例如它可以让你更好地理解我们平常说的配置系统是什么，其实配置也是代码，试想 if (config(...)) { ... } else { ... } 中的 config(...) 其实就是你的配置系统需要承载的内容，又例如你要实现一拖拽生成 UI 的工具，其实你就是在用拖拽生成了一颗 AST 树，然后在你的产品里实现了一个解析 AST 的解析器来渲染结果。同时反过来，你可以思考你的配置系统可以实现一些什么样的能力，它的上限就是能达到与写代码一样的功能，不过笔者不推荐这么做，因为业界一些方案例如 Blockly 或者流程图类似的方案来表示逻辑其实体验都不是很好，同时这些系统对使用者的素质要求不亚于要求他们直接写代码。

另外微信支付行业缴费、微信支付支付分行业招聘前端和后台工程师，在这里你可以：

1. 接触到国民民生级应用产品，海量的业务挑战与海量的满足感。

2. 接触到优秀的、不同专长的同事，以火箭般的速度成长。

3. 丰富的个人发展空间。

是不是心动了，赶快点击下列链接了解详情吧：

1. 28601-微信支付行业缴费开发工程师（深圳）

2. 28601-微信支付分行业Web前端工程师

3. 28601-微信支付分行业后台开发工程师（深圳）