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

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

2、我們使用編譯技術(shù)處理的局部是(10 + pow(b, c) * sqrt(4) - 1，其它局部我們只使用簡單的文本處理。麻雀雖小，但五臟俱全，這個計算器包含編譯技術(shù)中最必要的局部。雖然這次我們只是實(shí)現(xiàn)了一個計算器，但所使用的技術(shù)足以實(shí)現(xiàn)一個簡單的腳本語言的解釋器了。這個計算器分為如下幾個局部：詞法分析：把表達(dá)式的文本，解析成詞法元素列表(tokenList)。 語法分析：把tokenList解析成語法樹(synta*Tree)。 語義分析：把語法樹轉(zhuǎn)成匯編語言的代碼(asm) 匯編器：把匯編代碼翻譯為機(jī)器碼字節(jié)碼。 虛擬機(jī)：執(zhí)行字節(jié)碼。 一般的編譯步聚中不包含匯編器和虛擬機(jī)，而這里之所以包含

3、這兩個局部是因為：通常編譯器會直接由中間代碼生成機(jī)器碼，而不是生成匯編代碼，而這里我之所以要生成匯編代碼的原因是調(diào)試的時候匯編的可讀性很好，如果直接生成目標(biāo)代碼，則會非常難用肉眼來閱讀。 自己實(shí)現(xiàn)虛擬機(jī)的原因是：現(xiàn)有的機(jī)器包括物理機(jī)和虛擬機(jī)以及模擬器的指令雖然也很豐富，但似乎都沒有直接計算乘方或開方的指令，自已實(shí)現(xiàn)虛擬機(jī)可以任意設(shè)計計算指令，這樣可以降低整個程序的復(fù)雜度。 因匯編器與虛擬機(jī)并不是編譯原理的局部，所以下文中并不會描述其實(shí)現(xiàn)細(xì)節(jié)，但因為計算器代碼編譯后的目標(biāo)代碼就是匯編代碼，所以需要把匯編指令做一下說明以下把這個匯編語言簡稱為ASM。ASM指令介紹指令助記符 操作數(shù) 指命說明 st

4、orenumber把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ù)字這個虛擬機(jī)是基于棧來設(shè)計的，所有的計算指令的操作數(shù)都從棧中取，store命令向棧頂添加數(shù)據(jù)。print指令用于打印當(dāng)前棧頂?shù)臄?shù)據(jù)，在我們編譯的匯編代碼要做到：正確計算出結(jié)果，且計算完成

5、之后的結(jié)果要剛好在棧頂，這樣最后調(diào)用一個print指令即可以控制臺看到計算結(jié)果。ASM舉例：例1，如果我們要計算1-2*3，則我們寫出的匯編代碼如下行號是為下文解釋代碼方便而放上去的，不是代碼的一局部：點(diǎn)擊(此處)折疊或翻開 store 3store 2mulstore 1sub print 對這段代碼的說明如下：前兩行向棧頂添加兩個數(shù)字，先壓入3再壓入2，這樣棧頂?shù)臄?shù)字是2，第二個數(shù)字是3。 第三行mul會從棧頂彈出兩個數(shù)字2和3計算乘法，并把結(jié)果6再壓入棧中，此時棧中只有一個數(shù)字6。 第四行向棧頂壓入一個數(shù)字1，此時棧頂為1，第二個數(shù)字是6。 第五行sub指令從棧頂取出兩個數(shù)字，第一個數(shù)字

6、1做為被減數(shù)，第二個數(shù)字6做為減數(shù)，即計算1-6，并把結(jié)果壓入棧中，此時棧中只有一個數(shù)字-5。 最后一行print指令不對棧做寫操作，只讀取棧頂?shù)臄?shù)字，并打印出來。 在這里，我們用到兩個運(yùn)算，mul和sub，這兩個運(yùn)算都是二元運(yùn)算，因我在設(shè)計指令的時候，先取出來的數(shù)字是第一個操作數(shù)，所以先壓入的應(yīng)該是第二個操作數(shù)，這也是為什么代碼中先壓入的是3，之后是2，最后才是1。 例2，如果我們要計算(10 + pow(2, 3) * sqrt(4) - 1，則我們寫出的匯編代碼如下行號是為下文解釋代碼方便而放上去的，不是代碼的一局部：點(diǎn)擊(此處)折疊或翻開 store 1store 4sqrtstore

7、 3store 2powstore 10addmulsubprint 對這段代碼的說明如下：這段代碼稍有點(diǎn)復(fù)雜，但有前一段代碼的經(jīng)歷，我們可以看到，所有的操作數(shù)的先后順序是從右向左store的，所以store指令的順序是固定下來的，剩下的關(guān)鍵是操作指令應(yīng)該放在哪里。 操作指令也是有一個規(guī)律的，即：當(dāng)前棧頂?shù)臄?shù)據(jù)剛剛好滿足*運(yùn)算時，則操作指令就放在哪里，如： store 1的時候沒有任何操作的操作數(shù)都在棧中。 store 4的時候，剛剛好sqrt的操作數(shù)都在棧中，則此時參加sqrt指令。 store 3 store 2時，剛剛好可以計算pow。 store 10之后，就可以計算加法了，所以此時參

