基于編譯原理的計算器設(shè)計與實現(xiàn)

1、基于編譯原理的計算器設(shè)計與實現(xiàn)首先看一下這個計算器的功能：CALC> set a = 1; b = 2CALC> set c = 3CALC> calc (10 + pow(b, c) * sqrt(4) - 135.0CALC> exit 如上所示，這個計算器的功能非常簡單：1. 用 set 命令設(shè)置上下文中的變量。2. 用 calc 命令計算一個表達(dá)式的值。3. 用 exit 命令退出計算器。我們把編譯的重點放在 calc 命令后面的計算表達(dá)式的解析， 其它的部分我們可以簡單處 理(如 set 命令可以這樣簡單處理：先按分號分隔得到多個賦值處理，再按等號分隔就可以

2、在上下文中設(shè)置變量了，并不需要復(fù)雜的編譯過程) 。如上的演示例子中，我們使用編譯技術(shù)處理的部分是(10 + pow(b, c) * sqrt(4) - 1 ，其它部分我們只使用簡單的文本處理。麻雀雖小， 但五臟俱全， 這個計算器包含編譯技術(shù)中最必要的部分。 雖然這次我們只是 實現(xiàn)了一個計算器，但所使用的技術(shù)足以實現(xiàn)一個簡單的腳本語言的解釋器了。這個計算器分為如下幾個部分： 詞法分析：把表達(dá)式的文本，解析成詞法元素列表(tokenList) 。語法分析：把 tokenList 解析成語法樹 (syntaxTree)。 語義分析：把語法樹轉(zhuǎn)成匯編語言的代碼 (asm) 匯編器：把匯編代碼翻譯為機器

3、碼(字節(jié)碼) 。虛擬機：執(zhí)行字節(jié)碼。 一般的編譯步聚中不包含 “匯編器 ”和 “虛擬機 ”，而這里之所以包含這兩個部分是因為： 通常編譯器會直接由中間代碼生成機器碼， 而不是生成匯編代碼， 而這里我之所以要生 成匯編代碼的原因是 “調(diào)試的時候匯編的可讀性很好 ”，如果直接生成目標(biāo)代碼， 則會非常難 用肉眼來閱讀。自己實現(xiàn)虛擬機的原因是： 現(xiàn)有的機器 (包括物理機和虛擬機以及模擬器) 的指令雖然 也很豐富，但似乎都沒有直接計算 “乘方 ”或“開方 ”的指令，自已實現(xiàn)虛擬機可以任意設(shè)計計 算指令，這樣可以降低整個程序的復(fù)雜度。因匯編器與虛擬機并不是編譯原理的部分， 所以下文中并不會描述其實現(xiàn)細(xì)節(jié)，

4、 但因為 計算器代碼編譯后的目標(biāo)代碼就是匯編代碼， 所以需要把匯編指令做一下說明 (以下把這個 匯編語言簡稱為 ASM)。ASM指令介紹指令助記符操作數(shù)指命說明storenumber把number放入棧頂add從棧頂取出兩個數(shù)相加，并把結(jié)果壓回棧中sub從棧頂取出一個數(shù)做為被減數(shù)，再取一個做為減數(shù)，相減之后的結(jié) 果入棧mul從棧頂取出兩個數(shù)相乘，并把結(jié)果入棧div從棧頂取出一個數(shù)做為除法的分子，再取出一個做為除法的分母， 相除的結(jié)果入棧pow從棧頂取出一個數(shù)做為底，再取出一個做為幕，計算結(jié)果入棧sqrt從棧頂取出一個數(shù)，把這個數(shù)開平方后的結(jié)果入棧print在控制臺打印棧頂?shù)臄?shù)字這個虛擬機是基于

