前言

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

語(yǔ)法

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

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

或者用 EBNF：

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

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

number ＋ number ＋ number ＋ number

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

［number ＋ number］ ＋ number ＋ number

解析器找到了它的第一個(gè)匹配模式！

［add ＋ number］ ＋ number

在轉(zhuǎn)換成一個(gè)模式之后，它開(kāi)始尋找下一個(gè)

［add ＋ number］

add

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

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

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

這相當(dāng)于：

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

讓我們?cè)谀X海中模擬一下使用這個(gè)神奇的解析器來(lái)分析1＋2＊3＊4的過(guò)程：

number ＋ number ＊ number ＊ number

number ＋ ［number ＊ number］ ＊ number

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

number ＋ ［mul ＊ number］

number ＋ mul

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

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

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

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

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

讓我們來(lái)使用這種新的語(yǔ)法來(lái)模擬運(yùn)行一下1＋2＊3＊4：

number ＋ number ＊ number ＊ number

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

number ＋ ［number］ ＊ number ＊ number

number ＋ ［mul ＊ number］ ＊ number

number ＋ ［mul ＊ number］

［number］ ＋ mul

［mul］ ＋ mul

［add ＋ mul］

add

成功了！��！

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