8、加add指令。 add計算完成之后，再加上之前已計算完的sqrt指令，則此時乘法的所有操作數(shù)都在棧中了，則此時參加mul指令。 最后減操作也可以計算了，則加上sub指令。 所有計算完成之后打印出結(jié)果。 在這個例子中，我所說的規(guī)律其實(shí)就是后綴表達(dá)式。我們平常寫的算術(shù)表達(dá)式是中綴的，即符號在操作數(shù)中間，如1 + 2，的 + 在1和2中間，轉(zhuǎn)為后綴形式即為1 2 +這里因為我對于參數(shù)順序的設(shè)計是與正常順序相反的，所以1 + 2對于這個匯編器來說，其后綴形式就應(yīng)該為2 1 +大家是可以按照這個規(guī)律，相對簡單的實(shí)現(xiàn)這個計算器只要做好詞法分析就可以按照后綴表達(dá)式的規(guī)律直接由tokenList生成匯編代碼了

9、但我們的目的是用這個計算器的例子來講編譯，所以還是按步就班來講。詞法分析詞法分析的目的是把一段文本分解成詞法元素列表，例如(10 + pow(2, 3) * sqrt(4) - 1，做詞法分析之后會分解成如下幾個詞法元素： 10+pow(2,3)*sqrt(4)-1這里只是做了一次文本處理在處理之前，我們手里有的東西就是一串字符組成的字符串，在處理之后，我們按照一定的規(guī)則分解為多個單詞。算法是多種多樣的，有創(chuàng)造力的程序員會想出各種方法來處理這個單詞分解的問題。在編譯原理中，普遍的方式是用如下一個狀態(tài)轉(zhuǎn)換圖來實(shí)現(xiàn)的在圖中，橢圓形的是狀態(tài)，狀態(tài)與狀態(tài)之間有一條有方向的線，這個線代表從一個狀態(tài)到另一

10、個狀態(tài)的路徑，在這條線上面有一個花括號代表從前一個狀態(tài)到達(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)過假設(shè)干輸入后到達(dá)終結(jié)狀態(tài)，則這些輸入的字符可合并為詞法的合法單詞這里需要額外說明一點(diǎn)：在對輸入進(jìn)展匹配狀態(tài)時采用貪婪方式，即：盡量輸入更多的字符。在識別到一個合法的詞法單元之后，狀態(tài)回到START繼續(xù)識別下一個元素，直到?jīng)]有新的元素為止。這個狀態(tài)轉(zhuǎn)換圖在編譯原理中有一個專有名詞稱呼它確定有限狀態(tài)自動機(jī)，英文簡稱DFA。這里確定的意思是每

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

12、此時START狀態(tài)可承受這個輸入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)可識別一個合法

13、的詞法元素，即：從 START開場到當(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。 現(xiàn)在的情況與識別NUMBER的情況類似，當(dāng)前的狀態(tài)也是終結(jié)狀態(tài)，但按貪婪匹配的原則還要繼續(xù)看看是否可以匹配到新的輸入。 后面的b和

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

15、元素識別出來，不能忽略掉。 對于詞法元素的表示：通常我們會用一個類型Token來表示一個詞法元素，Token中有兩個屬性，一個用于表示這個Token的類型，另一個用于表示 容，只有數(shù)字與標(biāo)識符才需要使用Token類型的容屬性，其它的類型因為同一類型只有一種表示的可能，所以就不需要再把容保存下來了如ADD的容 一定是+。 關(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中都有一個運(yùn)算符，這個運(yùn)算符代表右移，但在C+11 標(biāo)準(zhǔn)中可以寫出這樣的代碼std:vectorstd:vector，在JDK5及以上版本也可以這樣寫 ListList，這里如果按貪婪批

17、配就錯了。所以必須在詞法分析中參加上下文的判斷才能決定是按兩 個來識別還是按一個來識別上下文的判斷是語法分析的局部了，但對于復(fù)雜的詞法構(gòu)造在沒有一個統(tǒng)一的詞法解析算法可以處理的情 況下就得借助更高級的方法了。 現(xiàn)在剩下的就是寫代碼了。 如果我把代碼貼在這里就太長了，不太適宜。所以下面我只描述一下描述DFA的思路： 思路一：直接靜態(tài)代碼來描述，類似這樣的方式把狀態(tài)機(jī)的每個路徑都描述出來：IF S = START AND c = 1 THEN S = INT . ELSIF .，這樣就可以輸入運(yùn)行了。 思路二：表格驅(qū)動式的，例如列出下面的表格即可知道哪個狀態(tài)經(jīng)過哪個輸入之后到達(dá)哪個新的狀態(tài)了下表的

18、左標(biāo)題是當(dāng)前的狀態(tài)，上標(biāo)題是在當(dāng)前狀態(tài)上的輸入，表格中的容是經(jīng)過路徑到達(dá)的狀態(tài)。 思路三：結(jié)合前兩個思路先寫一個代碼生成工具，工具讀取思路二中表格中的容，并生成思路一中的靜態(tài)代碼。0-9 . _a-zA-Z + - * / ( ) , START INT POINT ID ADD SUB MUL DIV LBT RBT MA INT INT NUMBER POINT NUMBER NUMBER NUMBER ID ID ID ADD SUB MUL DIV LBT RBT MA 下面舉一下DFA返回的Token對象的類型：NUM，F(xiàn)UN，VAR，ADD，SUB，MUL，DIV，LBT，RBT，

19、MA這里前三個與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ù)為輸入流。 parse方法的返回可以考慮返回一個Token的游標(biāo)，游標(biāo)供語法分析程序調(diào)用；也可以考慮解析完所有的詞法元素返回一個Token的列表。因為

20、目前比擬通用的語法分析算法只需要向前看一個Token對象，所以游標(biāo)就足夠了。 因為語法分析程序有可能會把已讀出來的Token放回去，下次再用，所以游 標(biāo)可考慮加一個putBack方法也可以考慮不實(shí)現(xiàn)這個方法，而由語法分析程序自己緩存當(dāng)前用不到的詞法元素如果DFA返回的是list就簡單一 些，語法分析器可以前后前后移動offset即可。 DFA返回list的方式實(shí)現(xiàn)雖然簡單一點(diǎn)，但對于要解析的數(shù)據(jù)非常大的情況就不適用了尤其數(shù)據(jù)是從網(wǎng)絡(luò)上以流的方式傳過來的，這樣我們根本不知道什 么時候這個流會完畢，所以還是需要一個元素就返回一個元素的做法比擬平安對于我們現(xiàn)在做的計算器的程序來說，隨便怎么做都可以了

21、。 語法分析語法分析是把詞法分析過程返回的tokenList轉(zhuǎn)換為語法樹的過程。詞法分析的結(jié)果是為語法分析效勞的，語法分析自然也是為下一步的語義分析做準(zhǔn)備的，在這一節(jié)中，我們只講一下語法樹是怎么構(gòu)造的，下一節(jié)語義分析的局部再講如何使用語法樹。語法樹是一個樹形的數(shù)據(jù)構(gòu)造，樹的每個根節(jié)點(diǎn)表示一個語法構(gòu)造，子節(jié)點(diǎn)表示構(gòu)成根這個大語法構(gòu)造的小語法構(gòu)造。這樣不斷劃分更小的語法構(gòu)造直到無法再分的子節(jié)點(diǎn)，其實(shí)就是一個整體與局部的關(guān)系。因樹形構(gòu)造是要畫圖的，但我們通常的工具是文本工具，所以我們通常用類似以下文本形式來表示樹形構(gòu)造：NODE1 -NODE2 NODE3NODE2 - NODE4這個表示的意思是：

22、NODE1為根節(jié)點(diǎn)，NODE1有兩個子節(jié)點(diǎn)NODE2和NODE3，NODE2又有一個子節(jié)點(diǎn)NODE4。這樣即可用文本的形式表示樹形構(gòu)造了。這種表示形式叫巴科斯式，英文簡稱為BNF下文中有需要表示這個名稱的地方，我就直接用BNF三個字母來代替了。下面我們看一下這個計算器的BNF對于復(fù)雜語言的BNF描述要寫幾十頁，但我們的計算器就只有這么幾行：點(diǎn)擊(此處)折疊或翻開 e*p - term e*p - term +e*p e*p - term -e*p term - factor term - factor*term term - factor /term factor - varName fact

23、or - number factor - -number factor - funCall factor - ( e*p ) funCall- funName ( params ) params - e*p params - e*p , params 下面對這個語法構(gòu)造描述一下：e*p為算術(shù)表達(dá)式，即為我們要分析的表達(dá)式整體。 term是可做加法或減法的項。 我們可看到e*p有三行表示基構(gòu)造，這三行是或的關(guān)系，即：e*p可能是一個term，也可能是一個term加上一個e*p，也可能是一個term減掉一個e*p。也就是說，e*p這個根節(jié)點(diǎn)的子節(jié)點(diǎn)可能只有一個節(jié)點(diǎn)，也可能有三個節(jié)點(diǎn)。 factor

24、是可做乘法或除法的項。 term繼續(xù)分解的過程與e*p是完全一樣的，這里就不再贅述。 這里把加減法與乘除法分開為兩種語法構(gòu)造的原因是，乘法與除法的優(yōu)先級高于加法與減法，按照我們現(xiàn)在的表示，在計算加法或減法之前必須先計算term，這樣因term是先計算的，所以優(yōu)先級就表示出來了。 varName是變量名，number是數(shù)字，funCall是函數(shù)調(diào)用 對于factor的組成局部就可理解為：可以為一個變量，或一個數(shù)字，或一個減號連著一個數(shù)字負(fù)數(shù)，或一次函數(shù)調(diào)用，或用小括號括起來的表達(dá)式。 funName是函數(shù)名，params是函數(shù)調(diào)用的參數(shù)。 funCall的構(gòu)造為：函數(shù)名后跟著一個括號，再跟著一個

25、或多個參數(shù)，再跟著一個括回。 params由兩個產(chǎn)生式，因每個參數(shù)都可以是單獨(dú)的算術(shù)表達(dá)式，所以一個e*p節(jié)點(diǎn)即可表示一個參數(shù)，如果有多個參數(shù)，則e*p后成要跟著一個逗號，之后再跟著其它的參數(shù)。 這種表示方法相對于樹形的表示來說，有一個優(yōu)點(diǎn)，即：相比照擬容易表示或，比方factor這個節(jié)點(diǎn)可能由變量名來表示，也可能由數(shù)字來表示，如可能是，這樣我們?nèi)绻媹D的話，如何表示多種可能中只選其中一種的情況呢？上面的表示是對語法構(gòu)造的抽象表示，抽象的東西還是具體化為我們的代碼中的數(shù)據(jù)構(gòu)造的。我們的目的是把我們的算術(shù)表達(dá)式變成符合語法樹描述的樣子，舉個例子來說：(1 + 2) * 3轉(zhuǎn)成語法語法樹就是下列圖