5、棧來設(shè)計的，所有的計算指令的操作數(shù)都從棧中取，store命令向棧頂添加數(shù)據(jù)。print指令用于打印當(dāng)前棧頂?shù)臄?shù)據(jù)，在我們編譯的匯編代碼要做到：正確計算出結(jié)果， 且計算完成之后的結(jié)果要剛好在棧頂，這樣最后調(diào)用一個print指令即可以控制臺看到計算結(jié)果。ASM舉例：例1，如果我們要計算1-2*3，則我們寫出的匯編代碼如下（行號是為下文解釋代碼方 便而放上去的，不是代碼的一部分）：點擊（此處）折疊或打開store 3store 2mulstore 1subprint對這段代碼的說明如下：前兩行向棧頂添加兩個數(shù)字，先壓入3再壓入2,這樣棧頂?shù)臄?shù)字是2,第二個數(shù)字是3。第三行mul會從棧頂彈出兩個數(shù)字（

6、2和3）計算乘法，并把結(jié)果（6）再壓入棧中， 此時棧中只有一個數(shù)字6。第四行向棧頂壓入一個數(shù)字1,此時棧頂為1，第二個數(shù)字是6。第五行sub指令從棧頂取出兩個數(shù)字，第一個數(shù)字1做為被減數(shù)，第二個數(shù)字6做為減數(shù)，即計算1-6，并把結(jié)果壓入棧中，此時棧中只有一個數(shù)字-5。最后一行print指令不對棧做寫操作，只讀取棧頂?shù)臄?shù)字，并打印出來。在這里，我們用到兩個運算，mul和sub，這兩個運算都是二元運算，因我在設(shè)計指令的時候，先取出來的數(shù)字是第一個操作數(shù)，所以先壓入的應(yīng)該是第二個操作數(shù)，這也是為什么代碼中先壓入的是 3,之后是2，最后才是1。例2，如果我們要計算（10 + pow（2, 3） * s

7、qrt（4） - 1 ，則我們寫出的匯編代碼如下（行號是為下文解釋代碼方便而放上去的，不是代碼的一部分)：點擊(此處)折疊或打開store 1store 4sqrtstore 3store 2powstore 10addmulsubprint對這段代碼的說明如下：這段代碼稍有點復(fù)雜，但有前一段代碼的經(jīng)驗，我們可以看到，所有的操作數(shù)的先后順 序是從右向左 store的，所以store指令的順序是固定下來的，剩下的關(guān)鍵是操作指令應(yīng)該 放在哪里。操作指令也是有一個規(guī)律的，即:當(dāng)前棧頂?shù)臄?shù)據(jù)剛剛好滿足某運算時，則操作指令就放在哪里，如：store 1的時候沒有任何操作的操作數(shù)都在棧中。store 4的

8、時候，剛剛好sqrt的操作數(shù)都在棧中，則此時加入sqrt指令。store 3 store 2時，剛剛好可以計算 pow。store 10之后，就可以計算加法了，所以此時加入add指令。add計算完成之后，再加上之前已計算完的sqrt指令，則此時乘法的所有操作數(shù)都在棧中了，則此時加入 mul指令。最后減操作也可以計算了，則加上sub指令。所有計算完成之后打印出結(jié)果。在這個例子中，我所說的規(guī)律”其實就是 后綴表達(dá)式”。我們平常寫的算術(shù)表達(dá)式是中綴”的，即符號在操作數(shù)中間，女口1 + 2，的+在1和2中間，轉(zhuǎn)為后綴形式即為1 2 +這里因為我對于參數(shù)順序的設(shè)計是與正?！表樞蛳喾吹模?+2對于這個

