簡介

在這篇文章中，我將向大家演示怎樣向一個通用計算器一樣解析并計算一個四則運算表達式。當我們結束的時候，我們將得到一個可以處理諸如 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            OR number + number

或者用 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。這樣，只需要告訴計算機如果解決這兩個問題，它就能解析整個表達式。事實上，無論多長的加法序列，它都能解決! 這就是形式文法的力量。
運算符優先級

算數表達式并不僅僅是符號的線性增長，運算符創造了一個隱式的層次結構，這非常適合用形式文法來表示:

1 + 2 * 3 / 4 - 5 + 6

這相當于:

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

我們可以通過嵌套規則表示此語法中的結構:
 

add: add+mul  | mul'+'mul  ;mul: mul '*; number  | number'*'number  ;

通過將add設為操作mul而不是number，我們就得到了乘法優先的規則。

讓我們在腦海中模擬一下使用這個神奇的解析器來分析1+2*3*4的過程：

  number + number * number * number  number + [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  ;mul: mul'*'number  | number'*'number  | number  ;

但是如果 mul能夠變成 add, 且 number能夠變成 mul ， 有些行的內容就變得多余了。丟棄它們，我們就得到了：
 

add: add'+'mul  | mul  ;mul: mul'*'number  | 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] + mul  [add + mul]  add

成功了！！！

如果你覺得這個很奇妙，那么嘗試著去用另一種算數表達式來模擬運行一下，然后看看表達式是如何用正確的方式來一步步解決問題的。或者等著閱讀下一節中的內容，看看計算機是如何一步步運行出來的！

運行解析器

現在我們對于如何讓我們的語法運作起來已經有了非常不錯的想法了，那就寫一個實際的語法來應用一下吧:

>>>fromplyplusimportGrammar>>> g=Grammar("""...""")>>>printg.parse('1+2*3-5').pretty()start add  add   add    mul     number      1   add_symbol    +   mul    mul     number      2    mul_symbol     *    number     3  add_symbol   -  mul   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 number | number;// Expand mul if it's just a numbernumber:'[d.]+';mul_symbol:'*'|'/';add_symbol:'+'|'-';

在新語法下樹是這樣的：
 

>>> g=Grammar("""...""")>>>printg.parse('1+2*3-5').pretty()start add  add   number    1   add_symbol    +   mul    number     2    mul_symbol     *    number     3  add_symbol   -  number   5

哦，這樣變得簡潔多了，我敢說，它是非常好的。

括號的處理及其它特性

目前為止，我們還明顯缺少一些必須的特性：括號，單元運算符(-(1+2))，及表達式中間允許存在空字符。其實這些特性都很容易就能實現，下面我們來嘗試一下。

需要先引入一個重要的概念：原子。在一個原子里面（括號中及單元運算）發生的所有操作都優先于所有加法或乘法運算（包括位操作）。由于原子只是一個優先級的構造器，并無語法意義，幫我們加上"@"符號以確保在編譯時它被能展開。

允許空格出現在表達式內最簡單的方法就是使用這種解釋方式：add SPACE add_symbol SPACE mul | mul;  但個解釋結果