學習golang底層源碼具備什麼知識（生動講解編譯原理入門）

2023-04-29 19:12:02 1

作者：pixelcao，騰訊 IEG 後臺開發工程師

最近的工作需要用表達式做一些參數的配置，然後發現大腦一片空白，在 Google 裡試了幾個關鍵詞（起初搜了下「符號引擎」，發現根本不是我想要的）之後，明白過來自己應該是需要補一些編譯原理的知識了。在掉了兩晚上頭髮之後，決定整理一下自己的知識網絡。

要解析的表達式大概長這個樣子：

avg(teams[*].players.attributes[skill])*rules[latency].maxLatency

正則表達式是個辦法，但不是最優解，除了很難通過一句正則解析整條語句外，以後擴展更多語法時，正則表達式的修改也分外麻煩。

作為非計算機科班出身的工程師，還是知道一點，任何領域發展出的課題都需要產、學、研三者的配合才能完成，「產」 指企業，「學」 指高等院校，「研」 指科研機構。

其實自打 C 語言從貝爾實驗室走出來之後，「研」 究這一步就已經完成大半了，於是被下放到 「學」 校，有了《編譯原理》這門課程，最後流入 「產」 業中大規模應用。

所以這篇文章主要從兩方面給初學者（尤其是跟我一樣非科班出身的 coder）一個指南：

以下內容均為個人理解，歡迎探討，如有不精確之處，以教科書為準～

編譯器由詞法分析、語法分析、語義檢查再到中間表示輸出和最後二進位生成的流程，這些已經可以作為前置知識，就不提了。

隨手打開一個工程，我們就能發現形形色色的語言文件，比如 yaml 格式的服務配置文件、json 格式的工程配置文件、js 和 go 等原始碼文件等。忽略掉他們繁雜的用途，按其表達能力，可以分為兩種：

歪個樓，這裡有一個弔詭的事實，yaml 竟然是圖靈完備的！甚至很多語言都需要特別使用 safe_load 來加載 yaml 文件，比如用 java 直接 load 這段 yaml，會執行一次 HTTP 請求。

