建站
咨詢
售后
建站咨詢
新聞中心
什么是解析
解析是將 輸入 根據(jù)要求 運(yùn)算 出 結(jié)果。 比如將四則表達(dá)式"1 + 2"運(yùn)算出3。
解析是 很常見(jiàn)的需求，特別是軟件的配置，但很多程序員不會(huì)自己去手寫(xiě)，可能也不知道怎么寫(xiě) 。 大概是因?yàn)楝F(xiàn)在已經(jīng)有了一些通用的標(biāo)準(zhǔn)格式，比如ini, json, yaml等，這些常見(jiàn)的格式都有標(biāo)準(zhǔn)庫(kù)可供使用。 然而 不管是否需要自己定制，還是用現(xiàn)有的格式，手寫(xiě)解析文本是一項(xiàng)非常提升編程能力的事情。 這也是本文的目的，通過(guò)四則運(yùn)算的例子，分享如何實(shí)現(xiàn)解析器，還有編程經(jīng)驗(yàn)和思考。
例子四則運(yùn)算
麻雀雖小，五臟俱全，這估計(jì)是最迷你的解析例子了。我們要做的事情就是將字符串"100 - 20 * 30 + 40 * 50"，解析運(yùn)算出結(jié)果：240。這里只支持整數(shù)和加減乘除。 有興趣的同學(xué)，可以不看本文的實(shí)現(xiàn) ，先自己手寫(xiě)試一下 。
(四則運(yùn)算語(yǔ)法表示)
解析通用模式
不管是實(shí)現(xiàn)語(yǔ)言，解析配置，解析特定文本需求，解析模式大致一樣，都是如圖所示。只是有些語(yǔ)義更復(fù)雜，有些需要考慮性能，在解析和執(zhí)行中間會(huì)增加更多的處理，像語(yǔ)法樹(shù)，甚至C語(yǔ)言.o文件。
通用術(shù)語(yǔ)：
text：文本字符串作為輸入源，文件的話會(huì)被讀成（流式）字符串。
run：運(yùn)行。運(yùn)行輸入，計(jì)算出結(jié)果。
parse：解析。
token：詞法單元，比如 "123", " 40", " +", " -" 。
expression：表達(dá)式，比如" 3", "1 + 2" 。
unary：一元操作數(shù)，比如3, 20, 100。
code：中間碼，由parse產(chǎn)生。
exec：運(yùn)行中間碼產(chǎn)生結(jié)果。
這些術(shù)語(yǔ)也會(huì)在代碼實(shí)現(xiàn)中出現(xiàn)。
運(yùn)算就是我們要做的事情，要實(shí)現(xiàn)解析和執(zhí)行兩個(gè)功能。以解析四則為例：
- calc_run(text):
- code = cacl_parse(text)
- cacl_exec(code)
(calc是calculator的縮寫(xiě))
計(jì)算機(jī)世界里的四則運(yùn)算
代碼是人類邏輯的一種表示方式。"1 + 2"是人眼可讀懂的，但對(duì)計(jì)算機(jī)，我們得設(shè)計(jì)一個(gè)它能執(zhí)行的。
1. 借助棧（數(shù)組），解析后的中間碼這樣表示： 。
code = [1, 2, +]
2. 執(zhí)行，遍歷code作相應(yīng)的處理。
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是臨時(shí)的棧用于存放運(yùn)算值）
思路就是壓值進(jìn)去，碰到操作符取出來(lái)運(yùn)算，并且將結(jié)果壓進(jìn)去， 所以最后 的結(jié)果 會(huì)是s[0]。
如何實(shí)現(xiàn)新功能
假設(shè)這是一個(gè)需求，怎么在不用996的情況下，完成并且是高質(zhì)量的代碼。這是編程能力的綜合體現(xiàn)，所以本質(zhì)上還是要不斷提升編程能力。需要指出的是簡(jiǎn)化是一種特別的能力，我們要在編碼中經(jīng)常使用。
1. 構(gòu)思整體設(shè)計(jì)，能清晰的陳述實(shí)現(xiàn)邏輯。
2. 編寫(xiě)測(cè)試用例。
我們給這個(gè)功能取個(gè)名稱：calculator，運(yùn)算器的意思，并且用它的縮寫(xiě)作為前綴cacl。
編程經(jīng)驗(yàn)：無(wú)比重要的命名
善用縮寫(xiě)作為前綴， 對(duì)項(xiàng)目和模塊加個(gè)有意義的前綴能讓讀代碼的人清楚它的上下文。 這在團(tuán)隊(duì)協(xié)作里更有價(jià)值。
a. 項(xiàng)目：比如nginx的源碼里都有ngx_，nginx unit里的nxt_，njs里的njs_等。這些都可以讓人清楚的知道這個(gè)項(xiàng)目的名稱。
b. 模塊：比如nginx里的http模塊ngx_http_，日志模塊ngx_http_log_，unit里文件服務(wù)的nxt_http_static_等。注意模塊是可以包含子模塊的。
所以我們將用cacl_作為四則運(yùn)算解析的前綴，會(huì)有cacl_run, cacl_parse, cacl_exec這樣的函數(shù)。
編程經(jīng)驗(yàn)： 追求清晰和簡(jiǎn)潔
代碼即邏輯，其它都是表達(dá)邏輯的方式。像文件，模塊，函數(shù)和變量等。
不管需要什么樣的命名，變量，功能函數(shù)，文件名等，清晰和簡(jiǎn)潔是我認(rèn)為最重要的。在做到清晰的前提下保持簡(jiǎn)潔，即一目了然。
比如命名：
nxt_http_request.c ，表示http 的請(qǐng)求處理模塊 ，足夠清晰和 簡(jiǎn)潔。
nxt_h1proto.c，表示http的1.1協(xié)議的處理。
nxt_epoll_engine.c，表示epoll模塊，對(duì)比下nxt_event_epoll_engine.c。因?yàn)閑poll已經(jīng)是個(gè)專業(yè)術(shù)語(yǔ)，用于處理網(wǎng)絡(luò)事件的，這時(shí)event就變的多余了，在能表達(dá)清晰的前提下，繼續(xù)追求簡(jiǎn)潔。
比如邏輯：
good
- /*
- * 讀數(shù)據(jù)
- * 如果成功，追加數(shù)據(jù)
- * 返回?cái)?shù)據(jù)
- */
- data = read();
- if (data) {
- data = data + "...";
- }
- return data;
ok
- /*
- * 讀數(shù)據(jù)
- * 如果失敗，返回空
- * 追加數(shù)據(jù)
- * 返回?cái)?shù)據(jù)
- */
- data = read();
- if (data == null) {
- return null;
- }
- data = data + "...";
- return data;
這是個(gè)很小的例子，只是為了說(shuō)明在做到清晰的前提，做到越簡(jiǎn)潔越好。
比如設(shè)計(jì)：
因?yàn)樘熨x可能是天花板。目前只懂的是保持簡(jiǎn)單和通用是好的設(shè)計(jì)。
前段時(shí)間提要實(shí)現(xiàn)一個(gè)功能，是Unit有關(guān)response filter的，但沒(méi)有被允許，這種設(shè)計(jì)目前組里只有nginx作者Igor的設(shè)計(jì)讓人最放心。其它人都能做，包括我，但是設(shè)計(jì)出來(lái)的東西要做到簡(jiǎn)單和通用，還是差點(diǎn)功力。
以前也經(jīng)歷過(guò)這個(gè)階段：學(xué)會(huì)復(fù)雜的功能，并覺(jué)得是干貨。建議多思考，多原創(chuàng)，多看優(yōu)秀的作品，及早突破一些認(rèn)識(shí)的局限。
實(shí)現(xiàn)解析邏輯
解析的結(jié)果是產(chǎn)生中間碼，引入parser對(duì)象方便解析。
- 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;
- }
對(duì)那些分散的信息，要考慮用聚集的方式比如對(duì)象，放在一起處理。這也是高內(nèi)聚的一種體現(xiàn)。
前面提到簡(jiǎn)化是一種能力。
簡(jiǎn)化1: 能從text里找出（所有的）token。實(shí)現(xiàn)下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;
- }
每次調(diào)用next_token()，就能拿到當(dāng)前的token，并且解析移動(dòng)到下一個(gè)token的開(kāi)始位置。
簡(jiǎn)化2：可以將運(yùn)算符*和+當(dāng)作同一級(jí)，但是這里篇幅有限，不貼中間實(shí)現(xiàn)過(guò)程
簡(jiǎn)化3: 分析邏輯，直到能清晰的表達(dá)，這也說(shuō)明你足夠理解它的本質(zhì)了。
以"1 + 2 * 3 - 4"為例：
我們將整個(gè)字符串稱為expression，里面的各塊也是expression。表達(dá)式的表示是 expression: expression [op expression]。
因此 "1 + 2 * 3 - 4"是表達(dá)式，"2 * 3"也是表達(dá)式, "1"和"4"也是表達(dá)式。
注意*的優(yōu)先級(jí)比+高，因?yàn)榭梢赃@樣分析：
2 * 3是一個(gè)整體，操作數(shù)(2) 操作符(*) 操作數(shù)(3)
1 + 2 * 3也是一個(gè)整體，操作數(shù)(1) 操作符(+) 操作數(shù)(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;
- }
注意：我們是邊解析邊產(chǎn)生中間碼的。
實(shí)現(xiàn)之執(zhí)行
執(zhí)行就相對(duì)簡(jiǎn)單很多了，只要思路清晰。
- 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;
- }
- }
- }
測(cè)試用例很重要
- 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);
編程經(jīng)驗(yàn)：一致性
每個(gè)代碼里有意義的函數(shù)和變量都像人物一樣。之前怎么命名，之后也一樣，同樣的意思不要有多余的表示。而且保持它們的出場(chǎng)順序不變。
- 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 = [
- ];
- unit_test(tests);
https://github.com/hongzhidao/the-craft-of-programming
在開(kāi)源浪潮下，寫(xiě)好的代碼尤其重要!
網(wǎng)站標(biāo)題：編程是門(mén)手藝，手寫(xiě)解析器：提升編程能力
轉(zhuǎn)載來(lái)源：http://www.5511xx.com/article/cdoejeo.html