9、匯編器來說，其后綴形式就應(yīng)該為21 +大家是可以按照這個規(guī)律，相對簡單的實現(xiàn)這個計算器一一只要做好詞法分析就可以按 照后綴表達(dá)式的規(guī)律直接由 tokenList生成匯編代碼了 一一但我們的目的是用這個計算器的 例子來講編譯，所以還是按步就班來講。詞法分析詞法分析的目的是把一段文本分解成詞法元素列表，例如(10 + pow(2, 3) * sqrt(4) - 1 ，做詞法分析之后會分解成如下幾個詞法元素:在編譯原理中，普遍的方式是用如下一個狀態(tài)轉(zhuǎn)換圖來實現(xiàn)的在圖中，橢圓形”的是狀態(tài)，狀態(tài)與狀態(tài)之間有一條有方向的線，這個線代表從一個狀 態(tài)到另一個狀態(tài)的路徑，在這條線上面有一個花括號代表從前一個狀態(tài)

10、到達(dá)后一個狀態(tài)的輸入（為方便表示，0-9表示從0到9十個數(shù)字，a-z表示從a到z二十六個字母等），如從 START犬態(tài)開始，輸入一個數(shù)字1,就會到達(dá)INT狀態(tài)。圖中藍(lán)色的狀態(tài)是終結(jié)狀態(tài)， 如果從START狀態(tài)經(jīng)過若干輸入后到達(dá)終結(jié)狀態(tài)，則這些輸入的字符可合并為詞法的合法單詞一一這里需要額外說明一點：在對輸入進(jìn)行匹配狀態(tài)時 采用貪婪方式，即：盡量輸入更多的字符。在識別到一個合法的詞法單元之后，狀態(tài)回到START!續(xù)識別下一個元素，直到?jīng)]有新的元素為止。這個狀態(tài)轉(zhuǎn)換圖在編譯原理中有一個專有名詞稱呼它確定有限狀態(tài)自動機 ”英文簡稱DFA。這里 確定”的意思是每一個狀態(tài)經(jīng)過一個輸入字符可以確定只有一條

11、路徑到達(dá)另一個狀態(tài)，有限”的意思是，狀態(tài)的個數(shù)是有限的。對于一個復(fù)雜語言的狀態(tài)數(shù)量是這個狀態(tài)機 的幾個數(shù)量級的大小。但我們現(xiàn)在的計算器只需要這幾個狀態(tài)就夠了。通常的DFA會由工具讀取正則方法描述而生成的，而不是直接手工構(gòu)造，但對我們現(xiàn) 在設(shè)計的計算器來說，其 DFA非常小，手工構(gòu)造是很方便的，所以就不用工具了。另外， 如果使用工具的話，我這篇文章也不會使用現(xiàn)有的工具，而是自己實現(xiàn)一個工具。下面舉個例子：我們有一個表達(dá)式12.3 + abc,下面我來描述一下 DFA的運行過程：定義一個變量s,來表示當(dāng)前狀態(tài)機所在的狀態(tài)（初始時s = STAR）輸入第一個字符1，此時START犬態(tài)可接受這個輸入

12、1，到達(dá)INT狀態(tài)，則變量s賦值 為INT狀態(tài)，此時可看到INT狀態(tài)的顏色是藍(lán)色表示當(dāng)前可識別為一個合法的詞法元素，但 因為我們的規(guī)則是貪婪匹配，所以我們還要看看是否還能夠匹配更多的字符。輸入第二個字符2,此時INT狀態(tài)也可以接受這人輸入，并到達(dá) INT狀態(tài)（轉(zhuǎn)了一個圈 又回到原來的狀態(tài)），此時變量s賦值為INT狀態(tài)。再輸入第三個字符 ，此時INT狀態(tài)可接受.到達(dá)NUMBER狀態(tài)，此時變量s賦值為 NUMBER 狀態(tài)。此時我們再向前看一個字符+，此時的狀態(tài)NUMBER無法接受這個字符了，同時我們可在看到 NUMBER 狀態(tài)的顏色是藍(lán)色的，表示當(dāng)前狀態(tài)可識別一個合法的詞法元素，即： 從START

13、開始到當(dāng)前我們一共經(jīng)歷的輸入為12.3，則這個單詞做為第一個合法的詞法元素。第一個詞法元素識別成功之后， 變量s要回到START狀態(tài)，并繼續(xù)輸入+，此時從START 狀態(tài)可到達(dá)ADD狀態(tài)，且ADD狀態(tài)并不允許接受任何輸入，同時ADD狀態(tài)的顏色也是藍(lán)色的，則我們又識別出第二個詞法元素 + 。在識別到第二個詞法元素之后，變更s要回到START狀態(tài)，并繼續(xù)輸入 a,此時START狀態(tài)可由a指向的路徑到達(dá)ID狀態(tài)，此時s賦值為新的狀態(tài)ID?，F(xiàn)在的情況與識別 NUMBER 的情況類似,當(dāng)前的狀態(tài)也是終結(jié)狀態(tài),但按貪婪匹配的 原則還要繼續(xù)看看是否可以匹配到新的輸入。后面的 b 和 c 都在 ID 一個狀態(tài)

