程式設計是門手藝，手寫解析器：提升程式設計能力

作者：洪志道

程式設計師洪志道

什麼是解析

解析是將

輸入

根據要求

運算

出

結果。

比如將四則表示式“1 + 2”運算出3。

解析是 很常見的需求，特別是軟體的配置，但很多程式設計師不會自己去手寫，可能也不知道怎麼寫 。 大概是因為現在已經有了一些通用的標準格式，比如ini， json， yaml等，這些常見的格式都有標準庫可供使用。 然而 不管是否需要自己定製，還是用現有的格式，手寫解析文字是一項非常提升程式設計能力的事情。 這也是本文的目的，透過四則運算的例子，分享如何實現解析器，還有程式設計經驗和思考。

例子四則運算

麻雀雖小，五臟俱全，這估計是最迷你的解析例子了。我們要做的事情就是將字串“100 - 20 * 30 + 40 * 50”，解析運算出結果：240。這裡只支援整數和加減乘除。 有興趣的同學，可以不看本文的實現 ，先自己手寫試一下 。

（四則運算語法表示）

解析通用模式

不管是實現語言，解析配置，解析特定文字需求，解析模式大致一樣，都是如圖所示。只是有些語義更復雜，有些需要考慮效能，在解析和執行中間會增加更多的處理，像語法樹，甚至C語言。o檔案。

通用術語：

text：文字字串作為輸入源，檔案的話會被讀成（流式）字串。

run：執行。執行輸入，計算出結果。

parse：解析。

token：詞法單元，比如

“123”，

“

40”，

“

+”，

“

-”

。

expression：表示式，比如“

3”， “1 + 2”

。

unary：一元運算元，比如3， 20， 100。

code：中間碼，由parse產生。

exec：執行中間碼產生結果。

這些術語也會在程式碼實現中出現。

運算就是我們要做的事情，要實現解析和執行兩個功能。以解析四則為例：

calc_run（text）： code = cacl_parse（text） cacl_exec（code）

（calc是calculator的縮寫）

計算機世界裡的四則運算

程式碼是人類邏輯的一種表示方式。“1 + 2”是人眼可讀懂的，但對計算機，我們得設計一個它能執行的。

1。 藉助棧（陣列），解析後的中間碼這樣表示： 。

code = ［1， 2， +］

2。 執行，遍歷code作相應的處理。

lo op：

c = code［i++］；

if （c is num） {

s。push（c）

} else {

op1 = s。pop（）

op2 = s。pop（）

r = op1 + op2

s。push（r）

}

（s是臨時的棧用於存放運算值）

思路就是壓值進去，碰到運算子取出來運算，並且將結果壓進去， 所以最後 的結果 會是s［0］。

如何實現新功能

假設這是一個需求，怎麼在不用996的情況下，完成並且是高質量的程式碼。這是程式設計能力的綜合體現，所以本質上還是要不斷提升程式設計能力。需要指出的是簡化是一種特別的能力，我們要在編碼中經常使用。

1。 構思整體設計，能清晰的陳述實現邏輯。

2。 編寫測試用例。

我們給這個功能取個名稱：calculator，運算器的意思，並且用它的縮寫作為字首cacl。

程式設計經驗：無比重要的命名

善用縮寫作為字首， 對專案和模組加個有意義的字首能讓讀程式碼的人清楚它的上下文。 這在團隊協作裡更有價值。

a。 專案：比如nginx的原始碼裡都有ngx_，nginx unit裡的nxt_，njs裡的njs_等。這些都可以讓人清楚的知道這個專案的名稱。

b。 模組：比如nginx裡的http模組ngx_http_，日誌模組ngx_http_log_，unit裡檔案服務的nxt_http_static_等。注意模組是可以包含子模組的。

所以我們將用cacl_作為四則運算解析的字首，會有cacl_run， cacl_parse， cacl_exec這樣的函式。

