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

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

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

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

4、ASM指令介紹指令助記符 操作數(shù) 指命說明 storenumber把number放入棧頂add從棧頂取出兩個數(shù)相加，并把結(jié)果壓回棧中sub從棧頂取出一個數(shù)做為被減數(shù)，再取一個做為減數(shù)，相減之后的結(jié)果入棧mul從棧頂取出兩個數(shù)相乘，并把結(jié)果入棧div從棧頂取出一個數(shù)做為除法的分子，再取出一個做為除法的分母，相除的結(jié)果入棧pow從棧頂取出一個數(shù)做為底，再取出一個做為冪，計(jì)算結(jié)果入棧sqrt從棧頂取出一個數(shù)，把這個數(shù)開平方后的結(jié)果入棧print在控制臺打印棧頂?shù)臄?shù)字這個虛擬機(jī)是基于棧來設(shè)計(jì)的，所有的計(jì)算指令的操作數(shù)都從棧中取，store命令向棧頂添加數(shù)據(jù)。print指令用于打印當(dāng)前棧頂?shù)臄?shù)據(jù)，在我們

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

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

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

8、計(jì)算pow。 store 10之后，就可以計(jì)算加法了，所以此時(shí)加入add指令。 add計(jì)算完成之后，再加上之前已計(jì)算完的sqrt指令，則此時(shí)乘法的所有操作數(shù)都在棧中了，則此時(shí)加入mul指令。 最后減操作也可以計(jì)算了，則加上sub指令。 所有計(jì)算完成之后打印出結(jié)果。 在這個例子中，我所說的“規(guī)律”其實(shí)就是“后綴表達(dá)式”。我們平常寫的算術(shù)表達(dá)式是“中綴”的，即符號在操作數(shù)中間，如1 + 2，的 + 在1和2中間，轉(zhuǎn)為后綴形式即為1 2 +這里因?yàn)槲覍τ趨?shù)順序的設(shè)計(jì)是與“正?！表樞蛳喾吹?，所以1 + 2對于這個匯編器來說，其后綴形式就應(yīng)該為2 1 +大家是可以按照這個規(guī)律，相對簡單的實(shí)現(xiàn)這個計(jì)算器

9、只要做好詞法分析就可以按照后綴表達(dá)式的規(guī)律直接由tokenList生成匯編代碼了但我們的目的是用這個計(jì)算器的例子來講編譯，所以還是按步就班來講。詞法分析詞法分析的目的是把一段文本分解成詞法元素列表，例如(10 + pow(2, 3) * sqrt(4) - 1，做詞法分析之后會分解成如下幾個詞法元素： （10+pow(2,3)*sqrt(4)-1這里只是做了一次文本處理在處理之前，我們手里有的東西就是一串字符組成的字符串，在處理之后，我們按照一定的“規(guī)則”分解為多個單詞。算法是多種多樣的，有創(chuàng)造力的程序員會想出各種辦法來處理這個單詞分解的問題。在編譯原理中，普遍的方式是用如下一個狀態(tài)轉(zhuǎn)換圖來實(shí)

10、現(xiàn)的在圖中，“橢圓形”的是狀態(tài)，狀態(tài)與狀態(tài)之間有一條有方向的線，這個線代表從一個狀態(tài)到另一個狀態(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)過若干輸入后到達(dá)終結(jié)狀態(tài)，則這些輸入的字符可合并為詞法的合法單詞這里需要額外說明一點(diǎn)：在對輸入進(jìn)行匹配狀態(tài)時(shí)采用貪婪方式，即：盡量輸入更多的字符。在識別到一個合法的詞法單元之后，狀態(tài)回到START繼續(xù)識別下一個元素，直到?jīng)]有新的元素為止。這個狀態(tài)