14、里轉(zhuǎn)圈,我就不在贅述了,這樣我們就識別到了最后一 個詞法元素 abc 了。用如上過程的方法可以識別任何正確的算術(shù)表達(dá)式,但還有幾點需要特別說明： 如何識別錯誤： 目前我見過的語言規(guī)范都在描述如何正確的編譯一個語言,但沒有一個規(guī)范有描述如何報錯的,所以我們目前能做的是只要按正常的走法走不通了,那就是錯了, 就要報錯,并盡可能提供詳細(xì)的錯誤信息。對空白的識別：我在DFA中并沒有畫識別空白的部分，原因是對于計算器程序來說，空白完全沒有用處,所以我只是在代碼中直接忽略這個輸入,以免狀態(tài)機無法識別空白,同時在識別到詞法元素之后,去掉單詞前后的空白。對于某些語言來說,空白是有意義的, 需要做為詞法元素識別

15、出來,不能忽略掉。對于詞法元素的表示：通常我們會用一個類型Token來表示一個詞法元素，Token中有兩個屬性,一個用于表示這個 Token 的類型,另一個用于表示內(nèi) 容,只有數(shù)字與標(biāo)識符才 需要使用Token類型的內(nèi)容屬性，其它的類型因為同一類型只有一種表示的可能，所以就不需要再把內(nèi)容保存下來了（如 ADD的內(nèi)容 一定是+）。關(guān)于標(biāo)識符：DFA中的ID狀態(tài)用于識別標(biāo)識符，這里的標(biāo)識符包括自定義的變量，也包括函數(shù)名。在DFA的設(shè)計過程中，我們可以選擇把普通標(biāo)識符與保留字做為不同的狀態(tài)，也可以用使用同一個狀態(tài)。我們現(xiàn)在的設(shè)計就使用了一個ID 狀態(tài)表示所有的標(biāo)識符,而在識別到一個ID之后，我們在看

16、是否是一個保留字，這樣在返回Token對象時設(shè)置不同的類型。對于INT和NUMBER：這個計算器的所有計算都使用的是double類型的數(shù)字，所在雖然我們的詞法可以識別到INT，但我們定義Token的類型時，就只定義一個 NUMBER類型，INT或NUMBER狀態(tài)確定的單詞都返回 NUMBER這個類型的Token對象。前面的邏輯中有一個貪婪批配的原則, 這個原則在某些語言的詞法中會有一些特例不適 用，例如在C+和 JAVA中都有一個運算符 “>>；'這個運算符代表右移，但在C+11標(biāo)準(zhǔn)中可以寫出這樣的代碼 std:vector<std:vector<int>

17、> ,在 JDK5 及以上版本也可以這樣寫 List<List<l nteger>>，這里如果按貪婪批配就錯了。所以必須在詞法分析中加入上下文的判斷 才能決定是按兩 個>來識別還是按一個 >>來識別 上下文的判斷是語法分析的部分了,但對于復(fù)雜的詞法結(jié)構(gòu)在沒有一個統(tǒng)一的詞法解析算法可以處理的情況下就得借助更高級的方法了?，F(xiàn)在剩下的就是寫代碼了。如果我把代碼貼在這里就太長了，不太合適。所以下面我只描述一下描述DFA的思路：思路一： 直接靜態(tài)代碼來描述, 類似這樣的方式把狀態(tài)機的每個路徑都描述出來： IF S =START AD c ='1&#

18、39; THEN S = INT . EL這樣就可以輸入運行了。思路二：表格驅(qū)動式的，例如列出下面的表格即可知道哪個狀態(tài)經(jīng)過哪個輸入之后到達(dá) 哪個新的狀態(tài)了 一一下表的左標(biāo)題是當(dāng)前的狀態(tài)， 上標(biāo)題是在當(dāng)前狀態(tài)上的輸入，表格中的內(nèi)容是經(jīng)過路徑到達(dá)的狀態(tài)。思路三：結(jié)合前兩個思路 一一先寫一個代碼生成工具，工具讀取思路二”中表格中的內(nèi)容，并生成 思路一 ”中的靜態(tài)代碼。0-9_a-zA-Z+-*/()5STARTNTPOINTIDADDSUBMULDIVLBTRBTCOMMAINTNTNUMBERPOINTNUMBERNUMBERNUMBERIDDIDADDSUBMULDIVLBTRBTCOMMA下

