動手寫一門簡單語言吧喵從計算姬開始

01-26

前文動手寫一門簡單語言吧喵里提到了白雪來自於計算姬, 設計的目標也是做簡單的數字計算處理, 不過在擁有函數(高階函數, 閉包)之後已經不僅僅是計算姬啦喵.

這次我們來回顧一下白雪的前身.

計算姬是可以說是編譯原理里最簡單的例子, 同時也是編程初學者不錯的一個練習. 相信大家不少人都寫過. 如果沒嘗試過的編程新手們有興趣也可以跟著本文嘗試一下, 我儘力採用最簡單通俗易懂又不失嚴謹的方式來解釋, 算作是編譯原理最簡單的入門級文章吧(畢竟寫一個計算姬好像並不需要這麼多知識).

這次呢我採取不太一樣的編程範式(函數式)來編寫計算姬, 不過原理都是一樣的啦喵. 編程新手們可以嘗試通過傳統的方式(命令式)來重現.

好啦喵, 開始吧

首先我們先明確目標, 做好準備工作

這次我們的目標是實現一個支持加減乘除冪和括弧的計算姬

() 括弧^ 冪*, / 乘, 除+, - 加, 減

優先順序從上往下依次遞減

然後語法(BNF)是:

直接文法寫出來可能會有點難懂, 看了下面的解釋就會好理解很多

expr_atom: "(" expr ")" | NUMBER表示的是輸入表達式里最基本的組成單位, 原子表達式, 即是不可再簡化分割的獨立單位.上式中表明了expr_atom的構成:一對包圍的括弧包括一個表達式 "(" expr ")" 或者單個數字NUMBER(上式中|符號表示或, 引號包圍的是表達式中具體出現的字元)形象來說:1 3.14 (1+2)都是原子表達式, 即是我們在處理表達式時可以當作單個對象處理.expr_pow: expr_atom "^" expr_pow | expr_atom同理冪表達由單個原子表達式構成或者由多個原子表達式通過冪運算符連接上式中的加號表示一個或多個重複例如:1 2^2 3^(1+2)^3對應的語法單位即是: 1>> expr_atom>> expr_pow 2 "^" 2>> expr_atom "^" expr_atom >> expr_atom "^" expr_pow>> expr_pow 3 "^" (1+2) "^" 3>> expr_atom "^" expr_atom "^" expr_atom >> expr_atom "^" expr_atom "^" expr_pow>> expr_atom "^" expr_pow>> expr_pow那麼乘法和加法表達式也是同樣處理最後單個加法表達式就是整個表達式啦接下來來看一個複雜表達式的語法構成(其中省略了平凡情況, 如expr_mul->expr_add->expr直接寫成expr_mul->expr和expr_mul<-expr_add<-expr直接寫成expr_mul<-expr)(1+2)*(3+4)^2 ( 1 + 2 )>> ( expr_atom + expr_atom )>> ( expr_add )>> ( expr )>> expr_atom// (3+4)同理 (1+2) * (3+4) ^ 2>> expr_atom * expr_atom ^ expr_atom>> expr_atom * expr_pow>> expr_mul>> expr對應的結構(樹形結構, 平凡情況被省略, 因為不承擔任何語義):expr_mul| expr_add expr_pow| | 1 2 expr_add 2 | 3 4

語法規定了表達式的具體形式與構成, 就是長什麼樣子啦.

有了表達式的語法組成之後我們就可以對表達式進行求值(語義)了

語義非常簡單(指稱語義), 和語法的表示方式相似

value_of(NUMBER) = numbervalue_of(expr_pow) = value_of(subexpr) ^ value_of(subexpr)value_of(expr_mul) = value_of(subexpr) * value_of(subexpr) or value_of(subexpr) value_of(subexpr) orvalue_of(expr_add) = value_of(subexpr) + value_of(subexpr) or value_of(subexpr) - value_of(subexpr) orvalue_of(NUMBER)就是對應表達式字元串所代表的值subexpr為構成語法單元的元素例如1+2為expr_add, 其兩個subexpr為NUMBER(1)和NUMBER(2)

語義在語法的基礎上規定了表達式對應的值及求值方法.

相信大家應該有聽過前綴表達式和後綴表達式.

前綴表達式(1+2)*(3+4)^2* + 1 2 ^ + 3 4 2

他們其實是同一個表達式的不同形式, 但值相同. 即是語法不同, 語義相同.

前綴表達式的語法:

大家動手分析計算一下不是很難理解. 有興趣也可以寫一下前綴表達式的計算姬, 這個要比我們要寫的中綴表達式計算姬要簡單, 沒有括弧喵.

有了以上的理論基礎之後就可以開始編碼啦喵, 這裡呢我使用的是Python 3.

首先我們先確定層次(這裡按照一個簡單的解釋器的結構設計是為了後續拓展方便):

Input>> String=>Lexer->Parser->Evaluator=>Number >>Output

第一步獲取輸入字元串

Input: (1+2)*(3+4)^2

第二步詞法分析, 主要檢查是否有非法字元, 分割符號, 將數字字面值字元轉換成具體數值, 方便後續分析.

(1+2)*(3+4)^2Lexer: ["(", 1, "+", 2, ")", "*", "(", 3, "+", 4, ")", "^", 2]

第三步語法分析, 根據上面給出的語法對分割好的符號分析語法結構

["(", 1, "+", 2, ")", "*", "(", 3, "+", 4, ")", "^", 2]Parser: ["*", ["+", 1, 2], ["^", ["+", 3, 4], 2]]

第四步語義分析(求值), 根據語法器給出的語法結構(語法樹)計算具體值

["*", ["+", 1, 2], ["^", ["+", 3, 4], 2]]Evaluator: 147

最後當然就是輸出啦喵

Output: 147

確定好每一個步驟之後開始編碼

Lexer:

Lexer主要的任務是分割符號和將數字字元串轉換為數字.

非常簡單, 思路為按照運算符號(+, -, *, /, (, ), ^)將字元串進行分割, 然後判斷是否為整數或者浮點數並進行轉換. 分割使用正則表達式re.split, 然後使用map進行字元數字轉換.

設計行為是:

Input: (1+2)*(3+4)^2Stage_1: ["(", "1", "+", "2", ")", "*", "(", "3", "+", "4", ")", "^", "2"]Stage_2: ["(", 1, "+", 2, ")", "*", "(", 3, "+", 4, ")", "^", 2]

主要框架如下:

lexer=(lambda __Str: list(map(lambda s: int(s) if s.isdigit() else float(s) if re.match(r"^(d+?.d*?|d*?.d+?)$", s) else s, filter(None, re.split(r"([+-*/()^])", __Str)))))

#從裡到外是re.split(r"([+-*/()^])", __Str) #字元串分割filter(None,...) #剔除分割出的空字元, 如1+(2-3)中+和(之間會有一個空字元map(lambda s:...,filter...) #對每個分割出的字元判斷, 若為數字則轉換#轉換函數:(lambda s: int(s) if s.isdigit() else #整數 float(s) if re.match(r"^(d+?.d*?|d*?.d+?)$", s) else #浮點數 s) #非數字不轉換

接下來, 優化一下, 使用filter將字元串中的空格去除, 並檢查是否有非法字元, 檢查是否有非法的數字字元串如1.0.0

lexer=(lambda __Str: list(map(lambda s: int(s) if s.isdigit() else float(s) if re.match(r"^(d+?.d*?|d*?.d+?)$", s) else s if s.find(".")==-1 else do_raise("invaild number"), filter(None, re.split(r"([+-*/()^])", "".join(filter( (lambda c: re.match(r"[d+-*/().^]",c) or not (c==" " or do_raise("unexpect symbol ""+c+"""))), __Str)))))))

詞法器完成啦喵!

Parser:

語法器的構造是整個計算姬中最複雜的部分, 可能會有些難.

首先我使用的是遞歸下降的語法分析, 首先我們就要解決lambda表達式的遞歸的問題, 因為lambda表達式匿名, 所以沒辦法直接遞歸, 我這裡採用了一種比較簡單的處理方法, 使用wapper包裝匿名函數, 在調用匿名函數時將自身作為第一個參數傳入, 用以遞歸.

wapper=lambda _f: (lambda *_x: _f(wapper(_f), *_x))

注意_f第一個參數即是函數本身, 這裡大家可以思考一下為什麼. 還有更好的解決辦法是使用不動點組合子, 這裡不做介紹, 大家如果有興趣可以去了解一下.

有了wapper後lambda就可以進行遞歸調用啦, 比如階乘就可以寫成:

fac=wapper( lambda self, n: 1 if n<=0 else n*self(n-1))fac(5) #return 120

需要遞歸的函數只需要多增加一個參數self即可, self傳入由wapper完成, 調用方式和函數原型一致.

在解決遞歸問題之後可以開始著手設計語法器啦喵.

根據上面給出的語法語義和對應的設計目標, 語法分析器將接受來自詞法分析器初步處理的表達式, 然後我們需要確定每次函數返回與語法對應的樹節點基本結構為:

expr_atom: expr or NUMBERexpr_pow: ["^", subexpr, subexpr]expr_mul: ["*", subexpr, subexpr] or ["/", subexpr, subexpr]expr_add: ["+", subexpr, subexpr] or ["-", subexpr, subexpr]

list中第一個符號用於標識該語法樹節點的類型, 注意無具體語義的語法結構被省略了.

除了返回分析好的語法樹意外我們還需要告訴調用者分析好的語法樹對應的具體表達式部分用以移動到後續表達式繼續分析, 這裡我選擇一同直接返回剩餘後續表達式.

那麼我們語法器的設計行為是:

Input: [1]Output: [1,[]] #expr_atom# expr_atom# |# NUMBERInput: [1, "+", 2]Output_subexpr_1: [1, ["+", 2]] #由expr_add調用至expr_atom, #Input: [1, "+", 2]Output_subexpr_2: [2, []] #由expr_add調用至expr_atom #Input: [2]Output_expradd: [["+", 1, 2], []]# expr_add# | # 1 2#乘除和冪的分析類似Input: [3, "+", "(", 2, "+", 1, ")"]Output_subexpr_1: [3, ["+", "(", 2, "+", 1, ")"]] #由expr_add調用至expr_atom #Input: [3, "+", "(", 2, "+", 1, ")"]Output_expradd: [["+", 2, 1], []] #由expr_add調用至expr_atom, 繼續調用到expr #Input: ["(", 2, "+", 1, ")"] #[2, "+", 1]的分析見上例Output_expradd: [["+", 3, ["+", 2, 1]], []]# expr_add# | # 3 expr_add# | # 2 1

注意觀察語法結構和遞歸調用順序.

語法分析器返回一個list, list[0]是分析完成的語法樹, list[1]是後續待分析的表達式部分.

好~接下來逐個部分設計:

#parser for expr_atom#expr_atom: "(" expr ")" | NUMBERexpr_atom=(lambda __List: (lambda _t: [_t[0],_t[1][1:]] if _t[1] and _t[1][0]==")" else do_raise("expect symbol ")"")) (expr(__List[1:])) if __List and __List[0]=="(" else #遇到"(" expr ")" [__List[0], __List[1:]] if __List and not isinstance(__List[0], str) else #單個數字 [0, __List] #均不是以上的情況, 不做處理, 返回0 )

然後是expr_pow

#parser for expr_pow#expr_pow: expr_atom "^" expr_pow |# expr_atomexpr_pow=wapper(lambda self, __List: (lambda _t: (lambda _t0: [[_t[1][0],_t[0],_t0[0]],_t0[1]]) (self(_t[1][1:])) if _t[1] and _t[1][0]=="^" else _t) #self為expr_atom, 若存在^符號則遞歸調用分析後續的expr_pow部分 (expr_atom(__List)))

接下來, 在處理加法和乘法表達式的時候要注意語法中出現了左遞歸

expr_add: expr_add "+" expr_mul | expr_add "-" expr_mul | expr_mul

在調用expr_add分析中第一個子表達式即是其本身, 按照語法直接編碼將會造成遞歸調用死循環, 永遠到達不了邊界條件, 無法分析任何符號.

這時候需要稍微修改一下文法, 觀察語法發現, expr_add的語法推導如果會終止的話(事實是必定會終止, 因為表達式長度有限, 構成的語法樹高度亦必定有限, 那麼推導將會在有限步內結束)開頭只能由expr_mul表達式構成, 那麼我們可以提出一個因子expr_mul放在文法的最前面. 修改過後的文法如下:

expr_addm: expr_mul expr_addm_x expr_addm_x: "+" expr_mul expr_addm_x | "-" expr_mul expr_addm_x | NONE

修改文法中的NONE代表空, 即是不對應表達式中的任何符號. 在修改文法後該如何正確生成語法樹呢? 這個問題需要仔細思考思考, 不像expr_atom和expr_pow那樣直觀.

進行推導語法:

1+2+3>> expr_addm>> expr_mul expr_addm_x>> expr_mul "+" expr_mul expr_addm_x>> expr_mul "+" expr_mul "+" expr_mul expr_addm_x>> expr_mul "+" expr_mul "+" expr_mul NONE推導完畢對應的語法樹為:expr_add| expr_add 3| 1 2

通過上面的例子可以得出在對expr_add_x進行推導展開時, 對應生成一個expr_add結構, 加號和減號後面緊跟的expr_mul為一個expr_add的右子節點, 左節點為調用者已經完成分析已構建的語法樹, 如初始expr_addm中開頭的expr_mul和每次expr_add_x生成好的語法樹作為後續expr_add_x分析出的語法樹的左節點.

(這種叫做繼承屬性, 即需要利用調用者已得到的信息進行構造. 相對而言的是綜合屬性, 即只使用自身內部所有被調用者返回的信息進行構造. 如expr_atom.)

偽代碼如下:function expr_addm(): expr_addm_x(expr_mul())function expr_addm_x(left_subexpr): if(operator + or - exist) expr_addm_x([operator, left_subexpr, expr_mul()]) else left_subexpr //已完成所有分析, 此時不需要繼續構建樹, 直接返回

完整實現如下:

#parser for expr_add#expr_addm: expr_mul expr_addm_x #expr_addm_x: "+" expr_mul expr_addm_x |# "-" expr_mul expr_addm_x |# NONE##expr_addm_x接受一個參數為調用者已構建好的語法樹expr_add=(lambda __List: (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) #遞歸調用expr_addm_x, 將構建好的語法樹傳入 #注意_t[0]為上層傳入的參數 (rf(_t[1][1:])) #rf為expr_mul if _t[1] and _t[1][0] in {"+","-"} else _t) ) #wapper內包圍的為expr_addm_x, 需要遞歸調用 (expr_mul, expr_mul(__List))))

對於expr_mul也是一樣, 只是把{"+","-"}改成{"*","/"}和expr_mul改成expr_pow就好.

上面這一部分可能有些複雜. 大家可能需要仔細思考一下.

最後語法器的為

expr=(lambda __List: expr_add(__List))parser=(lambda __List: expr(__List)[0] #我們只需要語法樹, 若無錯誤完成分析後待分析的表達式應為空 #expr(__List)[1]==[] )

把上面所有代碼整合就得到了完整的語法器:

expr_atom=(lambda __List: (lambda _t: [_t[0],_t[1][1:]] if _t[1] and _t[1][0]==")" else do_raise("expect symbol ")"")) (expr(__List[1:])) if __List and __List[0]=="(" else [__List[0], __List[1:]] if __List and not isinstance(__List[0], str) else [0, __List] )expr_pow=wapper(lambda self, __List: (lambda _t: (lambda _t0: [[_t[1][0],_t[0],_t0[0]],_t0[1]]) (self(_t[1][1:])) if _t[1] and _t[1][0]=="^" else _t) (expr_atom(__List)))expr_mul=(lambda __List: (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) (rf(_t[1][1:])) if _t[1] and _t[1][0] in {"*","/"} else _t) ) (expr_pow, expr_pow(__List)))expr_add=(lambda __List: (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) (rf(_t[1][1:])) if _t[1] and _t[1][0] in {"+","-"} else _t) ) (expr_mul, expr_mul(__List)))expr=(lambda __List: expr_add(__List))parser=(lambda __List: expr(__List)[0] )

或者把上述所有中間部分組合在一起省略掉中間函數壓縮一下得到:

parser_impl=wapper(lambda self, __List, __Level=3: ((lambda _t: [_t[0],_t[1][1:]] if _t[1] and _t[1][0]==")" else do_raise("expect symbol ")"")) (self(__List[1:])) if __List and __List[0]=="(" else [__List[0], __List[1:]] if __List and not isinstance(__List[0], str) else [0, __List] if __List and __List[0]!=")" else do_raise("unexpect ending of expression")) if __Level==0 else (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) (rf(_t[1][1:], __Level-1)) if _t[1] and _t[1][0] in [{"^"},{"*","/"},{"+","-"}][__Level-1] else _t)) (self, self(__List, __Level-1)))parser=(lambda __List: (lambda ret: ret[0] if not ret[1] else do_raise("unexpect symbol ""+ret[1][0]+""")) (parser_impl(__List)))

這裡我把所有的中間函數expr, expr_add, expr_mul, expr_pow, expr_atom全部整合到parser_impl里去了, 用參數__Level來表示各個中間階段:

__Level0: expr_atom1: expr_pow2: expr_mul3: expr_add

大家不好意思我偷懶了, 把expr_pow當成expr_add和expr_mul一樣處理了, 這樣生成出來的語法樹中冪運算是左結合而不是右結合的, 不過因為冪運算滿足結合律所以不是什麼大問題.

這樣做的好處是非常容易添加新的運算符, 只需要在[{"^"},{"*","/"},{"+","-"}]列表裡添加並安排好__Level就可以了, 並不需要大改語法器.

parser中還進行了一些額外的錯誤處理, 在表達式提前終止時報錯, 比如1+2)+3這類的括弧不匹配情況.

語法器完成啦喵!

Evaluator:

求值器是整個計算姬里最簡單的部分啦喵, 把語法分析器得到的語法樹從上到下遞歸求值就可以了. 若節點為單個數字直接返回數字, 若為中間節點先對左右子節點進行遞歸求值, 然後根據運算符進行計算.

evaluator=wapper(lambda self, _t: { "+":lambda x,y:x+y, "-":lambda x,y:x-y, "*":lambda x,y:x*y, "/":lambda x,y:float(x)/float(y), "^":lambda x,y:x**y, }[_t[0]](self(_t[1]), self(_t[2])) if isinstance(_t, list) else _t)

非常簡單對不對, 代碼非常簡單我就不解釋啦喵.

到這裡了呢, 所有主要部分都完成啦, 補上頭部和尾吧

import redef do_raise(msg): raise Exception("Syntax Error, "+msg+".")wapper=lambda _f: (lambda *_x: _f(wapper(_f), *_x))#...calculator=lambda __Str: evaluator(parser(lexer(__Str)))try: print(calculate(input()))except Exception as e: print(str(e))

最後的最後完整的計算姬誕生啦

