簡介
在這篇文章中，我將向大家示範怎樣向一個通用計算器一樣解析併計算一個四則運算表達式。當我們結束的時候，我們將得到一個可以處理諸如 1+2*-(-3+2)/5.6+3樣式的表達式的計算器了。當然，你也可以將它拓展的更為強大。
我本來是想提供一個簡單有趣的課程來講解 語法分析 和 正規語法（編譯原理內容）。同時，介紹一下 PlyPlus,這是一個我斷斷續續改進了好幾年的語法解析 介面。作為這個課程的附加產物，我們最後會得到一個完全可取代eval（）的一個安全的四則運算器。
如果你想在自家的電腦上試試本文中給的例子的話，你應該先安裝 PlyPlus ,使用指令pip install plyplus 。 （譯者註：pip是個套件管理系統，用來安裝用python寫的軟體包，具體使用方法大家可以百度之或是google之，就不贅述了。）
本篇文章需要對python的繼承使用有所了解。
語法
對於那些不懂的如何解析和正式語法工作的人而言，這裡有一個快速的概覽：正式語法是用來解析文本的一些不同層面的規則。每一個規則都描述了相對應的那部分輸入的文字是如何組成的。
這裡有一個用來展示如何解析1+2+3+4的例子：
Rule #1 - add IS MADE OF add + number
IS MADE OF add + number
IS MA
或用EBNF: add: add'+'number | number'+'number ;解析器每次都會尋找add+number或number+number，找到一個之後就會將其轉換成add。基本上而言，每一個解析器的目標都在於盡可能找到最高層次的表達式的抽象。 以下是解析器的每個步驟：number + number + number + number第一次轉換將所有的Number變成「number」法則[number + number] + number + number器找到了它的第一個匹配模式！ [add + number] + number在轉換成一個模式之後，它開始尋找下一個[add + number]add這些有次序的符號變成了一個層次上的兩個簡單規則: number+number和add+number。這樣，只需要告訴計算機如果解決這兩個問題，它就能解析整個表達式。事實上，無論多長的加法序列，它都能解決! 這就是形式文法的力量。 運算子優先權| mul'+'mul ;mul: mul '*; number | number'*'number ;透過透過將是換乘為運算規則。 讓我們在腦海中模擬一下使用這個神奇的解析器來分析1+2*3*4的過程：number + number * number * numbernumber + [number * number] * number解析器不知道number+number的結果，所以這是它（解析器）的另一個選擇number + [mul * number]number + mul現在我們遇到了一點困難! 解析器不知道如何處理number+mul。我們可以區分這種情況，但是如果我們繼續探索下去，就會發現有很多不同的沒有考慮到得可能，比如mul+number, add+number, add+add, 等等。 那我們該怎麼做呢？ 幸運的是，我們可以做一點小「把戲」：我們可以認為一個number本身是一個乘積，並且一個乘積本身是一個和！ 這個想法一開始看起來有點古怪，不過它的確是有意義的：add: add'+'mul | mul'+'mul | mul
*'number
| number'*'number
| number
;
但是如果mul能夠變成add, 且number能夠變成mul ， 有些行的內容就變得多餘了。要丟棄它們，我們就得到了：
add: add'+'mul
| mul
;
mul: mul'*'number
語法來模擬運行一下1+2*3*4：
number + number * number * number
現在沒有一個規則是對應number*number的了，但是解析器可以「變得有創造性」
number + [number] * number * number
number + [mul * number] * number
number + [mul * number]
[number] + mul
[mul] + mulul
[number] + mul[mul] + mululadd
成功了！ ！ ！
如果你覺得這個很奇妙，那麼試著著去用另一種算數表達式來模擬運行一下，然後看看表達式是如何用正確的方式來一步步解決問題的。或等著閱讀下一節的內容，看看電腦是如何一步一步運作出來的！
運行解析器
現在我們對於如何讓我們的語法運作起來已經有了非常不錯的想法了，那就寫一個實際的語法來應用一下吧:
start: add; //// 這是最高層
add: add add_symbol mul | mul;
mul: mul mul_symbol number | number;
number:'[d.]+'; // 十進位數字的正規表示式* ';// Match * 或 /
add_symbol:'+'|'-';// Match + or -
你可能想要複習一下正則表達式，但不管怎樣，這個語法都非常直截了當。讓我們用一個表達式來測試一下:
>>>fromplyplusimportGrammar
>>> g=Grammar("""...""")
>>>printg.parse('1+2* 3-5').pretty()
start
add
add
add
1
add_symbol
+
mul
2 mul_symbol * number 3 number 5乾得漂亮!仔細研究這棵樹，看看解析器選擇了什麼層次。 如果你希望親自運行這個解析器，並使用你自己的表達式，你只需有Python即可。安裝Pip和PlyPlus之後，將上面的指令貼到Python內(記得將'...'替換為實際的語法哦~)。 使樹成形Plyplus會自動創建一棵樹，但它並不一定是最優的。將number放入到mul和將mul放入到add非常有利於創建一個階層，現在我們已經有了一個階層那它們反而會成為一個負擔。我們告訴Plyplus對它們加前綴去「展開」（i.e.刪除）規則。 碰到一個@常常會展開一個規則，一個#則會壓平它，一個?會在它有一個子結點時展開。在這種情況下，?就是我們所需要的。 start: add;?add: add add_symbol mul | mul; // Expand add if it's just a mul/?mul: mul mul_symbol '[d.]+';mul_symbol:'*'|'/';add_symbol:'+'|'-';在新語法下樹是這樣的：>>> g== Grammar("""...""")>>>printg.parse('1+2*3-5').pretty()start add add add
add_symbol
+
mul
mul_symbol
*
number
3
5
哦，這樣變得簡潔多了，我敢說，它是非常好的。
括號的處理及其它特性
目前為止，我們還明顯缺少一些必須的特性：括號，單元運算符(-(1+2))，及表達式中間允許存在空字符。其實這些特性都很容易就能實現，下面我們來試試看。 需要先引入一個重要的概念：原子。在一個原子裡面（括號中及單元運算）發生的所有運算都優先於所有加法或乘法運算（包括位元運算）。由於原子只是一個優先順序的構造器，並無語法意義，幫我們加上"@"符號以確保在編譯時它被能展開。 允許空格出現在表達式內最簡單的方法就是使用這種解釋方式：add SPACE add_symbol SPACE mul | mul; 但個解釋結果囉嗦且可讀性差。所有，我們需要令Plyplus總是忽略空格。 下面是完整的語法，包容了上述所述特性：start: add;?add: (add add_symbol)? mul;?mul: (mul multom_symbol)? aul;?mul: (mul multom_symbol)? aul;?mul: (mul multom_symbol)? a neg | number |'('add')';neg:'-'atom;number:'[d.]+';mul_symbol:'*'|'/';add_symbol:' +'|'-';WHITESPACE:'[ t]+'(%ignore);
請確保理解這個語法再進入下一步：計算！
運算
現在，我們已經可以將一個表達式轉換成一棵分層樹了，只需要逐分支地掃描這棵樹，便可得到最終結果。
我們現在要開始寫程式碼了，在此之前，我需要對這棵樹做兩點解釋：
1.每個分支都是包含以下兩個屬性的實例：
頭(head)：規則的名字(例如add或number);
尾(tail)：包含所有與其符合的子規則的清單。
2.Plyplus預設會刪除不必要的標記。在本例中，'( ' ，')' 和 '-' 會被刪除。但add和mul會有自己的規則，Plyplus會知道它們是必須的，從而不會被刪除它們。如果你需要保留這些標記，可以手動關掉這項功能，但從我的經驗來看，最好不要這樣做，而是手動修改相關語法效果更佳。
言歸正傳，現在我們開始寫程式碼。我們將用一個非常簡單的轉換器來掃描這棵樹。它會從最外面的分支開始掃描，直到到達根節點為止，而我們的工作是告訴它如何掃描。如果一切順利的話，它將總會從最外層開始掃描!讓我們看看具體的實現吧。
>>>importoperator as op
>>>fromplyplusimportSTransformer
classCalc(STransformer):
） arg1, operator_symbol, arg2=exp.tail
operator_func={'+': op.add,
'*': op.mul,
returnoperator_func(arg1, arg2)
number =lambdaself, exp:float(exp.tail[0]) exp exp.tail[0] __default__=lambdaself, exp: exp.tail[0]
mul=_bin_operator
每個方法對應一個規則。如果方法不存在的話，將會呼叫__default__方法。我們在其中省略了start,add_symbol和mul_symbol，因為它們只會回傳自己的分支。
我使用了float()來解析數字，這是個懶方法，但我也可以用解析器來實現。
為了讓語句整潔，我使用了運算子模組。例如add基本上就是 'lambda x,y: x+y'之類的。
OK，現在我們運行這段程式碼來檢查結果。
ifs=='':
break
tree=calc_grammar.parse(s)
() tree
https://github.com/erezsh/ plyplus/blob/master/examples/calc.py