11、轉(zhuǎn)換圖在編譯原理中有一個專有名詞稱呼它“確定有限狀態(tài)自動機(jī)”，英文簡稱DFA。這里“確定”的意思是每一個狀態(tài)經(jīng)過一個輸入字符可以確定只有 一條路徑到達(dá)另一個狀態(tài)，“有限”的意思是，狀態(tài)的個數(shù)是有限的。對于一個復(fù)雜語言的狀態(tài)數(shù)量是這個狀態(tài)機(jī)的幾個數(shù)量級的大小。但我們現(xiàn)在的計(jì)算器只需要 這幾個狀態(tài)就夠了。通常的DFA會由工具讀取正則方法描述而生成的，而不是直接手工構(gòu)造，但對我們現(xiàn)在設(shè)計(jì)的計(jì)算器來說，其DFA非常小，手工構(gòu)造是很方便的，所以就不用工具了。另外，如果使用工具的話，我這篇文章也不會使用現(xiàn)有的工具，而是自己實(shí)現(xiàn)一個工具。下面舉個例子：我們有一個表達(dá)式12.3 + abc，下面我來描述一下D

12、FA的運(yùn)行過程：定義一個變量s，來表示當(dāng)前狀態(tài)機(jī)所在的狀態(tài)（初始時(shí)s = START）。 輸入第一個字符1，此時(shí)START狀態(tài)可接受這個輸入1，到達(dá)INT狀態(tài)，則變量s賦值為INT狀態(tài)，此時(shí)可看到INT狀態(tài)的顏色是藍(lán)色表示當(dāng)前可識別為一個合法的詞法元素，但因?yàn)槲覀兊囊?guī)則是貪婪匹配，所以我們還要看看是否還能夠匹配更多的字符。 輸入第二個字符2，此時(shí)INT狀態(tài)也可以接受這人輸入，并到達(dá)INT狀態(tài)（轉(zhuǎn)了一個圈又回到原來的狀態(tài)），此時(shí)變量s賦值為INT狀態(tài)。 再輸入第三個字符 . ，此時(shí)INT狀態(tài)可接受 . 到達(dá)NUMBER狀態(tài)，此時(shí)變量s賦值為NUMBER狀態(tài)。 此時(shí)我們再向前看一個字符 + ，此時(shí)

13、的狀態(tài)NUMBER無法接受這個字符了，同時(shí)我們可在看到NUMBER狀態(tài)的顏色是藍(lán)色的，表示當(dāng)前狀態(tài)可識別一個合法的詞法元素，即：從 START開始到當(dāng)前我們一共經(jīng)歷的輸入為12.3，則這個單詞做為第一個合法的詞法元素。 第一個詞法元素識別成功之后，變量s要回到START狀態(tài)，并繼續(xù)輸入 + ，此時(shí)從START狀態(tài)可到達(dá)ADD狀態(tài)，且ADD狀態(tài)并不允許接受任何輸入，同時(shí)ADD狀態(tài)的顏色也是藍(lán)色的，則我們又識別出第二個詞法元素 + 。 在識別到第二個詞法元素之后，變更s要回到START狀態(tài)，并繼續(xù)輸入a，此時(shí)START狀態(tài)可由a指向的路徑到達(dá)ID狀態(tài)，此時(shí)s賦值為新的狀態(tài)ID。 現(xiàn)在的情況與識別N

14、UMBER的情況類似，當(dāng)前的狀態(tài)也是終結(jié)狀態(tài)，但按貪婪匹配的原則還要繼續(xù)看看是否可以匹配到新的輸入。 后面的b和c都在ID一個狀態(tài)里轉(zhuǎn)圈，我就不在贅述了，這樣我們就識別到了最后一個詞法元素abc了。 用如上過程的方法可以識別任何正確的算術(shù)表達(dá)式，但還有幾點(diǎn)需要特別說明： 如何識別錯誤：目前我見過的語言規(guī)范都在描述如何正確的編譯一個語言，但沒有一個規(guī)范有描述如何報(bào)錯的，所以我們目前能做的是只要按正常的走法走不通了，那就是錯了，就要報(bào)錯，并盡可能提供詳細(xì)的錯誤信息。 對空白的識別：我在DFA中并沒有畫識別空白的部分，原因是對于計(jì)算器程序來說，空白完全沒有用處，所以我只是在代碼中直接忽略這個輸入，以