程式設計經驗： 追求清晰和簡潔

程式碼即邏輯，其它都是表達邏輯的方式。像檔案，模組，函式和變數等。

不管需要什麼樣的命名，變數，功能函式，檔名等，清晰和簡潔是我認為最重要的。在做到清晰的前提下保持簡潔，即一目瞭然。

比如命名：

nxt_http_request。c ，表示http 的請求處理模組 ，足夠清晰和 簡潔。

nxt_h1proto。c，表示http的1。1協議的處理。

nxt_epoll_engine。c，表示epoll模組，對比下nxt_event_epoll_engine。c。因為epoll已經是個專業術語，用於處理網路事件的，這時event就變的多餘了，在能表達清晰的前提下，繼續追求簡潔。

比如邏輯：

good

/* * 讀資料 * 如果成功，追加資料 * 返回資料 */ data = read（）； if （data） { data = data + “。。。”； } return data；

ok

/* * 讀資料 * 如果失敗，返回空 * 追加資料 * 返回資料 */ data = read（）； if （data == null） { return null； } data = data + “。。。”； return data；

這是個很小的例子，只是為了說明在做到清晰的前提，做到越簡潔越好。

比如設計：

因為天賦可能是天花板。目前只懂的是保持簡單和通用是好的設計。

前段時間提要實現一個功能，是Unit有關response filter的，但沒有被允許，這種設計目前組裡只有nginx作者Igor的設計讓人最放心。其它人都能做，包括我，但是設計出來的東西要做到簡單和通用，還是差點功力。

以前也經歷過這個階段：學會複雜的功能，並覺得是乾貨。建議多思考，多原創，多看優秀的作品，及早突破一些認識的侷限。

實現解析邏輯

解析的結果是產生中間碼，引入parser物件方便解析。

function calc_parse（text） { var parser = { text： text， pos： 0， token： {}， code： ［］ }； next_token（parser）； if （calc_parse_expr（parser， 2）） { return null； } if （parser。token。val ！= TOK_END） { return null； } parser。code。push（OP_END）； return parser。code； }

對那些分散的資訊，要考慮用聚集的方式比如物件，放在一起處理。這也是高內聚的一種體現。

前面提到簡化是一種能力。

簡化1： 能從text裡找出（所有的）token。實現下next_token（）。

var TOK_END = 0， TOK_NUM = 1； function next_token（parser） { var s = parser。text； while （s［parser。pos］ == ‘ ’） { parser。pos++； } if （parser。pos == s。length） { parser。token。val = TOK_END； return； } var c = s［parser。pos］； switch （c） { case ‘1’： case ‘2’： case ‘3’： case ‘4’： case ‘5’： case ‘6’： case ‘7’： case ‘8’： case ‘9’： case ‘0’： parse_number（parser）； break； default： parser。token。val = c； parser。pos++； break； } } function parse_number（parser） { var s = parser。text； var num = 0； while （parser。pos < s。length） { var c = s［parser。pos］； if （c >= ‘0’ && c <= ‘9’） { num = num * 10 + （c - ‘0’）； parser。pos++； continue； } break； } parser。token。val = TOK_NUM； parser。token。num = num； }

每次呼叫next_token（），就能拿到當前的token，並且解析移動到下一個token的開始位置。

簡化2：可以將運算子*和+當作同一級，但是這裡篇幅有限，不貼中間實現過程

簡化3： 分析邏輯，直到能清晰的表達，這也說明你足夠理解它的本質了。

以“1 + 2 * 3 - 4”為例：

我們將整個字串稱為expression，裡面的各塊也是expression。表示式的表示是 expression： expression ［op expression］。

因此 “1 + 2 * 3 - 4”是表示式，“2 * 3”也是表示式， “1”和“4”也是表示式。

注意*的優先順序比+高，因為可以這樣分析：

2 * 3是一個整體，運算元（2） 運算子（*） 運算元（3）