19、面舉一下 DFA返回的 Token對象的類型：NUM，F(xiàn)UN, VAR, ADD, SUB, MUL, DIV, LBT，RBT COMMA這里前三個與DFA的狀態(tài)名不同：NUM代表INT狀態(tài)和NUMBER狀態(tài)兩個狀態(tài)識別出的詞法元素。FUN和VAR都是ID狀態(tài)識別出的元素， 如果這個ID是一個函數(shù)名，則Token為FUN類 型，否則即為VAR類型。其它類型與 DFA的狀態(tài)是對應(yīng)的。最后說一下DFA的接口：假設(shè)DFA有一個方法叫做parse,則這個方法的參數(shù)只有一個字符串用于傳入表達(dá)式即 可。如果我們寫的 DFA是用于解析長文本的（而不僅僅是解析這個簡短的算術(shù)表達(dá)式），則可以考慮參數(shù)為輸入流。

20、parse方法的返回可以考慮返回一個 Token的游標(biāo)，游標(biāo)供語法分析程序調(diào)用；也可以 考慮解析完所有的詞法元素返回一個 Token的列表。因為目前比較通用的語法分析算法只需 要向前看一個Token對象，所以游標(biāo)就足夠了。因為語法分析程序有可能會把已讀出來的Token放回去，下次再用，所以游 標(biāo)可考慮加一個putBack方法一一也可以考慮不實現(xiàn)這個方法，而由語法分析程序自己緩存當(dāng)前用不 到的詞法元素 一一如果DFA返回的是list就簡單一 些，語法分析器可以前后前后移動ofset即可。DFA返回list的方式實現(xiàn)雖然簡單一點，但對于要解析的數(shù)據(jù)非常大的情況就不適用了 尤其數(shù)據(jù)是從網(wǎng)絡(luò)上以流的方

21、式傳過來的，這樣我們根本不知道什么時候這個流會結(jié)束，所以還是需要一個元素就返回一個元素的做法比較安全一一對于我們現(xiàn)在做的計算器的程序來說，隨便怎么做都可以了。語法分析語法分析是把詞法分析過程返回的 tokenList 轉(zhuǎn)換為語法樹的過程。 詞法分析的結(jié)果是為語法分析服務(wù)的，語法分析自然也是為下一步的語義分析做準(zhǔn)備 的，在這一節(jié)中， 我們只講一下語法樹是怎么構(gòu)造的， 下一節(jié)語義分析的部分再講如何使用 語法樹。語法樹是一個樹形的數(shù)據(jù)結(jié)構(gòu)， 樹的每個根節(jié)點表示一個語法結(jié)構(gòu)， 子節(jié)點表示構(gòu)成根 這個大語法結(jié)構(gòu)的小語法結(jié)構(gòu)。 這樣不斷劃分更小的語法結(jié)構(gòu)直到無法再分的子節(jié)點， 其實 就是一個整體與部分的關(guān)

22、系。因樹形結(jié)構(gòu)是要畫圖的， 但我們通常的工具是文本工具， 所以我們通常用類似以下文本 形式來表示樹形結(jié)構(gòu)：NODE1 -> NODE2 NODE3NODE2 -> NODE4這個表示的意思是： N0DE1為根節(jié)點，N0DE1有兩個子節(jié)點 N0DE2和N0DE3, N0DE2 又有一個子節(jié)點 NODE4。這樣即可用文本的形式表示樹形結(jié)構(gòu)了。這種表示形式叫巴科斯范式”英文簡稱為BNF下文中有需要表示這個名稱的地方，我就直接用BNF三個字母來代替了。下面我們看一下這個計算器的BNF（對于復(fù)雜語言的 BNF描述要寫幾十頁，但我們的計算器就只有這么幾行） ：點擊（此處 ）折疊或打開exp-&