15、免狀態(tài)機(jī)無法 識別空白，同時(shí)在識別到詞法元素之后，去掉單詞前后的空白。對于某些語言來說，空白是有意義的，需要做為詞法元素識別出來，不能忽略掉。 對于詞法元素的表示：通常我們會用一個類型Token來表示一個詞法元素，Token中有兩個屬性，一個用于表示這個Token的類型，另一個用于表示內(nèi) 容，只有數(shù)字與標(biāo)識符才需要使用Token類型的內(nèi)容屬性，其它的類型因?yàn)橥活愋椭挥幸环N表示的可能，所以就不需要再把內(nèi)容保存下來了（如ADD的內(nèi)容 一定是+）。 關(guān)于標(biāo)識符：DFA中的ID狀態(tài)用于識別標(biāo)識符，這里的標(biāo)識符包括自定義的變量，也包括函數(shù)名。在DFA的設(shè)計(jì)過程中，我們可以選擇把普通標(biāo)識符與保留字 做為

16、不同的狀態(tài)，也可以用使用同一個狀態(tài)。我們現(xiàn)在的設(shè)計(jì)就使用了一個ID狀態(tài)表示所有的標(biāo)識符，而在識別到一個ID之后，我們在看是否是一個保留字，這 樣在返回Token對象時(shí)設(shè)置不同的類型。 對于INT和NUMBER：這個計(jì)算器的所有計(jì)算都使用的是double類型的數(shù)字，所在雖然我們的詞法可以識別到INT，但我們定義Token的類型 時(shí)，就只定義一個NUMBER類型，INT或NUMBER狀態(tài)確定的單詞都返回NUMBER這個類型的Token對象。 前面的邏輯中有一個貪婪批配的原則，這個原則在某些語言的詞法中會有一些特例不適用，例如在C+和JAVA中都有一個運(yùn)算符“”，這個運(yùn)算符代表右移，但在C+11 標(biāo)

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

18、SIF .，這樣就可以輸入運(yùn)行了。 思路二：表格驅(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 + - * / ( ) , START INT POINT ID ADD SUB MUL DIV LBT RBT COMMA INT INT NUMBER POINT NUMBER NUMBER NUMBER ID ID ID ADD SUB MU

19、L DIV LBT RBT COMMA 下面舉一下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á)式）

20、，則可以考慮參數(shù)為輸入流。 parse方法的返回可以考慮返回一個Token的游標(biāo)，游標(biāo)供語法分析程序調(diào)用；也可以考慮解析完所有的詞法元素返回一個Token的列表。因?yàn)槟壳氨容^通用的語法分析算法只需要向前看一個Token對象，所以游標(biāo)就足夠了。 因?yàn)檎Z法分析程序有可能會把已讀出來的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)

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

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

23、p - term -exp term - factor term - factor*term term - factor /term factor - varName factor - number factor - -number factor - funCall factor - ( exp ) funCall- funName ( params ) params - exp params - exp , params 下面對這個語法結(jié)構(gòu)描述一下：exp為算術(shù)表達(dá)式，即為我們要分析的表達(dá)式整體。 term是可做加法或減法的項(xiàng)。 我們可看到exp有三行表示基結(jié)構(gòu)，這三行是或的關(guān)系，即：exp

24、可能是一個term，也可能是一個term加上一個exp，也可能是一個term減掉一個exp。也就是說，exp這個根節(jié)點(diǎn)的子節(jié)點(diǎn)可能只有一個節(jié)點(diǎn)，也可能有三個節(jié)點(diǎn)。 factor是可做乘法或除法的項(xiàng)。 term繼續(xù)分解的過程與exp是完全一樣的，這里就不再贅述。 這里把加減法與乘除法分開為兩種語法結(jié)構(gòu)的原因是，乘法與除法的優(yōu)先級高于加法與減法，按照我們現(xiàn)在的表示，在計(jì)算加法或減法之前必須先計(jì)算term，這樣因term是先計(jì)算的，所以優(yōu)先級就表示出來了。 varName是變量名，number是數(shù)字，funCall是函數(shù)調(diào)用 對于factor的組成部分就可理解為：可以為一個變量，或一個數(shù)字，或一個減

25、號連著一個數(shù)字（負(fù)數(shù)），或一次函數(shù)調(diào)用，或用小括號括起來的表達(dá)式。 funName是函數(shù)名，params是函數(shù)調(diào)用的參數(shù)。 funCall的結(jié)構(gòu)為：函數(shù)名后跟著一個括號，再跟著一個或多個參數(shù)，再跟著一個括回。 params由兩個產(chǎn)生式，因每個參數(shù)都可以是單獨(dú)的算術(shù)表達(dá)式，所以一個exp節(jié)點(diǎn)即可表示一個參數(shù)，如果有多個參數(shù)，則exp后成要跟著一個逗號，之后再跟著其它的參數(shù)。 這種表示方法相對于樹形的表示來說，有一個優(yōu)點(diǎn)，即：相對比較容易表示“或”，比如factor這個節(jié)點(diǎn)可能由變量名來表示，也可能由數(shù)字來表示，如可能是，這樣我們?nèi)绻媹D的話，如何表示多種可能中只選其中一種的情況呢？上面的表示是對

26、語法結(jié)構(gòu)的抽象表示，抽象的東西還是具體化為我們的代碼中的數(shù)據(jù)結(jié)構(gòu)的。我們的目的是把我們的算術(shù)表達(dá)式變成符合語法樹描述的樣子，舉個例子來說：(1 + 2) * 3轉(zhuǎn)成語法語法樹就是下圖所示的樣子：圖中藍(lán)色的部分為語法樹的葉子節(jié)點(diǎn)，也就是不能再分解的節(jié)點(diǎn)。這些葉子節(jié)點(diǎn)正是詞法分析部分的詞法元素。下面我們看一下來看一下構(gòu)造這個樹的步驟：上 面的圖中只有三種非葉子節(jié)點(diǎn)的類型（exp、term、factor）以及幾個葉子節(jié)點(diǎn)的類型number、*、+、(、)，所以下面我只以這幾個為 例做一下描述，其它的節(jié)點(diǎn)類型的解析步驟是類似的因+*()這幾個符號在描述中會不太好看，所以下文中我改用add、mul、lb

27、t、rbt來表示。 節(jié)點(diǎn)的類型： 我們可以為每種節(jié)點(diǎn)類型單獨(dú)創(chuàng)建一個類，如：exp類型的節(jié)點(diǎn)即為Exp類型的對象，term類型的節(jié)點(diǎn)即為Term類型的對象 也可以考慮只用一個類型TreeNode，而用Node中的一個屬性type來表示不同的節(jié)點(diǎn)類型。 我選擇用第二種方式來表示節(jié)點(diǎn)的類型，這樣對于子節(jié)點(diǎn)的表示也相對簡單的直接用一個list即可。 對于number類型的節(jié)點(diǎn)，還需要一個屬性來表示數(shù)字的內(nèi)容，所以TreeNode類中除了type字段之外，還要有一個content字段varName或funName類型也是需要content字段的，用于表示變量名或函數(shù)名。 為每個非葉子節(jié)點(diǎn)寫一個函數(shù)來解

28、析這個語法結(jié)構(gòu)，如：parseExp、parseTerm、parseFactor，因?yàn)槲覀兠總€語法結(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 - exp，則parseExp的代碼可以按下面的步驟來寫： 創(chuàng)建一個類TreeNode的對象expNode，并指定其類型為exp。 調(diào)用parseTerm函數(shù)解析出expNode的第一個子元素termNode。 向前看下一個詞法元素（

29、如果還有下一個的話）： 如果為add或sub類型的Token，則創(chuàng)建第二個子元素opNode（這個元素的類型為add或sub），之后再遞歸調(diào)用parseExp解析第三個子元素。 如果不為add或sub類型的Token，則一定是出錯了。 反回expNode。 term有三個產(chǎn)生式：term - factor和term - factor * term和term - factor / term，這三個產(chǎn)生式與exp的三個產(chǎn)生式是同一個格式的，所以代碼也幾乎是一樣的。 factor有五個產(chǎn)生式，但我們現(xiàn)在這個例子用不到變更和函數(shù)，所以只看其中的三個：factor - number和factor - -

30、 number和factor - ( exp )，則parseFactor的代碼可以這樣寫： 創(chuàng)建一個類TreeNode的對象factorNode，并指定其類型為factor。 向前看一個詞法元素： 如果是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類

31、型的，則先創(chuàng)建一個lbt類型的TreeNode做為factorNode的第一個子節(jié)點(diǎn)，再調(diào)用parseExp函數(shù)來獲得第二個子節(jié) 點(diǎn)，再向前看一個Token，如果是rbt類型的，則創(chuàng)建一個rbt類型的Token做為第三個子節(jié)點(diǎn)（如果看到的不是rbt類型的就要報(bào)語法錯誤了）。 返回factorNode。 按上面描述的邏輯實(shí)現(xiàn)代碼是要不了多少行代碼就可以實(shí)現(xiàn)這個計(jì)算器的語法解析了。還有兩個funCall和params，這兩個類型的解析與exp或term或factor差不多，就不再描述了。下面還要說一點(diǎn)額外的注意事項(xiàng)：我們現(xiàn)在寫代碼這種方式叫做LL(1)型，也叫遞歸向下型的語法分析，在這種 語法分析

32、方式中，我們總是先創(chuàng)建根節(jié)點(diǎn)，再創(chuàng)建子節(jié)點(diǎn)，在創(chuàng)建子節(jié)點(diǎn)時(shí)，我們總是由最左邊的節(jié)點(diǎn)開始一個一個去創(chuàng)建（如parseExp中，我們先創(chuàng)建出 來的就是expNode，然后再創(chuàng)建的是termNode，之后如果還有元素的話就會創(chuàng)建opNode和下一個expNode），這種語法解析方式是最容 易用代碼實(shí)現(xiàn)的，所以我才使用這種方式來做，但這種解析方式有一個局限性：語法的BNF描述中不能有左遞歸。何為左遞歸呢？舉個例子來說：exp的產(chǎn)生式 中的兩個exp - term + exp和exp - term - exp，如果改為exp - exp +term和exp -exp - term，也是對的，但按照這樣的

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

34、為：是有的。但本文只需要實(shí)現(xiàn)計(jì)算器的語法，就沒有必要喧賓奪主來花費(fèi)大量的篇幅來寫其它的語法解析方式。以后 如果有時(shí)間可專門再寫一個博文來講語法解析。 語法分析有時(shí)也是要判斷上下文的，比如：假設(shè)在C+代 碼中有這樣的一句：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è)計(jì)者帶來了很大的麻煩，JAVA對于范型方法的調(diào)用就避免了C+的尷尬：JAVA中范型參數(shù)位置不在方法名與參數(shù)之間，而

35、在方法名之前，如： f(c)，這樣就不會與其它的JAVA語法沖突了。從這也可看出，語法的設(shè)計(jì)對語法解析程序的編寫影響是非常直接的。最后再講一點(diǎn)稍微偏門一點(diǎn)的東西：上面講的解析過程是正統(tǒng)的語法解析方式，用這樣的方式來解析計(jì)算器的算術(shù)表達(dá)式有點(diǎn)殺雞用牛刀的感覺。對于算術(shù)表達(dá)式的語法樹可以用以更簡單的結(jié)構(gòu)，例如：表達(dá)式(10 + pow(2, 3) * sqrt(4) - 1的語法樹可以表示成下面的圖形：這個圖顯然比正統(tǒng)的語法解析方式的結(jié)果樹要小很多因?yàn)檫@個樹中只有終結(jié)符號，exp、term、factor等非終結(jié)符號是不存在的。對于這樣的語法樹的語義分析也更簡單，后面講語義分析時(shí)再講一下如何解析這個

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