在Parser里確定運算符的優先順序(以Python語言設計為例

01-31

運算優先順序其實是很好解決的一件事情。

通常的做法應該是在Parser里定死吧。當然，也是有語言可以自由定製運算符優先順序的，實現起來也非常簡單。

今天我就寫一下如何在Parser里確定運算符的優先順序。

這篇文章以一個Python表達式的簡化版本為教程。

花幾分鐘看完這篇文章，你離手寫Python的Parser只剩下願不願意的距離了。

首先我們先假設有一個東西，是最高階的表達式，它就是我們需要的那個Ast單位。

為了顯得官方一點，我就按照CPython的命名，把這樣一個Ast稱作Test。

但是我們也有一些字面量，字面量以各種方式的組合形成了Ast。

下面是一些字面量Parser的定義。

Number := Rd+|d*.d+n# 這個一看就是int或者double。 n# 浮點數的正則比較麻煩，詳見Cm-lang/Cm-Document/Ebnfn# https://github.com/Cm-lang/Cm-Document/blob/master/Ebnf/Grammarn# Decimal 字面量Parser的定義nnConst := RTrue(?!S)|False(?!S)|None(?!S)n# 一些常量。為什麼不直接是True，原因稍微複雜一點點，因為它會加入tokenizer的生成規則里。n# 想知道這個規則可以私我或者等我出文檔。n# 如果不加(?!S), 一個叫做TrueObj的變數可能被token拆成 True 和 Obj兩個東西。n# 但其實你也可以不寫(?!S)，不過token就需要你手動寫了。n# 我想token應該對一個稍微學過這方面的人來說都應該非常簡單。nnName := R[a-zA-Z_][a-zA-Z0-9]*n# 符號nNEWLINE := n # 換行符。n

然後我們需要定義一個作為原子的AstParser.

Atomt::= Number | Const | Name n

我們現在是這麼考慮的，之後可以再修訂，非常簡單。

好的，現在我們來考慮優先順序。

容許讓我把位運算省略，作為一個假程序員，我不懂位運算，每次他們說什麼快速冪我都看不懂。

我給出一些運算符和一些操作。

函數調用 some(args...)nC風格的下標取值 some[args...]n符號 +some -somen加減 + - n乘除取余 * / %n單目邏輯運算符 notn雙目邏輯運算符 and orn

來，想一下這個優先順序。。

我翻個頁，趁著看不到官方的做法，看官不妨自己想一下(當然我知道有人是可以秒的。

好，我說這樣更合理。

小括弧最優先。。。
函數調用和取下標同級，屬於最優先的操作。
取符號是第二優先的。
乘除取余同級，第三優先。
單目邏輯運算第四優先。
雙目邏輯運算中and第五優先, or第六優先。

arr = [1, 2, 3]nfunc = lambda x, y : x+ynn+ arr[0] 是 + ( arr[0]) n1 - -+2 是 1 + (-(-(+2)))n1 + 2*3/5 是 1 + (2 * 3 / 5)nnot func(1) and arr[0] + 2 or arr n 是 ( (not func(1)) and (arr[0] + 2) ) or arr n

怎麼實現呢，我們從優先順序最高的寫起。為什麼呢？

(不想聽分析想直接看代碼的請跳到下一次分割線。

因為實際上，解析是一個連續的過程(你想想一下parser在連續的可能性中跳躍)，

a ::= b c | d e nb ::= e f n你的解析器解析在a的時候，一定是從a滑到e，而不是像發神經一樣，從a因為一個原因就莫名跳到e。n

優先順序高的要相互結合，那就是連續處理的——處理完了第1級的一個結果A後，中間再處理一些1到2優先順序的結果，才能處理第3級的一個結果B，而不可能從第1級直接跳到第3級，這算是介值定理這個普遍抽象的一個具現。

而從把第一級的一個結構A處理一半，然後到第二級B處理一些東西，再到其他第一級A里去處理一些東西，又回到A再繼續處理，這個需求並不總是有的。因為在你的parser跳動的時候，可以有一個東西(記為R)記錄之前的狀態，當A需要某個狀態的知識時候，直接從R裡面拿出來就行。雖然這不能滿足所有關於parser的幻想，但它應當是這些幻想里比較高效(也許是最高效)的那個。

接下來，來看我寫完這個解析器，順便解析一些python代碼吧。

Atom ::= Number | Const | Name | ( Test )n

P.S : 括弧可以強制改變優先順序到最高。

函數調用或者去下標。

AtomExpr ::= Atom Trailer*nTrailer ::= [ Test (, Test)* ] | ( Test (, Test)* )n

給表達式加符號

Factor ::= AtomExpr | (+ | -) Factorn

乘除以及取余

Term ::= Factor ((* | / | %) Factor)*n

邏輯否

NotTest ::= Term | [not(?!S)] NotTestn

邏輯或

OrTest ::= NotTest (or(?!S) NotTest)*n

邏輯與

AndTest ::= OrTest (and(?!S) OrTest)*n

好了.。。

就是這樣。

OrTest和Lambda表達式合起來是Test。

所有的定義，詳見Python的表達式文法。

測試。

如果有興趣，這兒有一個Travis的測試文件

以及測試結果。