所有代碼見於Here

運算符優先順序，描述二元中綴運算中，進行約歸計算的先後次序。

1 + 2 - 3 / 4 * 5 % 6 => (1 + 2) - (((3 / 4) * 5) % 6)

這個運算符優先順序啊，有好些語言都是定死的。

Kotlin Grammar

additiveExpression (used by rangeExpression) : multiplicativeExpression (additiveOperation multiplicativeExpression)* ;multiplicativeExpression (used by additiveExpression) : typeRHS (multiplicativeOperation typeRHS)* ;

CPython Grammar

comp_op: <|>|==|>=|<=|<>|!=|in|not in|is|is notstar_expr: * exprexpr: xor_expr (| xor_expr)*xor_expr: and_expr (^ and_expr)*and_expr: shift_expr (& shift_expr)*shift_expr: arith_expr ((<<|>>) arith_expr)*arith_expr: term ((+|-) term)*term: factor ((*|@|/|%|//) factor)*factor: (+|-|~) factor | powerpower: atom_expr [** factor]

但是呢，其實不定死也是很好做的，並且於解釋器和編譯器也沒有任何害處(可能是因為擔心人濫用優先順序，隨意修改導致可讀性很差。

那我們今天來做什麼呢，兩件事，理論加實際。

理論就是給出一個優先順序處理的幾個解決方案，講述為什麼要這麼解決，並且實現它們。

實現就是寫計算器唄。

(你秒完計算器可以給我今天推薦的工具打個廣告，就說，只需體驗三分鐘，你就會愛上這款框架。

1. 過程。

1 + 2 ** 3 * 4 /* 我們引入一個符號"**"用來表示乘方。*/

優先順序，字面意思，誰的值比較高，先處理誰。

我們定一個值的序關係:

(**) > (*) > +

我們來看，誰最高，"**"最高，那麼先處理"**".

1 + (2 ** 3) * 4

此時，(2**3)內部不用你在管了，它已經成了一個整體，括弧裡面的計算沒有次序衝突。

記它為A.

接下來，還有

1 + A * 4

誰最高，"*"最高。好

B = (A * 4)原式 = 1 + B

廢話般的過程就很清楚了。

所以我們下面有兩種辦法解決優先順序問題，一個是定死的優先順序, 另一個就沒定死。

我們下面選用如下的二元運算符以及數字(整數和小數)，描述計算器文法。

+, -, *, /, //, ** // 表示整除行吧？

2. 定死的方法

我還是指定一下本系列專用parser框架。

船新版本只支持Python的3.6及以上版本(for type hinting)，1.1版本可以支持3.4及以上的。

我這裡只給船新版本的，船新時來到就是賺到。（語法有不懂的請直接問我... 實際上這語法完全衍生自CPython所用的pgen前端。其實我當時看他們那個，也沒啥context就直接看懂了）

首先我們定義數字的字面量(literal)。

number := Rd+; # := 定義的是一個詞法結構。通常它是含類型的，但我們這次不用考慮。decimal ::= number [. number]; # ::= 定義的是一個語法結構。

我們看一下這東西有什麼效果。把上面寫的代碼放到calc.ruiko裡面。

ruiko calc.ruiko calc_parser --test# ruiko <語法文件> <parser generated here> [--test 提供語法測試腳本]

然後我們來測一下語法。

python test_lang.py decimal "1.2"# python test_lang.py <語法結構> "<DSL代碼>" [--testTk 列印分詞結果]

parse成功。現在我們回到calc.ruiko裏來，根據優先順序添加算術語法。

我們們先確定一個最低級的語法結構，很多語言都有，叫做atom。然後又假設一個最高級的，在這裡我們是一個算數計算的結果，所以可以叫arith.

atom ::= decimal | ( arith );

當一個最高級的東西被一個括弧包裹起來，這個包含括弧的整體就可以作為一個最低級的語法結構了。

然後，我們看這樣的表達，-1, +(1 * 2 - 3), -(1 + 2 - 3)。

所以atom上其實可以加一個符號，對吧。

factor ::= [-|+] atom;

factor表示的是一個可以有前綴的atom。

然後，就是最高優先順序的二元運算, **。

power ::= factor (** factor)*;

指數和底數均結合最近的**，不是嘛？

然後，優先順序次一級的，乘除法

mulDiv ::= power (// power|/ power|* power)*;/*PS: 以上代碼實際上和 mulDiv ::= power ((//|/|*) power)*; 等價*/

然後加減法亦然, 不過加減法就是最頂層的東西了，所以它就是arith。這件事情，一般要接近寫完語法定義的時候才能發現。

arith::= mulDiv (+ mulDiv|- mulDiv)*;

好，我們現在成功的表達了具有優先順序的二元運算，讓我們看看結果。

首先，還是編譯一下。

ruiko calc.ruiko calc_parser --testpython test_lang.py arith "1312+3*4"

仔細看輸出，尤其看運算符所在的層級。

注意，這個tokenizer沒有正確的處理空白字元，如果你想輸入 "1 + 2 * 3"而非 "1+2*3"把下面這兩行放到文件前面。 ignore[space] space := Rs+;

以上，就是一個簡易計算器的語法parser.

但是這不是我們的正題，因為對這個我以前是發過文章的。

我們要做的是處理下面這個文法解析出來的結構。

calc_oppt.ruiko

ignore [space]space := Rs+;number := Rd+; decimal ::= number [. number];atom ::= decimal | ( arith );factor ::= [-|+] atom;arith ::= factor ((+ | - | ** | * | // | /) factor)*;

注意看arith的定義，我們不在文法裏規定優先順序，這使得，我們可以在語言中動態的修改優先順序。

先測試一下上面的語法。

ruiko calc_oppt.ruiko calc_oppt_parser.py --testpython test_lang.py arith "1312 + 3 * 4"

可以看到生成的ast裏是沒有優先順序概念的。

3. 沒有定死的方法

好，我們直接來寫計算器的解釋器。

在這個有calc.py的目錄下，新建一個文件取名calc.py然後這樣來。

下面使 calc.py的一個簡略描述

from Ruikowa.ObjectRegex.ASTDef import Astfrom Ruikowa.ErrorHandler import ErrorHandlerfrom numbers import Numberfrom calc_oppt_parser import *src_code_token_parse = ErrorHandler(arith.match, token_func).from_source_codedef parse(src: str) -> Ast: filename = <my calculator> return src_code_token_parse(filename, src)def ast_for_decimal(decimal: Ast) -> Real: passdef ast_for_arith(arith: Ast) -> Real: passdef ast_for_factor(factor: Ast) -> Real: passdef ast_for_atom(atom: Ast) -> Real: passclass DoublyList: passdef repl(): while True: try: inp = input(my_calc:: ) print(ast_for_arith(parse(inp))) except KeyboardInterrupt: print(
bye) import sys sys.exit(0)

這個ast_for_xxx的東西是我在python源碼裏學的，好用的一匹。。。這個都是套路，但是今天不講，我就只把定義放這兒。重申，今天所有代碼可以在calc文件夾下看到。

關鍵問題是，當我們拿到一個arith之後，我們知道裡面都是一個個factor的加減乘除。

那怎麼正確的按照優先順序求值呢？

記不得上面第一節過程裏講了啥的，回去看看，這個過程。描述的是解析優先順序不同的二元運算符。

誰最高，先做誰。消除其兩端，三個化為整體。

好的，那不就是，把這些平坦的二元運算符根據優先順序排個降序。不停從當前優先順序最高的符號節點開始，每次處理其左右兩項的二元運算，然後合為一項。

這個吧，其實有個雙向鏈表比較高效。我至今還沒有做到一個高效又強力(支持各種lazy)的雙向鏈表，這裡隨手寫一個，還是放到calc.py裏。

Python codes: 全代碼見這裡，還是很舒服整潔的。下面是根據運算符優先順序表來處理二元運算的關鍵函數。

@currydef fmap(t, func): return lambda *args: func(*map(t, args))def visit_bin_expr(func, seq: DoublyList[AstParser]): def sort_by_func(e: DoublyList[Tokenizer]): return op_priorities[e.content.string] # 在解析ast的範疇上進行二元函數調用 functor = fmap(func) # 先只取運算符節點。通過每個運算符節點的前驅後繼可以訪問factor項 op_nodes = (each for each in seq if each.content.name is not UNameEnum.factor) # 根據優先順序進行降序 op_nodes: DoublyList[Tokenizer] = sorted( op_nodes, key=sort_by_func, reverse=True) # 從優先順序大到小一次進行約歸。 for each in op_nodes: # 對當前未約歸的最優先的運算符，求值左右兩項的二元運算 bin_expr = functor(op_func[each.content.string])(each.prev.content, each.next.content) # 下面的事情就是， # 把當前運算符節點的值修改成為左右兩項二元運算結果。 # 作用是使運算符節點，成為由其與其左右二項約歸後的整體。 each.content = bin_expr try: # try 比if快是python特有的。。別學 each.prev.prev.next = each each.prev = each.prev.prev except AttributeError: pass try: each.next.next.prev = each each.next = each.next.next except AttributeError: pass each: DoublyList[Real] return each.content

然後這就是最後的交互界面。想來很二，寫了接近100行的有效代碼就為了寫個計算器。。

/* 最後強插一段rem的代碼來描述 */let arith_lst = arith . toDoublyListlet op_priorities = %{ "+": 1, "-": 1, "*": 2, "/": 2, "//":2}arith_lst . filter{ # 選取 所有的運算符節點 |factor_or_op| factor_or_op.Name is not UNameEnum.factor} . sortedDescend { # 根據優先順序排降序 |op| op_priorities![op.string]} . foreach { # 每個節點約歸 |op| let bin_expr = visit opprevcontent opcontent opnextcontent op.content = bin_expr # 運算符兩邊一定會有項的 ... 所以next, prev一把梭 let l = "prev" let r = "next" macro # 三個作為整體，其前驅的後繼修改為三個的整體。 l = "next" r = "prev" macro # 三個作為整體，其後繼的前驅修改為三個的整體。 } . snd # 取第二個，一定是約歸好了的值 where let macro = `if {op.getl .get l !=None}{ op.get l . get l . set r op op.set l $ op .get l .get l } let visit = {|l, m, r| case m as "+" => l + r, as "-" => l - r, as "*" => l * r, as "/" => l / r, as "//" => l // r end } end

推薦閱讀：

相關文章