23、gt; termexp-> term + expexp-> term - expterm-> factorterm-> factor * termterm-> factor / termfactor-> varNamefactor-> numberfactor-> - numberfactor-> funCallfactor-> ( exp )funCall> funName ( params )params-> expparams-> exp , params下面對這個語法結(jié)構(gòu)描述一下：exp 為算術(shù)表達(dá)式，即為我

24、們要分析的表達(dá)式整體。term 是可做加法或減法的項。我們可看到exp有三行表示基結(jié)構(gòu)，這三行是或的關(guān)系，即：exp可能是一個term，也可能是一個term加上一個exp，也可能是一個term減掉一個exp。也就是說，exp這個根節(jié) 點的子節(jié)點可能只有一個節(jié)點，也可能有三個節(jié)點。factor 是可做乘法或除法的項。term 繼續(xù)分解的過程與 exp 是完全一樣的，這里就不再贅述。 這里把加減法與乘除法分開為兩種語法結(jié)構(gòu)的原因是， 乘法與除法的優(yōu)先級高于加法與 減法，按照我們現(xiàn)在的表示，在計算加法或減法之前必須先計算term，這樣因term是先計 算的，所以優(yōu)先級就表示出來了。varName是變

25、量名，number是數(shù)字，fun Call是函數(shù)調(diào)用對于factor的組成部分就可理解為：可以為一個變量，或一個數(shù)字，或一個減號連著一個數(shù)字（負(fù)數(shù)），或一次函數(shù)調(diào)用，或用小括號括起來的表達(dá)式。funName是函數(shù)名，params是函數(shù)調(diào)用的參數(shù)。fun Call的結(jié)構(gòu)為：函數(shù)名后跟著一個括號，再跟著一個或多個參數(shù)，再跟著一個括回。params由兩個產(chǎn)生式，因每個參數(shù)都可以是單獨的算術(shù)表達(dá)式，所以一個exp節(jié)點即可表示一個參數(shù)，如果有多個參數(shù)，則exp后成要跟著一個逗號，之后再跟著其它的參數(shù)。這種表示方法相對于樹形的表示來說，有一個優(yōu)點，即：相對比較容易表示或”，比如factor這個節(jié)點可能由變

26、量名來表示，也可能由數(shù)字來表示，如可能是,這樣我們?nèi)绻媹D的話，如何表示多種可能中只選其中一種的情況呢？上面的表示是對語法結(jié)構(gòu)的抽象表示，抽象的東西還是具體化為我們的代碼中的數(shù)據(jù)結(jié)構(gòu)的。我們的目的是把我們的算術(shù)表達(dá)式變成符合語法樹描述的樣子，舉個例子來說：（1 + 2）*3轉(zhuǎn)成語法語法樹就是下圖所示的樣子：圖中藍(lán)色的部分為語法樹的葉子節(jié)點，也就是不能再分解的節(jié)點。這些葉子節(jié)點正是詞法分析部分的詞法元素。下面我們看一下來看一下構(gòu)造這個樹的步驟：上 面的圖中只有三種非葉子節(jié)點的類型（exp、term、factor）以及幾個葉子節(jié)點的類型number、*、+、（、），所以下面我只以這幾個為例做一下描

27、述，其它的節(jié)點類型的解析步驟是類似的一一因+*（）這幾個符號在描述中會不太好看，所以下文中我改用 add、mul、Ibt、rbt來表示。節(jié)點的類型：我們可以為每種節(jié)點類型單獨創(chuàng)建一個類，如：exp類型的節(jié)點即為 Exp類型的對象，term類型的節(jié)點即為Term類型的對象也可以考慮只用一個類型TreeNode,而用Node中的一個屬性type來表示不同的節(jié)點類型。我選擇用第二種方式來表示節(jié)點的類型, 這樣對于子節(jié)點的表示也相對簡單的直接用一 個 list 即可。對于 number 類型的節(jié)點,還需要一個屬性來表示數(shù)字的內(nèi)容,所以TreeNode 類中除了 type字段之外，還要有一個 conte

