手寫一個解析器
摘要:業界通用的做法是先定義這個領域相關的語法,將這個語法形式化描述(就像寫正則表達式),然後根據這語法實現一個 Parser 將代碼轉成抽象語法樹(AST),再解析和運行這顆抽象語法樹。生成 Parser 會用到我們之前介紹到的 Nearley 框架,首先我們將上面給出的 BNF 語法定義保存到 grammar.ne 文件裏。
作者: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:
-
=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 或者流程圖類似的方案來表示邏輯其實體驗都不是很好,同時這些系統對使用者的素質要求不亞於要求他們直接寫代碼。
另外微信支付行業繳費、微信支付支付分行業招聘前端和後臺工程師,在這裏你可以:
-
接觸到國民民生級應用產品,海量的業務挑戰與海量的滿足感。
-
接觸到優秀的、不同專長的同事,以火箭般的速度成長。
-
豐富的個人發展空間。
是不是心動了,趕快點擊下列鏈接瞭解詳情吧: