作者：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：
-
=C1+C2*C3 =C1*C2+C3 * +
-
字符串里面有运算符，例如
=C1+C2+"=C1+C2"。 -
运算有左右括号匹配来改变运算优先级，例如
=(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 %}
在介绍每一个产生式之前，我们先介绍两个概念：
-
符号 ：它代表代码某一部分，例如 if 语句
if (...) { ... }整一块可以看做是一个符号，字符串"123"可以看做是一个符号，符号是一个递归的概念，符号可以包含其他符号。例如if (...) { a = "123" }这个 "if" 符号包含了字符串符号"123"。 -
终结符 ：当一个符号不包含其他符号了，那么它就是终结符。例如字符串符号
"123"中的1这是个终结符，因为它不能细分其它符号了。
具体到每一条产生式，可分三个部分：
-
->的左边是非终结符符号，它代表父级的概念，它可以包含多个符号或者终结符。 -
->右边内容是左边符号的展开表达式，它代表符号能够如何被展开，它可以包含多个符号或终结符。 -
最后部分是 Nearley 的 Post Processor，它会在应用完这条产生式后执行，它也是一段 JS 代码，它可以使用我们之前定义的 Helper 变量和函数。它的运行结果将会作为整条产生式的运行结果。
至此如何书写 BNF 就介绍完了，你可以已经发现了，正则表达式也可以用 BNF 来表示，事实上正则也是上下文无关的问题，自然也就可以用 BNF 来表示。
2. 生成 Parser
生成 Parser 会用到我们之前介绍到的 Nearley 框架，首先我们将上面给出的 BNF 语法定义保存到 grammar.ne 文件里。
-
我们先运行
npm install --save nearley来为项目安装 Nearley 依赖，然后运行npm install -g nearley来安装 Nearley 相关命令的全局依赖。 -
运行
nearleyc grammar.ne -o grammar.js生成 Parser 相关文件grammar.js。 -
运行下面的代码即可对 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 树进行从底往上地求值，整个过程是对树进行深度遍历完成的。
求值之前，我们先对数的非叶子节点定义一些原子操作：
-
Identifier: 在 Excel 中拿到对应的行列将其作为Identifier节点的值返回。 -
Expression Expression * Expression
-
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 可以在这里查看：
另外一个例子
为了加深理解，这里给出另外一个需求，将 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 或者流程图类似的方案来表示逻辑其实体验都不是很好，同时这些系统对使用者的素质要求不亚于要求他们直接写代码。
另外微信支付行业缴费、微信支付支付分行业招聘前端和后台工程师，在这里你可以：
-
接触到国民民生级应用产品，海量的业务挑战与海量的满足感。
-
接触到优秀的、不同专长的同事，以火箭般的速度成长。
-
丰富的个人发展空间。
是不是心动了，赶快点击下列链接了解详情吧：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 阿里架构师手写Tomcat——Session源码解析
- 手写call、apply、bind及相关面试题解析
- 手写一个webpack插件
- 从头手写一个Promise
- 前端面试之手写代码
- 手写简易IOC容器
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