28、nt字段 varName或funName類型也是需要 content 字段的,用于表示變量名或函數(shù)名。為每個非葉子節(jié)點寫一個函數(shù)來解析這個語法結(jié)構(gòu),如：parseExp、 parseTerm 、parseFactor，因為我們每個語法結(jié)構(gòu)（或子語法結(jié)構(gòu)）都是TreeNode類型的對象為根的樹，所以這幾個函數(shù)的返回值類型為TreeNode。每個函數(shù)內(nèi)的結(jié)構(gòu)化代碼與BNF中的描述可完全對應(yīng)得上，比如：exp 有三個產(chǎn)生式："exp -> term"禾和 "exp -> term + exp"禾和 "exp -> term - ex

29、p"，貝U parseExp的代碼可以按下面的步驟來寫：創(chuàng)建一個類 TreeNode的對象expNode，并指定其類型為 exp。 調(diào)用parseTerm函數(shù)解析出expNode的第一個子元素 termNode。 向前看下一個詞法元素（如果還有下一個的話） ：如果為add或sub類型的Token,則創(chuàng)建第二個子元素 opNode （這個元素的類型為add或sub）,之后再遞歸調(diào)用 parseExp解析第三個子元素。如果不為add或sub類型的Token,則一定是出錯了。反回 expNode。term 有三個產(chǎn)生式："term -> factor" 和&quo

30、t;term -> factor * term" 和"term -> factor / term",這三個產(chǎn)生式與exp的三個產(chǎn)生式是同一個格式的，所以代碼也幾乎是一樣的。factor 有五個產(chǎn)生式，但我們現(xiàn)在這個例子用不到變更和函數(shù)，所以只看其中的三個："factor -> number"和"factor -> - number"和"factor -> （ exp ）"，貝U parseFactor 的代碼可以這樣 寫：創(chuàng)建一個類 TreeNode的對象factorNode

31、，并指定其類型為 factor。 向前看一個詞法元素：如果是num類型的Token,則創(chuàng)建一個 number類型的TreeNode對象做為factorNode 的子節(jié)點（這個節(jié)點的content值為當(dāng)前這個 Token的值）。如果是sub類型的Token,則再從tokenList中讀出一個 num,創(chuàng)建一個 number類型的 TreeNode做為factorNode的子節(jié)點（這個節(jié)點的content值為當(dāng)前這個Token的值把符號位 反過來）。如果是 lbt 類型的,則先創(chuàng)建一個 lbt 類型的 TreeNode 做為 factorNode 的第一個子節(jié)點, 再調(diào)用parseExp函數(shù)來獲得

32、第二個子節(jié)點，再向前看一個 Token,如果是rbt類型的，貝U創(chuàng)建一個rbt類型的Token做為第三個子節(jié)點（如果看到的不是rbt類型的就要報語法錯誤了）。返回 factorNode。 按上面描述的邏輯實現(xiàn)代碼是要不了多少行代碼就可以實現(xiàn)這個計算器的語法解析了。還有兩個fun Call和params,這兩個類型的解析與 exp或term或factor差不多，就不再 描述了。下面還要說一點額外的注意事項：我們現(xiàn)在寫代碼這種方式叫做LL（1）型，也叫遞歸向下型的語法分析，在這種語法分析方式中，我們總是先創(chuàng)建根節(jié)點，再創(chuàng)建子節(jié)點，在創(chuàng)建子節(jié)點時，我們總是由最左邊的節(jié)點開始一個一個去創(chuàng)建(如 par

33、seExp中，我們先創(chuàng)建出 來的就是expNode，然后再創(chuàng)建的 是termNode，之后如果還有元素的話就會創(chuàng)建opNode和下一個expNode)，這種語法解析方式是最容易用代碼實現(xiàn)的，所以我才使用這種方式來做，但這種解析方式有一個局限性： 語法的BNF描述中不能有左遞歸。何為左遞歸呢？舉個例子來說：exp的產(chǎn)生式 中的兩個"exp -> term + exp"禾和 "exp -> term - exp"，如果改為 "exp -> exp + term"禾和 "exp -> exp - term&

