簡介

在這篇文章中，我將向大家演示怎樣向一個(gè)通用計(jì)算器一樣解析并計(jì)算一個(gè)四則運(yùn)算表達(dá)式。當(dāng)我們結(jié)束的時(shí)候，我們將得到一個(gè)可以處理諸如 1+2*-(-3+2)/5.6+3樣式的表達(dá)式的計(jì)算器了。當(dāng)然，你也可以將它拓展的更為強(qiáng)大。

我本意是想提供一個(gè)簡單有趣的課程來講解 語法分析 和 正規(guī)語法（編譯原理內(nèi)容）。同時(shí)，介紹一下 PlyPlus,這是一個(gè)我斷斷續(xù)續(xù)改進(jìn)了好幾年的語法解析 接口。作為這個(gè)課程的附加產(chǎn)物，我們最后會(huì)得到完全可替代eval（）的一個(gè)安全的四則運(yùn)算器。

如果你想在自家的電腦上試試本文中給的例子的話，你應(yīng)該先安裝 PlyPlus ,使用命令pip install plyplus  。（譯者注：pip是一個(gè)包管理系統(tǒng)，用來安裝用python寫的軟件包，具體使用方法大家可以百度之或是google之，就不贅述了。）

本篇文章需要對(duì)python的繼承使用有所了解。

語法

對(duì)于那些不懂的如何解析和正式語法工作的人而言，這里有一個(gè)快速的概覽：正式語法是用來解析文本的一些不同層面的規(guī)則。每一個(gè)規(guī)則都描述了相對(duì)應(yīng)的那部分輸入的文本是如何組成的。

這里是一個(gè)用來展示如何解析1+2+3+4的例子：

Rule #1 - add  IS MADE OF  add + number   
                       OR  number + number 

或者用 EBNF:

add: add'+'number  
   | number'+'number  
   ; 

解析器每次都會(huì)尋找add+number或者number+number，找到一個(gè)之后就會(huì)將其轉(zhuǎn)換成add。基本上而言，每一個(gè)解析器的目標(biāo)都在于盡可能的找到最高層次的表達(dá)式抽象。

以下是解析器的每個(gè)步驟：

1.number + number + number + number第一次轉(zhuǎn)換將所有的Number變成“number”規(guī)則

2.[number + number] + number + number解析器找到了它的第一個(gè)匹配模式！

3.[add + number] + number在轉(zhuǎn)換成一個(gè)模式之后，它開始尋找下一個(gè)

4.[add + number]

5.add

這些有次序的符號(hào)變成了一個(gè)層次上的兩個(gè)簡單規(guī)則: number+number和add+number。這樣，只需要告訴計(jì)算機(jī)如果解決這兩個(gè)問題，它就能解析整個(gè)表達(dá)式。事實(shí)上，無論多長的加法序列，它都能解決! 這就是形式文法的力量。

運(yùn)算符優(yōu)先級(jí)

算數(shù)表達(dá)式并不僅僅是符號(hào)的線性增長，運(yùn)算符創(chuàng)造了一個(gè)隱式的層次結(jié)構(gòu)，這非常適合用形式文法來表示:

1 + 2 * 3 / 4 - 5 + 6

這相當(dāng)于:

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

我們可以通過嵌套規(guī)則表示此語法中的結(jié)構(gòu):

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

通過將add設(shè)為操作mul而不是number，我們就得到了乘法優(yōu)先的規(guī)則。 讓我們?cè)谀X海中模擬一下使用這個(gè)神奇的解析器來分析1+2*3*4的過程：

1.number + number * number * number

2.number + [number * number] * number解析器不知道number+number的結(jié)果，所以這是它（解析器）的另一個(gè)選擇

3.number + [mul * number]

4.number + mul

5.???

現(xiàn)在我們遇到了一點(diǎn)困難! 解析器不知道如何處理number+mul。我們可以區(qū)分這種情況，但是如果我們繼續(xù)探索下去，就會(huì)發(fā)現(xiàn)有很多不同的沒有考慮到得可能，比如mul+number, add+number, add+add, 等等。

那么我們應(yīng)該怎么做呢？

幸運(yùn)的是，我們可以做一點(diǎn)小“把戲”：我們可以認(rèn)為一個(gè)number本身是一個(gè)乘積，并且一個(gè)乘積本身是一個(gè)和！

這種思路一開始看起來有點(diǎn)古怪，不過它的確是有意義的：

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

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

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

讓我們來使用這種新的語法來模擬運(yùn)行一下1+2*3*4：

1.number + number * number * number現(xiàn)在沒有一個(gè)規(guī)則是對(duì)應(yīng)number*number的了，但是解析器可以“變得有創(chuàng)造性”

2.number + [number] * number * number

3.number + [mul * number] * number

4.number + [mul * number]

5.[number] + mul

6.[mul] + mul

7.[add + mul]

8.add

成功了?。?！

如果你覺得這個(gè)很奇妙，那么嘗試著去用另一種算數(shù)表達(dá)式來模擬運(yùn)行一下，然后看看表達(dá)式是如何用正確的方式來一步步解決問題的。或者等著閱讀下一節(jié)中的內(nèi)容，看看計(jì)算機(jī)是如何一步步運(yùn)行出來的！

運(yùn)行解析器

現(xiàn)在我們對(duì)于如何讓我們的語法運(yùn)作起來已經(jīng)有了非常不錯(cuò)的想法了，那就寫一個(gè)實(shí)際的語法來應(yīng)用一下吧:

start: add;            // 這是最高層  
add: add add_symbol mul | mul;  
mul: mul mul_symbol number | number;  
number:'[d.]+';      // 十進(jìn)制數(shù)的正則表達(dá)式  
mul_symbol:'*'|'/';// Match * or /  
add_symbol:'+'|'-';// Match + or - 

你可能想要復(fù)習(xí)一下正則表達(dá)式，但不管怎樣，這個(gè)語法都非常直截了當(dāng)。讓我們用一個(gè)表達(dá)式來測試一下吧:

>>>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 

干得漂亮!

仔細(xì)研究一下這棵樹，看看解析器選擇了什么層次。

如果你希望親自運(yùn)行這個(gè)解析器，并使用你自己的表達(dá)式，你只需有Python即可。安裝Pip和PlyPlus之后，將上面的命令粘貼到Python內(nèi)(記得將'...'替換為實(shí)際的語法哦~)。

使樹成形

Plyplus會(huì)自動(dòng)創(chuàng)建一棵樹，但它并不一定是最優(yōu)的。將number放入到mul和將mul放入到add非常有利于創(chuàng)建一個(gè)階層，現(xiàn)在我們已經(jīng)有了一個(gè)階層那它們反而會(huì)成為一個(gè)負(fù)擔(dān)。我們告訴Plyplus對(duì)它們加前綴去“展開”（i.e.刪除）規(guī)則。

碰到一個(gè)@常常會(huì)展開一個(gè)規(guī)則，一個(gè)#則會(huì)壓平它，一個(gè)?會(huì)在它有一個(gè)子結(jié)點(diǎn)時(shí)展開。在這種情況下，?就是我們所需要的。

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 number  
number:'[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 

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

括號(hào)的處理及其它特性

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

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

允許空格出現(xiàn)在表達(dá)式內(nèi)最簡單的方法就是使用這種解釋方式：add SPACE add_symbol SPACE mul | mul;  但個(gè)解釋結(jié)果啰嗦且可讀性差。所有，我們需要令Plyplus總是忽略空格。

下面是完整的語法，包容了以上所述特性：

start: add;  
?add: (add add_symbol)? mul;  
?mul: (mul mul_symbol)? atom;  
@atom: neg | number |'('add')';  
neg:'-'atom;  
number:'[d.]+';  
mul_symbol:'*'|'/';  
add_symbol:'+'|'-';  
WHITESPACE:'[ t]+'(%ignore); 