!!javax.script.ScriptEngineManager[!!java.net.URLClassLoader[[!!java.net.URL[\"http://localhost\"]]]]

不管是為特定領域而發明的各類 DSL，還是圖靈完備的 GPL 語言，他們基本都符合 BNF（巴科斯範式）。

BNF 是一種 上下文無關文法，舉個例子就是，人類的語言就是一種 上下文有關文法，我隨時都可以講一句 「以上說的都是廢話」，戲弄一下讀者閱讀本文所花的時間（每當回憶起來，我都會坐在輪椅上大呼過癮）。

關於 BNF 具體定義，這裡摘抄一下維基百科，後面做詳細解說：

BNF 規定是推導規則(產生式)的集合，寫為：

::=

這裡的 是非終結符，而表達式由一個符號序列，或用指示選擇的豎槓 '|' 分隔的多個符號序列構成，每個符號序列整體都是左端的符號的一種可能的替代。從未在左端出現的符號叫做終結符。

暫且不用理解裡面提到的 「終結符」 和 「非終結符」，在明白來龍去脈之前去查這些，說不定大腦會 stackoverflow。但是也別慌，所有術語和英文縮寫都是紙老虎，其實他們都是很簡單的概念，但是你需要一個合適的場景來理解它們起到的作用。

2.2 學科交叉：自然語言理解

上節我們說到，計算機語言多數是符合 BNF 的上下文無關語言，從表達能力上分為 DSL 和 GPL 兩類；而人類語言屬於上下文有關語言，其實正是由於這一點，才給在 NLP（自然語言理解）領域帶來了不少困難。

好，知道了這些英文縮寫，再去讀那些專業文章會簡單得多。

這些其實都是在 靜態層面 上對語言的描述，為了實際執行這些語言，就需要對其進行解析，還原出語言本身所描述的信息結構。這件事，在計算機領域的課程叫《編譯原理》，在智能科學與技術的課程叫《自然語言理解》。

編譯原理（一張圖）：

編譯原理

自然語言理解（兩張圖）：

NLP

不難看出，兩者的流程驚人的相似：

都需要先進行 tokenize 處理，編譯器做的是詞法分析（常用工具搜 lexer），NLP 做的是 分詞（最常見的是 jieba 分詞）詞法分析的產物是有含義的 token，下面都需要進行語法分析（即 parser），NLP 裡通常會做 向量化（最常見的是 word2vec 方法）這兩步完成後，編譯器前端得到的產物是 AST（Abstract Syntax Tree，抽象語法樹），NLP 得到的產物是一段話的向量化表示

兩者的共同點止步於此，鑑於 NLP 技術仍在高速發展（而編譯原理早就是老生常談了），向量化得到的產物難以處理同義詞，所以後面的步驟也局限於分析一句話的意圖、和提取有效信息（利用這些可以做一個簡陋版的 Siri）。最新（其實是兩年前了）的進展是 BERT 模型和衍生出來的許多研究上下文關係的方法，現在的 NLP 技術已經可以做閱讀理解問題了。

此外，DSL 和 GPL 的共同點也止步於此。要記得，DSL 是面向特定用途的語言，以 JSON 為例，得到 AST 就已經有完整的信息結構了，在面向對象語言裡無非再多一步：利用反射將其映射到一個 class 的所有欄位裡；以 HTML 為例，得到 AST 就已經有完整的 DOM 樹了，瀏覽器已經具備渲染出整個網頁所需的大部分信息。

最後，對 GPL 語言來說，編譯型語言目的是生成機器可執行的代碼，解釋型語言的目的是生成虛擬機認識的中間代碼。這部分職責由編譯器後端承擔，現代編譯器領域的最佳拍檔就是 Clang LLVM。

2.3 別慌：英文縮寫都是紙老虎

現在我們知道了事情的來龍去脈，也就明白了開頭的需求屬於哪種問題。對工程師來說，解決問題的第一步就是先知道你面對的是什麼問題：使用編譯原理的知識來解析開頭的表達式，相當於定義一個簡陋的 DSL 語言，並編寫詞法解析器和語法解析器（lexer & parser）來將其轉換成 AST（抽象語法樹），進而對其進行處理。

在進行工程實踐之前，還有些術語不得不先行了解。

首先是前面提到的終結符和非終結符，重複一下上面解釋 BNF 時舉的抽象表達式： ::= 。可以這樣來理解：

由詞法解析器生成的符號，也叫 token，是終結符。終結符是最小表義單位，無法繼續進行拆解和解析規則左側定義的符號，是非終結符。非終結符需要進行語法解析，最終由終結符構成其表示形式

其次是 NFA 和 DFA，FA 表示 Finite Automata（有窮狀態機），即根據不同的輸入來轉換內部狀態，其內部狀態是有限個數的。而 NFA 和 DFA 分別代表 有窮不確定狀態機 和 有窮確定狀態機。運用子集構造法可以將 NFA 轉換為 DFA，讓構造得到的 DFA 的每個狀態對應於 NFA 的一個狀態的集合。

詞法分析器（lexer）生成終結符，而語法分析器（parser）則利用自頂向下或自底向上的方法，利用文法中定義的終結符和非終結符，將輸入信息轉換為 AST（抽象語法樹）。也就是我們在此次需求中需要獲得的東西。

三、工程實踐

我們的案例是使用 golang 來編寫 lexer 和 parser。

在工程上，不同語言的實踐方式是不一樣的。你可以選擇自己編寫 lexer 和 parser，也可以選擇通過定義 yacc 文件的方式讓工具自動生成。在參考文獻中會給出自己編寫它們的相關文章，在 golang 的案例裡，lexer 需要自己編寫，而 parser 則由工具生成。

如果使用 Antlr 的話，可以將 lexer 和 parser 一同搞定，用得好的話，可以實現諸如像 JS 和 Swift 語言互相轉換的特技。不在本文實踐範圍內。

3.1 goyacc 的安裝

Golang 1.8 之前自帶 goyacc 工具，由於使用量太少，之後版本就需要手動安裝了。

goget-ugithub.com/golang/tools/tree/master/cmd/goyacc

使用起來參數如下：

然後我們需要搞定詞法分析器和語法分析器。

3.2 使用 goyacc 的思路

yacc 類工具的共同特點就是，通過編寫 .y 格式的說明文件定義語法，然後使用 yacc 命令行工具生成對應語言的原始碼。

所以嘗起來就比較像 protobuf，proto 文件就像 .y 文件一樣本身不可執行，需要用一些 protogen 工具來生成對應每種語言的原始碼文件。

在 goyacc 中，lexer 本身相對簡單，自己編寫 go 代碼實現就夠了，parser 部分所需的文法約定，需要我們編寫 .y 文件，也就需要了解 yacc 的文法約定。goyacc 會在生成好的 go 原始碼中提供 yyParse 、yyText 、yyLex 等接口，最後我們自己編寫調用 parser 的文件，就能把流程跑起來了。

我們的目的，就是給定如下示例輸入，然後輸出能代表 AST 的數據結構：

#示例輸入avg(teams[*].maxPlayers)*flatten(rules[red].players.playerAttributes[exp])#示例輸出parsedobj:[map[avg:[map[teams:*]map[maxPlayers:]]]map[flatten:[map[rules:red]map[players:]map[playerAttributes:exp]]last_operator:*]][{"avg":[{"teams":"*"},{"maxPlayers":""}]},{"flatten":[{"rules":"red"},{"players":""},{"playerAttributes":"exp"}],"last_operator":"*"}]

3.3 詞法分析器

lexer 我們選擇自己用 golang 編寫。lexer 的基本功能是通過一個 buffer reader 不斷讀取文本，然後告訴 goyacc 遇到的是什麼符號。

Lex 函數的返回值類型（即詞法分析器的實際產物）需要在後面的 yacc 文件的 token 部分定義。

為了與 goyacc 結合，我們需要定義和實現以下接口：

typeScannerstruct{buf*bufio.Readerdatainterface{}errerrordebugbool}funcNewScanner(rio.Reader,debugbool)*Scanner{return&Scanner{buf:bufio.NewReader(r),debug:debug,}}func(sc*Scanner)Error(sstring){fmt.Printf("syntaxerror:%s\n",s)}func(sc*Scanner)Reduced(rule,stateint,lval*yySymType)bool{ifsc.debug{fmt.Printf("rule:%v;state%v;lval:%v\n",rule,state,lval)}returnfalse}func(s*Scanner)Lex(lval*yySymType)int{returns.lex(lval)}

我們可以定義私有函數完成 lex 的實際工作。

3.4 語法分析器

上節我們有說，yacc 文件最終會生成 go 原始碼文件，裡面包含了 yyParse 、yyText 、yyLex 等接口的具體實現。

而 yacc 只包含定義文法的語法，不含各類程式語言的語法，所以聰明的你肯定能猜到，yacc 文件中免不了會出現類似宏定義的東西，會直接嵌入各類程式語言的代碼片段。

有了這個心理預期，我們看一下 yacc 文件的結構：

{%嵌入代碼%}文法定義%%文法規則%%嵌入代碼（golang代碼，通常忽略此部分直接在寫在代碼頭中）

其文法定義如下：

我們自己編寫 yacc 實現 parser，最少需要知道的就是前面四種描述符。一開始我們只實現最簡單的語法規則，後面自己就會逐漸了解更高級的文法規則了。

3.5 參考工程

goyacc 的示例工程不多，不推薦用 yacc 實現計算器的例子，參考性比較差。

如下工程實現了用 golang 解析 JSON 數據，只需要補一個 go.mod 和 main 函數就能拿來邊調試邊參考著實現自己的需求了，十分推薦：https://github.com/sjjian/yacc-examples

moduleexample.com/mgo1.14requiregithub.com/pkg/errorsv0.9.1

packagemainimport("encoding/json""fmt""io/ioutil""example.com/m/yacc_parseJson")funccheck(eerror){ife!=nil{panic(e)}}funcmain{dat,err:=ioutil.ReadFile("json.txt")check(err)fmt.Printf("rawstr:%s\n",string(dat))jsonobj,err:=yacc_parseJson.ParseJson(string(dat),true)fmt.Printf("parsedobj:% v\n",jsonobj)jsonStr,_:=json.Marshal(jsonobj)fmt.Printf(string(jsonStr))}

四、參考文獻

編譯原理（基礎篇）golang 實現自定義語言的基礎什麼是 NFA 和 DFA從 antlr 扯淡到一點點編譯原理How to Write a Parser in Go,