26、所示的樣子：圖中藍(lán)色的局部為語法樹的葉子節(jié)點(diǎn)，也就是不能再分解的節(jié)點(diǎn)。這些葉子節(jié)點(diǎn)正是詞法分析局部的詞法元素。下面我們看一下來看一下構(gòu)造這個樹的步驟：上 面的圖中只有三種非葉子節(jié)點(diǎn)的類型e*p、term、factor以及幾個葉子節(jié)點(diǎn)的類型number、*、+、(、)，所以下面我只以這幾個為 例做一下描述，其它的節(jié)點(diǎn)類型的解析步驟是類似的因+*()這幾個符號在描述中會不太好看，所以下文中我改用add、mul、lbt、rbt來表示。 節(jié)點(diǎn)的類型： 我們可以為每種節(jié)點(diǎn)類型單獨(dú)創(chuàng)立一個類，如：e*p類型的節(jié)點(diǎn)即為E*p類型的對象，term類型的節(jié)點(diǎn)即為Term類型的對象 也可以考慮只用一個類型Tree

27、Node，而用Node中的一個屬性type來表示不同的節(jié)點(diǎn)類型。 我選擇用第二種方式來表示節(jié)點(diǎn)的類型，這樣對于子節(jié)點(diǎn)的表示也相對簡單的直接用一個list即可。 對于number類型的節(jié)點(diǎn)，還需要一個屬性來表示數(shù)字的容，所以TreeNode類中除了type字段之外，還要有一個content字段varName或funName類型也是需要content字段的，用于表示變量名或函數(shù)名。 為每個非葉子節(jié)點(diǎn)寫一個函數(shù)來解析這個語法構(gòu)造，如：parseE*p、parseTerm、parseFactor，因為我們每個語法構(gòu)造或子語法構(gòu)造都是TreeNode類型的對象為根的樹，所以這幾個函數(shù)的返回值類型為Tre

28、eNode。 每個函數(shù)的構(gòu)造化代碼與BNF中的描述可完全對應(yīng)得上，比方： e*p有三個產(chǎn)生式：e*p - term和e*p - term + e*p和e*p - term - e*p，則parseE*p的代碼可以按下面的步驟來寫： 創(chuàng)立一個類TreeNode的對象e*pNode，并指定其類型為e*p。 調(diào)用parseTerm函數(shù)解析出e*pNode的第一個子元素termNode。 向前看下一個詞法元素如果還有下一個的話： 如果為add或sub類型的Token，則創(chuàng)立第二個子元素opNode這個元素的類型為add或sub，之后再遞歸調(diào)用parseE*p解析第三個子元素。 如果不為add或sub類

29、型的Token，則一定是出錯了。 反回e*pNode。 term有三個產(chǎn)生式：term - factor和term - factor * term和term - factor / term，這三個產(chǎn)生式與e*p的三個產(chǎn)生式是同一個格式的，所以代碼也幾乎是一樣的。 factor有五個產(chǎn)生式，但我們現(xiàn)在這個例子用不到變更和函數(shù)，所以只看其中的三個：factor - number和factor - - number和factor - ( e*p )，則parseFactor的代碼可以這樣寫： 創(chuàng)立一個類TreeNode的對象factorNode，并指定其類型為factor。 向前看一個詞法元素： 如

30、果是num類型的Token，則創(chuàng)立一個number類型的TreeNode對象做為factorNode的子節(jié)點(diǎn)這個節(jié)點(diǎn)的content值為當(dāng)前這個Token的值。 如果是sub類型的Token，則再從tokenList中讀出一個num，創(chuàng)立一個number類型的TreeNode做為factorNode的子節(jié)點(diǎn)這個節(jié)點(diǎn)的content值為當(dāng)前這個Token的值把符號位反過來。 如果是lbt類型的，則先創(chuàng)立一個lbt類型的TreeNode做為factorNode的第一個子節(jié)點(diǎn)，再調(diào)用parseE*p函數(shù)來獲得第二個子節(jié) 點(diǎn)，再向前看一個Token，如果是rbt類型的，則創(chuàng)立一個rbt類型的Token

31、做為第三個子節(jié)點(diǎn)如果看到的不是rbt類型的就要報語法錯誤了。 返回factorNode。 按上面描述的邏輯實(shí)現(xiàn)代碼是要不了多少行代碼就可以實(shí)現(xiàn)這個計算器的語法解析了。還有兩個funCall和params，這兩個類型的解析與e*p或term或factor差不多，就不再描述了。下面還要說一點(diǎn)額外的考前須知：我們現(xiàn)在寫代碼這種方式叫做LL(1)型，也叫遞歸向下型的語法分析，在這種 語法分析方式中，我們總是先創(chuàng)立根節(jié)點(diǎn)，再創(chuàng)立子節(jié)點(diǎn)，在創(chuàng)立子節(jié)點(diǎn)時，我們總是由最左邊的節(jié)點(diǎn)開場一個一個去創(chuàng)立如parseE*p中，我們先創(chuàng)立出 來的就是e*pNode，然后再創(chuàng)立的是termNode，之后如果還有元素的話就

32、會創(chuàng)立opNode和下一個e*pNode，這種語法解析方式是最容 易用代碼實(shí)現(xiàn)的，所以我才使用這種方式來做，但這種解析方式有一個局限性：語法的BNF描述中不能有左遞歸。何為左遞歸呢？舉個例子來說：e*p的產(chǎn)生式 中的兩個e*p - term + e*p和e*p - term - e*p，如果改為e*p - e*p +term和e*p -e*p - term，也是對的，但按照這樣的產(chǎn)生式來寫代碼時，第一個要解析的就不是term，則還是一個e*p，要解析第一個TreeNode就要遞歸調(diào)用parseE*p函數(shù)了，這樣就會形成無限的遞歸了。所以我們在設(shè)計LL(1)型的文法描述時要防止左遞歸。 LL(1

33、)的文法設(shè)計在解析復(fù)雜的語言時會有語法描述上的局限性，如：C語言 的一條語句開頭如果為ABC，則這個ABC可能一個變量名，也可能是行號，此時必須再向前看一個Token才能知道應(yīng)該使用哪個產(chǎn)生式，這就變成 LL(2)型了LL后面括號中的數(shù)字代表我們在識別語法產(chǎn)生式時，要向前看幾個Token這樣的語法解析的代碼就復(fù)雜很多了。則，有沒有實(shí)現(xiàn)簡 單，且語法描述能力又強(qiáng)的解析方法呢？答案為：是有的。但本文只需要實(shí)現(xiàn)計算器的語法，就沒有必要喧賓奪主來花費(fèi)大量的篇幅來寫其它的語法解析方式。以后 如果有時間可專門再寫一個博文來講語法解析。 語法分析有時也是要判斷上下文的，比方：假設(shè)在C+代 碼中有這樣的一句：

34、f(c);這句代碼在沒有上下文的情況下是不能判斷是什么，它可能是一個函數(shù)調(diào)用f是函數(shù)名，A和B是形參數(shù)，c是函數(shù)的參數(shù)，也可能是一 個逗號表達(dá)式f，A，B，c都是變量或值，這一名就表示為f小于A，B大于c其實(shí)這是C+語法上的一個考慮不周之處，這給編譯器的設(shè)計者帶來了很大的麻煩，JAVA對于型方法的調(diào)用就防止了C+的為難：JAVA中型參數(shù)位置不在方法名與參數(shù)之間，而在方法名之前，如： f(c)，這樣就不會與其它的JAVA語法沖突了。從這也可看出，語法的設(shè)計對語法解析程序的編寫影響是非常直接的。最后再講一點(diǎn)稍微偏門一點(diǎn)的東西：上面講的解析過程是正統(tǒng)的語法解析方式，用這樣的方式來解析計算器的算術(shù)表達(dá)

35、式有點(diǎn)殺雞用牛刀的感覺。對于算術(shù)表達(dá)式的語法樹可以用以更簡單的構(gòu)造，例如：表達(dá)式(10 + pow(2, 3) * sqrt(4) - 1的語法樹可以表示成下面的圖形：這個圖顯然比正統(tǒng)的語法解析方式的結(jié)果樹要小很多因為這個樹中只有終結(jié)符號，e*p、term、factor等非終結(jié)符號是不存在的。對于這樣的語法樹的語義分析也更簡單，后面講語義分析時再講一下如何解析這個袖珍版本的語法樹。這個樹的構(gòu)造即：所有的葉子節(jié)點(diǎn)都是操作數(shù)，所有的根節(jié)點(diǎn)都是操作符同時大家也可以注意到括號不見了，實(shí)際上括號在語法樹中也是不必要的。至于這個語法樹如何構(gòu)造就留個懸念，不在這里講了。語義分析語義分析是把語法樹轉(zhuǎn)成中間代碼

36、，再由中間代碼轉(zhuǎn)成目標(biāo)代碼。但對于簡單的分析來說，我們省略中間代碼的步驟，直接讀語法樹生成目標(biāo)代碼目標(biāo)代碼即為前面講過的ASM代碼。雖然對于復(fù)雜的語言來說語義分析這個局部是非常復(fù)雜，但對于語法與設(shè)計都很簡單的語言來說語義分析這個局部簡直簡單到可以合并到語法分析的過程中去做了，只是我們現(xiàn)在的目的是用計算器的例子來講編譯過程，所以這個局部還是簡單講一講。我之所以說這個計算器的語義分析可以合并到語法分析中是因為計算器的構(gòu)造中沒有上下文的判斷，所以語法分析不報錯的話，語義分析就一定沒有問題了。我們還是以在語法分析中的 (1 + 2) * 3 的例子來講語義分析，這個表達(dá)式的語法樹還是這個：語法分析是構(gòu)造語法樹，語