34、quot;， 也是對的，但按照這樣的產(chǎn)生式來寫代碼時，第一個要解析的就不是 term，則還是一個exp，要解析第一個TreeNode就要遞歸調(diào)用parseExp函數(shù)了，這樣就會形成無限的遞歸了。所以 我們在設(shè)計LL(1)型的文法描述時要避免左遞歸。LL(1)的文法設(shè)計在解析復(fù)雜的語言時會有語法描述上的局限性，如：C語言的一條語句開頭如果為 ABC,則這個ABC可能一個變量名，也可能是行號，此時必須再向前看一個 Token才能知道應(yīng)該使用哪個產(chǎn)生式，這就變成LL(2型了 一一LL后面括號中的數(shù)字代表我們在識別語法產(chǎn)生式時，要向前看幾個Token這樣的語法解析的代碼就復(fù)雜很多了。那么，有沒有實現(xiàn)簡

35、 單，且語法描述能力又強的解析方法呢？答案為：是有的。但本文只需要實 現(xiàn)計算器的語法，就沒有必要喧賓奪主來花費大量的篇幅來寫其它的語法解析方式。以后如果有時間可專門再寫一個博文來講語法解析。語法分析有時也是要判斷上下文的，比如：假設(shè)在C+代 碼中有這樣的一句：f<A, B>(c);這句代碼在沒有上下文的情況下是不能判斷是什么，它可能是一個函數(shù)調(diào)用(f是函數(shù)名，A和B是范形參數(shù)，c是函數(shù)的參數(shù))，也可能是一 個逗號表達(dá)式(f，A，B，c都是變量或 值，這一名就表示為 f小于A，B大于c)其實這是C+語法上的一個考慮不周之處，這 給編譯器的設(shè)計者帶來了很大的麻煩，JAVA對于范型方法的

36、調(diào)用就避免了C+的尷尬：JAVA中范型參數(shù)位置不在方法名與參數(shù)之間，而在方法名之前，如：<A, B> f(c)，這樣就不會與其它的JAVA語法沖突了。從這也可看出，語法的設(shè)計對語法解析程序的編寫影響是非常直 接的。最后再講一點稍微偏門一點的東西：上面講的解析過程是正統(tǒng)的語法解析方式，用這樣的方式來解析計算器的算術(shù)表達(dá)式有點殺雞用牛刀的感覺。對于算術(shù)表達(dá)式的語法樹可以用以更簡單的結(jié)構(gòu)，例如：表達(dá)式(10 + pow(2, 3) * sqrt(4)-1的語法樹可以表示成下面的圖形：這個圖顯然比正統(tǒng)的語法解析方式的結(jié)果樹要小很多一一因為這個樹中只有終結(jié)符號,exp、term、factor

37、等非終結(jié)符號是不存在的。對于這樣的語法樹的語義分析也更簡單，后面講語義分析時再講一下如何解析這個袖珍版本的語法樹。這個樹的構(gòu)造即：所有的葉子節(jié)點都是操作數(shù)，所有的根節(jié)點都是操作符 一一同時大家也可以注意到括號不見了，實際上括號在語法樹中也是不必要的。至于這個語法樹如何構(gòu)造就留個懸念，不在這里講了。語義分析語義分析是把語法樹轉(zhuǎn)成中間代碼，再由中間代碼轉(zhuǎn)成目標(biāo)代碼。 但對于簡單的分析來說，我們省略中間代碼的步驟， 直接讀語法樹生成目標(biāo)代碼 （目標(biāo)代碼即為前面講過的 ASM 代碼）。雖然對于復(fù)雜的語言來說語義分析這個部分是非常復(fù)雜，但對于語法與設(shè)計都很簡單的語言來說語義分析這個部分簡直簡單到可以合并到語法分析的過程中去做了，只是我們現(xiàn)在的目的是用計算器的例子來講編譯過程，所以這個部分還是簡單講一講。我之所以說這個計算器的語義分析可以合并到語法分析中是因為計算器的結(jié)構(gòu)中沒有 上下文的判斷，所以語法分析不報錯的話，語義分析就一定沒有問題了。我們還是以在語法分析中的（1 + 2） * 3的例子來講語義分析，這個表達(dá)式的語法樹還是這個：語法分析是構(gòu)造語法樹，語義分析是讀語法樹，所以語義分析的代碼與語法分析的代碼 是相通的，讀這個語法樹我們也是需要parseExp、 parseT