1 + 2 * 3也是一個整體，運算元（1） 運算子（+） 運算元（2 * 3）

依此類推。程式碼如下：

var OP_END = 0， OP_NUM = 1， OP_ADD = 2， OP_SUB = 3， OP_MUL = 4， OP_DIV = 5； function calc_parse_expr（parser， level） { if （level == 0） { return calc_parse_unary（parser）； } if （calc_parse_expr（parser， level - 1）） { return -1； } for （；；） { var op = parser。token。val； switch （level） { case 1： switch （op） { case ‘*’： var opcode = OP_MUL； break； case ‘/’： var opcode = OP_DIV； break； default： return 0； } break； case 2： switch （op） { case ‘+’： var opcode = OP_ADD； break； case ‘-’： var opcode = OP_SUB； break； default： return 0； } break； } next_token（parser）； if （calc_parse_expr（parser， level - 1）） { return -1； } parser。code。push（opcode）； } return 0； } function calc_parse_unary（parser） { switch （parser。token。val） { case TOK_NUM： parser。code。push（OP_NUM）； parser。code。push（parser。token。num）； break； default： return -1； } next_token（parser）； return 0； }

注意：我們是邊解析邊產生中間碼的。

實現之執行

執行就相對簡單很多了，只要思路清晰。

function calc_exec（code） { var i = 0； var stack = ［］； for （；；） { opcode = code［i++］； switch （opcode） { case OP_END： return stack［0］； case OP_NUM： var num = code［i++］； stack。push（num）； break； case OP_ADD： var op2 = stack。pop（）； var op1 = stack。pop（）； var r = op1 + op2； stack。push（r）； break； case OP_SUB： var op2 = stack。pop（）； var op1 = stack。pop（）； var r = op1 - op2； stack。push（r）； break； case OP_MUL： var op2 = stack。pop（）； var op1 = stack。pop（）； var r = op1 * op2； stack。push（r）； break； case OP_DIV： var op2 = stack。pop（）； var op1 = stack。pop（）； var r = op1 / op2； stack。push（r）； break； } } }

測試用例很重要

function calc_run（text） { var code = calc_parse（text）； if （code == null） { return null； } return calc_exec（code）； } function unit_test（tests） { for （var i = 0； i < tests。length； i++） { var test = tests［i］； var ret = calc_run（test。text）； if （ret ！= test。expect） { console。log（“\”“ + test。text + ”\“ failed，”， “expect \”“ + test。expect + ”\“，”， “got \”“ + ret + ”\“”）； } } } var tests = ［ { text： “123”， expect： 123 }， { text： “1 + 2 + 3”， expect： 6 }， { text： “10 - 1 - 11”， expect： -2 }， { text： “1 + 2 * 3 - 4”， expect： 3 }， { text： “1 + 2 * 3 - 4 / 2”， expect： 5 }， { text： “”， expect： null }， { text： “a”， expect： null }， { text： “10 a ”， expect： null }， { text： “10 + ”， expect： null }， { text： “ + 2”， expect： null }， ］； unit_test（tests）；

程式設計經驗：一致性

每個程式碼裡有意義的函式和變數都像人物一樣。之前怎麼命名，之後也一樣，同樣的意思不要有多餘的表示。而且保持它們的出場順序不變。

var TOK_END = 0， TOK_NUM = 1； var OP_END = 0， OP_NUM = 1， OP_ADD = 2， OP_SUB = 3， OP_MUL = 4， OP_DIV = 5； function calc_run（text） { } function calc_parse（text） { } function calc_parse_expr（parser， level） { } function calc_parse_unary（parser） { } function next_token（parser） { } function parse_number（parser） { } function calc_exec（code） { } function unit_test（tests） { } var tests = ［ ］；

https：//github。com/hongzhidao/the-craft-of-programming

在開源浪潮下，寫好的程式碼尤其重要！