import redef do_raise(msg): raise Exception("Syntax Error, "+msg+".")wapper=lambda _f: (lambda *_x: _f(wapper(_f), *_x))lexer=(lambda __Str: list(map(lambda s: int(s) if s.isdigit() else float(s) if re.match(r"^(d+?.d*?|d*?.d+?)$", s) else s if s.find(".")==-1 else do_raise("invaild number"), filter(None, re.split(r"([+-*/()^])", "".join(filter( (lambda c: re.match(r"[d+-*/().^]",c) or not (c==" " or do_raise("unexpect symbol ""+c+"""))), __Str)))))))parser_impl=wapper(lambda self, __List, __Level=3: ((lambda _t: [_t[0],_t[1][1:]] if _t[1] and _t[1][0]==")" else do_raise("expect symbol ")"")) (self(__List[1:])) if __List and __List[0]=="(" else [__List[0], __List[1:]] if __List and not isinstance(__List[0], str) else [0, __List] if __List and __List[0]!=")" else do_raise("unexpect ending of expression")) if __Level==0 else (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [[_t[1][0],_t[0],_t0[0]],_t0[1]])) (rf(_t[1][1:], __Level-1)) if _t[1] and _t[1][0] in [{"^"},{"*","/"},{"+","-"}][__Level-1] else _t)) (self, self(__List, __Level-1)))parser=(lambda __List: (lambda ret: ret[0] if not ret[1] else do_raise("unexpect symbol ""+ret[1][0]+""")) (parser_impl(__List)))evaluator=wapper(lambda self, _t: { "+":lambda x,y:x+y, "-":lambda x,y:x-y, "*":lambda x,y:x*y, "/":lambda x,y:float(x)/float(y), "^":lambda x,y:x**y, }[_t[0]](self(_t[1]), self(_t[2])) if isinstance(_t, list) else _t)calculator=lambda __Str: evaluator(parser(lexer(__Str)))try: print(calculator(input()))except Exception as e: print(str(e))

因為計算姬全是用函數式的方式編寫的, 我們可以還可以喪心病狂的把所有代碼寫在一行里

import redef do_raise(msg):raise Exception("Syntax Error, "+msg+".")wapper=lambda _flambda*_x:_f(wapper(_f),*_x))evaluate=((lambda __Strlambda ret:ret[0]if not ret[1]else do_raise("unexpect symbol ""+ret[1][0]+""")) (wapper(lambda self, __Str, __Level=3: ((lambda _t: [_t[0],_t[1][1:]] if _t[1] and _t[1][0]==")" else do_raise("expect symbol ")"")) (self(__Str[1:])) if __Str and __Str[0]=="(" else [(lambda s: int(s) if s.isdigit() else float(s) if re.match(r"^(d+?.d*?|d*?.d+?)$", s) else s if s.find(".")==-1 else do_raise("invaild number") )(__Str[0]), __Str[1:]] if __Str and __Str[0][0] and (__Str[0][0].isdigit() or __Str[0][0]==".") else [0, __Str] if __Str and __Str[0]!=")" else do_raise("unexpect ending of expression")) if __Level==0 else (wapper(lambda self, rf, _t: (lambda _t0: self(rf, [{ "+":lambda x,y:x+y, "-":lambda x,y:x-y, "*":lambda x,y:x*y, "/":lambda x,y:float(x)/float(y), "^":lambda x,y:x**y, }[_t[1][0]](_t[0],_t0[0]),_t0[1]])) (rf(_t[1][1:], __Level-1)) if _t[1] and _t[1][0] in [{"^"},{"*","/"},{"+","-"}][__Level-1] else _t)) (self, self(__Str, __Level-1))) ((lambda s, regret: list(filter(None, re.split(r"([+-*/()^])", s.replace(" ","")))) if not regret else do_raise("unexpect symbol ""+regret.group(0)+"""))(__Str,re.search(r"[^d+-*/().^ ]",__Str))))))try: print(evaluate(input()))except Exception as e: print(str(e))

當然啦, 來源於計算姬的白雪當然也擁有計算姬的所有功能, 需要計算姬的話只需要一行

lambda:f()=input()

文章很長, 謝謝各位耐心閱讀, 希望對大家有幫助.

下次我會向大家介紹如何在計算姬基礎上給她賦予函數

函數的出現, 計算姬就完全變成了解釋器

新的冒險即將開始...

動手寫一門簡單語言吧喵 從計算姬開始

動手寫一門簡單語言吧喵從計算姬開始