手写一个解析器

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

前言

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

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

点击播放视频

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

正则及其限制

在日常工作中，经常会遇到模式匹配的问题，例如你能需要从 0755-8771032 这样的电话号码格式中提取出区号和区号和电话号码，然后保存下来；可能需要判断 [email protected] 这样的邮箱地址是否合法；又可能你需要实现类似于 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-微信支付分行业后台开发工程师（深圳）