建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「碼農(nóng)桃花源」，作者小X。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼農(nóng)桃花源公眾號(hào)。
成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),福綿企業(yè)網(wǎng)站建設(shè),福綿品牌網(wǎng)站建設(shè),網(wǎng)站定制,福綿網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,福綿網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
你好，我是小X。
曹大最近開(kāi) Go 課程了，小X 正在和曹大學(xué) Go。
這個(gè)系列會(huì)講一些從課程中學(xué)到的讓人醍醐灌頂?shù)臇|西，撥云見(jiàn)日，帶你重新認(rèn)識(shí) Go。
抽象語(yǔ)法樹(shù)是編譯過(guò)程中的一個(gè)中間產(chǎn)物，一般簡(jiǎn)單了解一下就行了。但我們可以把 Go 語(yǔ)言的整個(gè) parser 和 ast 包直接拿來(lái)用，在一些場(chǎng)景下有很大的威力。
什么是 ast 呢，我從維基百科上摘錄了一段：
在計(jì)算機(jī)科學(xué)中，抽象語(yǔ)法樹(shù)(Abstract Syntax Tree，AST)，或簡(jiǎn)稱語(yǔ)法樹(shù)(Syntax tree)，是源代碼語(yǔ)法結(jié)構(gòu)的一種抽象表示。它以樹(shù)狀的形式表現(xiàn)編程語(yǔ)言的語(yǔ)法結(jié)構(gòu)，樹(shù)上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。
核心就是說(shuō) ast 能以一種樹(shù)的形式表示代碼結(jié)構(gòu)。有了樹(shù)結(jié)構(gòu)，就可以對(duì)它做遍歷，能干很多事。
假定一個(gè)場(chǎng)景
假定一個(gè)場(chǎng)景：我們可以從司機(jī)平臺(tái)的某個(gè)接口獲取司機(jī)的各種特征，例如：年齡、訂單數(shù)、收入、每天駕駛時(shí)長(zhǎng)、駕齡、平均車速、被投訴次數(shù)……數(shù)據(jù)一般采用 json 來(lái)傳遞。
司機(jī)平臺(tái)的運(yùn)營(yíng)小姐姐經(jīng)常需要搞一些活動(dòng)，例如選出：
- 訂單數(shù)超過(guò) 10000，且駕齡超過(guò) 5 年的老司機(jī)
- 每天駕駛時(shí)小于 3 小時(shí)，且收入超過(guò) 500 的高效司機(jī)
- 年齡大于 40，且平均速度大于 70 的“狂野”司機(jī)
- ……
這些規(guī)則并不是固定的，經(jīng)常在變化，但總歸是各種司機(jī)特征的組合。
為了簡(jiǎn)化，我們選取 2 個(gè)特征，并用一個(gè) Driver 結(jié)構(gòu)體來(lái)表示：
- type Driver struct {
- Orders int
- DrivingYears int
- }
為了配合運(yùn)營(yíng)搞活動(dòng)，我們需要根據(jù)運(yùn)營(yíng)給的規(guī)則來(lái)判斷一個(gè)司機(jī)是否符合要求。
如果公司人多，可以安排一個(gè) rd 專門(mén)伺候運(yùn)營(yíng)小姐姐，每次做活動(dòng)都來(lái)手動(dòng)修改代碼，也不是不可以。并且其實(shí)挺簡(jiǎn)單，我們來(lái)寫(xiě)一個(gè)示例代碼：
- // 從第三方獲取司機(jī)特征，json 表示
- func getDriverRemote() []byte {
- return []byte(`{"orders":100000,"driving_years":18}`)
- }
- // 判斷是否為老司機(jī)
- func isOldDriver(d *Driver) bool {
- if d.Orders > 10000 && d.DrivingYears > 5 {
- return true
- }
- return false
- }
- func main() {
- bs := getDriverRemote()
- var d Driver
- json.Unmarshal(bs, &d)
- fmt.Println(isOldDriver(&d))
- }
直接來(lái)看 main 函數(shù)：getDriverRemote 模擬從第三方 RPC 獲取一個(gè)司機(jī)的特征數(shù)據(jù)，用 json 表示。接著 json.Unmarshal 來(lái)反序列化 Driver 結(jié)構(gòu)體。最后調(diào)用 isOldDriver 函數(shù)來(lái)判斷此司機(jī)是否符合運(yùn)營(yíng)的規(guī)則。
isOldDriver 根據(jù) Driver 結(jié)構(gòu)體的 2 個(gè)字段使用 if 語(yǔ)句來(lái)判斷此司機(jī)是否為老司機(jī)。
確實(shí)還挺簡(jiǎn)單。
但是每次更新規(guī)則還得經(jīng)過(guò)一次完整的上線流程，也挺麻煩的。有沒(méi)有更簡(jiǎn)單的辦法呢?使得我們可以直接解析運(yùn)營(yíng)小組姐給我們的一個(gè)用字符串表示的規(guī)則，并直接返回一個(gè) bool 型的值，表示是否滿足條件。
有的!
接下來(lái)就是本文的核心內(nèi)容，如何使用 ast 來(lái)完成同樣的功能。
直觀地理解如何用 ast 解析規(guī)則
使用 ast 包提供的一些函數(shù)，我們可以非常方便地將如下的規(guī)則字符串：
- orders > 10000 && driving_years > 5
解析成一棵這樣的二叉樹(shù)：
規(guī)則二叉樹(shù)
其中，ast.BinaryExpr 代表一個(gè)二元表達(dá)式，它由 X 和 Y 以及符號(hào) OP 三部分組成。最上面的一個(gè) BinaryExpr 表示規(guī)則的左半部分和右半部分相與。
很明顯，左半部分就是：orders > 10000，而右半部分則是：driving_years > 5。神奇的是，左半部分和右半部分恰好又都是一個(gè)二元表達(dá)式。
左半部分的 orders > 10000 其實(shí)也是最小的葉子節(jié)點(diǎn)，它可以算出來(lái)一個(gè) bool 值。把它拆開(kāi)來(lái)之后，又可以分成 X、Y、OP。X 是 orders，OP 是 ">"，Y 則是 "10000"。其中 X 表示一個(gè)標(biāo)識(shí)符，是 ast.Ident 類型，Y 表示一個(gè)基本類型的字面量，例如 int 型、字符串型……是 ast.BasicLit 類型。
右半部分的 driving_years > 18 也可以照此拆分。
然后，從 json 中取出這個(gè)司機(jī)的 orders 字段的值為 100000，它比 10000 大，所以左半部分算出來(lái)為 true。同理，右半部分算出來(lái)也為 true。最后，再算最外層的 "&&"，結(jié)果仍然為 true。
至此，直接根據(jù)規(guī)則字符串，我們就可以算出來(lái)結(jié)果。
如果寫(xiě)成程序的話，就是一個(gè) dfs 的遍歷過(guò)程。如果不是葉子結(jié)點(diǎn)，那就是二元表達(dá)式結(jié)點(diǎn)，那就一定有 X、Y、OP 部分。遞歸地遍歷 X，如果 X 是葉子結(jié)點(diǎn)，那就結(jié)束遞歸，并計(jì)算出 X 的值……
這里再展示一個(gè)用 ast 包打印出來(lái)的抽象語(yǔ)法樹(shù)：
Go 打印 ast
上圖中，1、2、3 表示最外層的二元表達(dá)式;4、5、6 則表示左邊這個(gè)二元表達(dá)式。
結(jié)合這張圖，再參考 ast 包的相關(guān)結(jié)構(gòu)體 代碼，就非常清晰了。例如 ast.BinaryExpr 的代碼如下：
- // A BinaryExpr node represents a binary expression.
- BinaryExpr struct {
- X Expr // left operand
- OpPos token.Pos // position of Op
- Op token.Token // operator
- Y Expr // right operand
- }
它有 X、Y、OP，甚至還解析出了 Op 的位置，用 OpPos 表示。
如果你還對(duì)實(shí)現(xiàn)感興趣，那就繼續(xù)看下面的原理分析部分，否則可以直接跳到結(jié)尾總結(jié)部分。
原理分析
還是用上面那個(gè)例子，我們直接寫(xiě)一個(gè)表達(dá)式：
- orders > 10000 && driving_years > 5
接下來(lái)用 ast 來(lái)解析規(guī)則并判斷真假。
- func main() {
- m := map[string]int64{"orders": 100000, "driving_years": 18}
- rule := `orders > 10000 && driving_years > 5`
- fmt.Println(Eval(m, rule))
- }
為了簡(jiǎn)單，我們直接用 map 來(lái)代替 json，道理是一樣的，僅僅為了方便。
Eval 函數(shù)判斷 rule 的真假：
- // Eval : 計(jì)算 expr 的值
- func Eval(m map[string]int64, expr string) (bool, error) {
- exprAst, err := parser.ParseExpr(expr)
- if err != nil {
- return false, err
- }
- // 打印 ast
- fset := token.NewFileSet()
- ast.Print(fset, exprAst)
- return judge(exprAst, m), nil
- }
先將表達(dá)式解析成 Expr，接著調(diào)用 judge 函數(shù)計(jì)算結(jié)果：
- // dfs
- func judge(bop ast.Node, m map[string]int64) bool {
- // 葉子結(jié)點(diǎn)
- if isLeaf(bop) {
- // 斷言成二元表達(dá)式
- expr := bop.(*ast.BinaryExpr)
- x := expr.X.(*ast.Ident) // 左邊
- y := expr.Y.(*ast.BasicLit) // 右邊
- // 如果是 ">" 符號(hào)
- if expr.Op == token.GTR {
- left := m[x.Name]
- right, _ := strconv.ParseInt(y.Value, 10, 64)
- return left > right
- }
- return false
- }
- // 不是葉子節(jié)點(diǎn)那么一定是 binary expression（我們目前只處理二元表達(dá)式）
- expr, ok := bop.(*ast.BinaryExpr)
- if !ok {
- println("this cannot be true")
- return false
- }
- // 遞歸地計(jì)算左節(jié)點(diǎn)和右節(jié)點(diǎn)的值
- switch expr.Op {
- case token.LAND:
- return judge(expr.X, m) && judge(expr.Y, m)
- case token.LOR:
- return judge(expr.X, m) || judge(expr.Y, m)
- }
- println("unsupported operator")
- return false
- }
judge 使用 dfs 遞歸地計(jì)算表達(dá)式的值。
遞歸地終止條件是葉子節(jié)點(diǎn)：
- // 判斷是否是葉子節(jié)點(diǎn)
- func isLeaf(bop ast.Node) bool {
- expr, ok := bop.(*ast.BinaryExpr)
- if !ok {
- return false
- }
- // 二元表達(dá)式的最小單位，左節(jié)點(diǎn)是標(biāo)識(shí)符，右節(jié)點(diǎn)是值
- _, okL := expr.X.(*ast.Ident)
- _, okR := expr.Y.(*ast.BasicLit)
- if okL && okR {
- return true
- }
- return false
- }
總結(jié)
今天這篇文章主要講了如何用 ast 包和 parser 包解析一個(gè)二元表達(dá)式，并見(jiàn)識(shí)到了它的威力，利用它可以做成一個(gè)非常簡(jiǎn)單的規(guī)則引擎。
其實(shí)利用 ast 包還可以做更多有意思的事情。例如批量把 thrift 文件轉(zhuǎn)化成 proto 文件、解析 sql 語(yǔ)句并做一些審計(jì)……
想要更深入的學(xué)習(xí)，可以看曹大這篇《golang 和 ast》[1]，據(jù)曹大自己說(shuō)，他可以在 30 分鐘內(nèi)完成一個(gè)項(xiàng)目的一個(gè) api 的編寫(xiě)，非常霸氣!不服噴他……
網(wǎng)頁(yè)標(biāo)題：曹大帶我學(xué) Go之初識(shí) Ast 的威力
網(wǎng)頁(yè)網(wǎng)址：http://m.fisionsoft.com.cn/article/dpcidco.html