請(qǐng)確保理解這個(gè)語法再進(jìn)入下一步：計(jì)算！

運(yùn)算

現(xiàn)在，我們已經(jīng)可以將一個(gè)表達(dá)式轉(zhuǎn)化成一棵分層樹了，只需要逐分支地掃描這棵樹，便可得到最終結(jié)果。

我們現(xiàn)在要開始編寫代碼了，在此之前，我需要對(duì)這棵樹做兩點(diǎn)解釋：

1.每個(gè)分支都是包含如下兩個(gè)屬性的實(shí)例：

頭(head)：規(guī)則的名字(例如add或者number);

尾(tail)：包含所有與其匹配的子規(guī)則的列表。

2.Plyplus默認(rèn)會(huì)刪除不必要的標(biāo)記。在本例中，'( ' ，')' 和 '-' 會(huì)被刪除。但add和mul會(huì)有自己的規(guī)則，Plyplus會(huì)知道它們是必須的，從而不會(huì)被刪除它們。如果你需要保留這些標(biāo)記，可以手動(dòng)關(guān)掉這項(xiàng)功能，但從我的經(jīng)驗(yàn)來看，最好不要這樣做，而是手動(dòng)修改相關(guān)語法效果更佳。

言歸正傳，現(xiàn)在我們開始編寫代碼。我們將用一個(gè)非常簡單的轉(zhuǎn)換器來掃描這棵樹。它會(huì)從最外面的分支開始掃描，直到到達(dá)根節(jié)點(diǎn)為止，而我們的工作是告訴它如何掃描。如果一切順利的話，它將總會(huì)從最外層開始掃描!讓我們看看具體的實(shí)現(xiàn)吧。

>>>importoperator as op  
>>>fromplyplusimportSTransformer  
classCalc(STransformer):  
   
    def_bin_operator(self, exp):  
        arg1, operator_symbol, arg2=exp.tail  
   
        operator_func={'+': op.add,  
                          '-': op.sub,  
                          '*': op.mul,  
                          '/': op.div }[operator_symbol]  
   
        returnoperator_func(arg1, arg2)  
   
    number     =lambdaself, exp:float(exp.tail[0])  
    neg        =lambdaself, exp:-exp.tail[0]  
    __default__=lambdaself, exp: exp.tail[0]  
   
    add=_bin_operator  
    mul=_bin_operator 

每個(gè)方法都對(duì)應(yīng)一個(gè)規(guī)則。如果方法不存在的話，將調(diào)用__default__方法。我們?cè)谄渲惺÷粤藄tart,add_symbol和mul_symbol，因?yàn)樗鼈冎粫?huì)返回自己的分支。

我使用了float()來解析數(shù)字，這是個(gè)懶方法，但我也可以用解析器來實(shí)現(xiàn)。

為了使語句整潔，我使用了運(yùn)算符模塊。例如add基本上是 'lambda x,y: x+y'之類的。

OK，現(xiàn)在我們運(yùn)行這段代碼來檢查一下結(jié)果。

>>> Calc().transform( g.parse('1 + 2 * -(-3+2) / 5.6 + 30'))  
31.357142857142858 

那么eval()呢？7

>>>eval('1 + 2 * -(-3+2) / 5.6 + 30')  
31.357142857142858 

成功了:)

最后一步：REPL

為了美觀，我們把它封裝到一個(gè)不錯(cuò)的計(jì)算器 REPL：

defmain():  
    calc=Calc()  
    whileTrue:  
        try:  
            s=raw_input('> ')  
        exceptEOFError:  
            break 
        ifs=='':  
            break 
        tree=calc_grammar.parse(s)  
        printcalc.transform(tree) 

完整的代碼可從這里獲取：https://github.com/erezsh/plyplus/blob/master/examples/calc.py

原文鏈接：http://www.oschina.net/translate/how-to-write-a-calculator-in-50-python-lines-without-eval