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

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

2、rt(4)-1，其它局部我們只使用簡單的文本處理。麻雀雖小，但五臟俱全，這個計算器包含編譯技術中最必要的局部。雖然這次我們只是實現(xiàn)了一個計算器，但所使用的技術足以實現(xiàn)一個簡單的腳本語言的解釋器了。這個計算器分為如下幾個局部：詞法分析：把表達式的文本，解析成詞法元素列表(tokenList)。語法分析：把tokenList解析成語法樹(syntaxTree)。語義分析：把語法樹轉成匯編語言的代碼(asm)匯編器：把匯編代碼翻譯為機器碼字節(jié)碼。虛擬機：執(zhí)行字節(jié)碼。一般的編譯步聚中不包含“匯編器和“虛擬機，而這里之所以包含這兩個局部是因為：通常編譯器會直接由中間代碼生成機器碼，而不是生成匯編代碼，而

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

4、棧中sub從棧頂取出一個數(shù)做為被減數(shù)，再取一個做為減數(shù)，相減之后的結果入棧mul從棧頂取出兩個數(shù)相乘，并把結果入棧div從棧頂取出一個數(shù)做為除法的分子，再取出一個做為除法的分母，相除的結果入棧pow從棧頂取出一個數(shù)做為底，再取出一個做為哥，計算結果入棧sqrt從棧頂取出一個數(shù)，把這個數(shù)開平方后的結果入棧print在控制臺打印棧頂?shù)臄?shù)字這個虛擬機是基于棧來設計的，所有的計算指令的操作數(shù)都從棧中取，store命令向棧頂添加數(shù)據(jù)。print指令用于打印當前棧頂?shù)臄?shù)據(jù)，在我們編譯的匯編代碼要做到：正確計算出結果，且計算完成之后的結果要剛好在棧頂，這樣最后調用一個print指令即可以控制臺看到計算結果。

5、ASM舉例：例1,如果我們要計算1-2*3,那么我們寫出的匯編代碼如下行號是為下文解釋代碼方便而放上去的，不是代碼的一局部：點擊(此處)折疊或翻開store3store2mulstore1subprint對這段代碼的說明如下：前兩行向棧頂添加兩個數(shù)字，先壓入3再壓入2,這樣棧頂?shù)臄?shù)字是2,第二個數(shù)字是3。第三行mul會從棧頂彈出兩個數(shù)字2和3計算乘法，并把結果6再壓入棧中，此時棧中只有一個數(shù)字6。第四行向棧頂壓入一個數(shù)字1,此時棧頂為1,第二個數(shù)字是6。第五行sub指令從棧頂取出兩個數(shù)字，第一個數(shù)字1做為被減數(shù)，第二個數(shù)字6做為減數(shù)，即計算1-6,并把結果壓入棧中，此時棧中只有一個數(shù)字-5。最

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

7、經歷，我們可以看到，所有的操作數(shù)的先后順序是從右向左store的，所以store指令的順序是固定下來的，剩下的關鍵是操作指令應該放在哪里。操作指令也是有一個規(guī)律的，即：當前棧頂?shù)臄?shù)據(jù)剛剛好滿足某運算時，那么操作指令就放在哪里，如：store1的時候沒有任何操作的操作數(shù)都在棧中。store4的時候，剛剛好sqrt的操作數(shù)都在棧中，那么此時參加sqrt指令。store3store2時，剛剛好可以計算pow。store10之后，就可以計算加法了，所以此時參加add指令。add計算完成之后，再加上之前已計算完的sqrt指令，那么此時乘法的所有操作數(shù)都在棧中了，那么此時參加mul指令。最后減操作也可以計

8、算了，那么加上sub指令。所有計算完成之后打印出結果。在這個例子中，我所說的“規(guī)律其實就是“后綴表達式。我們平常寫的算術表達式是“中綴的，即符號在操作數(shù)中間，如1+2,的+在1和2中間，轉為后綴形式即為12+這里因為我對于參數(shù)順序的設計是與“正常順序相反的，所以1+2對于這個匯編器來說，其后綴形式就應該為21+大家是可以按照這個規(guī)律，相對簡單的實現(xiàn)這個計算器一一只要做好詞法分析就可以按照后綴表達式的規(guī)律直接由tokenList生成匯編代碼了一一但我們的目的是用這個計算器的例子來講編譯，所以還是按步就班來講。詞法分析詞法分析的目的是把一段文本分解成詞法元素列表，例如(10+pow(2,3)*sq

9、rt(4)-1,做詞法分析之后會分解成如下幾個詞法元素：0ow)23*qrts(I4)這里只是做了一次文本處理一一在處理之前，我們手里有的東西就是一串字符組成的字符串，在處理之后，我們按照一定的“規(guī)那么分解為多個單詞。算法是多種多樣的，有創(chuàng)造力的程序員會想出各種方法來處理這個單詞分解的問題。在編譯原理中，普遍的方式是用如下一個狀態(tài)轉換圖來實現(xiàn)的在圖中，“橢圓形的是狀態(tài)，狀態(tài)與狀態(tài)之間有一條有方向的線，這個線代表從一個狀態(tài)到另一個狀態(tài)的路徑，在這條線上面有一個花括號代表從前一個狀態(tài)到達后一個狀態(tài)的輸入為方便表示，0-9表示從0到9十個數(shù)字，a-z表示從a到z二十六個字母等，如從START狀態(tài)開場

10、，輸入一個數(shù)字1,就會到達INT狀態(tài)。圖中藍色的狀態(tài)是終結狀態(tài)，如果從START狀態(tài)經過假設干輸入后到達終結狀態(tài)，那么這些輸入的字符可合并為詞法的合法單詞一一這里需要額外說明一點：在對輸入進展匹配狀態(tài)時采用貪婪方式，即：盡量輸入更多的字符。在識別到一個合法的詞法單元之后，狀態(tài)回到START繼續(xù)識別下一個元素，直到沒有新的元素為止。這個狀態(tài)轉換圖在編譯原理中有一個專有名詞稱呼它“確定有限狀態(tài)自動機，英文簡稱DFA。這里“確定的意思是每一個狀態(tài)經過一個輸入字符可以確定只有一條路徑到達另一個狀態(tài)，“有限的意思是，狀態(tài)的個數(shù)是有限的。對于一個復雜語言的狀態(tài)數(shù)量是這個狀態(tài)機的幾個數(shù)量級的大小。但我們現(xiàn)在

11、的計算器只需要這幾個狀態(tài)就夠了。通常的DFA會由工具讀取正那么方法描述而生成的，而不是直接手工構造，但對我們現(xiàn)在設計的計算器來說，其DFA非常小，手工構造是很方便的，所以就不用工具了。另外，如果使用工具的話，我這篇文章也不會使用現(xiàn)有的工具，而是自己實現(xiàn)一個工具。下面舉個例子：我們有一個表達式12.3+abc,下面我來描述一下DFA的運行過程：定義一個變量s,來表示當前狀態(tài)機所在的狀態(tài)初始時s=START。輸入第一個字符1,此時START狀態(tài)可承受這個輸入1,到達INT狀態(tài)，那么變量s賦值為INT狀態(tài)，此時可看到INT狀態(tài)的顏色是藍色表示當前可識別為一個合法的詞法元素，但因為我們的規(guī)那么是貪婪匹

12、配，所以我們還要看看是否還能夠匹配更多的字符。輸入第二個字符2,此時INT狀態(tài)也可以承受這人輸入，并到達INT狀態(tài)轉了一個圈又回到原來的狀態(tài)，此時變量s賦值為INT狀態(tài)。再輸入第三個字符.，此時INT狀態(tài)可承受.到達NUMBER狀態(tài)，此時變量s賦值為NUMBER狀態(tài)。此時我們再向前看一個字符+，此時的狀態(tài)NUMBER無法承受這個字符了，同時我們可在看到NUMBER狀態(tài)的顏色是藍色的，表示當前狀態(tài)可識別一個合法的詞法元素，即：從START開場到當前我們一共經歷的輸入為12.3，那么這個單詞做為第一個合法的詞法元素。第一個詞法元素識別成功之后，變量s要回到START狀態(tài)，并繼續(xù)輸入+，此時從STA

13、RT狀態(tài)可到達ADD狀態(tài)，且ADD狀態(tài)并不允許承受任何輸入，同時ADD狀態(tài)的顏色也是藍色的，那么我們又識別出第二個詞法元素+。在識別到第二個詞法元素之后，變更s要回到START狀態(tài)，并繼續(xù)輸入a，此時START狀態(tài)可由a指向的路徑到達ID狀態(tài)，此時s賦值為新的狀態(tài)ID?，F(xiàn)在的情況與識別NUMBER的情況類似，當前的狀態(tài)也是終結狀態(tài)，但按貪婪匹配的原那么還要繼續(xù)看看是否可以匹配到新的輸入。后面的b和c都在ID一個狀態(tài)里轉圈，我就不在贅述了，這樣我們就識別到了最后一個詞法元素abc了。用如上過程的方法可以識別任何正確的算術表達式，但還有幾點需要特別說明：如何識別錯誤：目前我見過的語言規(guī)都在描述如何

14、正確的編譯一個語言，但沒有一個規(guī)有描述如何報錯的，所以我們目前能做的是只要按正常的走法走不通了，那就是錯了，就要報錯，并盡可能提供詳細的錯誤信息。對空白的識別：我在DFA中并沒有畫識別空白的局部，原因是對于計算器程序來說，空白完全沒有用處，所以我只是在代碼中直接忽略這個輸入，以免狀態(tài)機無法識別空白，同時在識別到詞法元素之后，去掉單詞前后的空白。對于某些語言來說，空白是有意義的，需要做為詞法元素識別出來，不能忽略掉。對于詞法元素的表示：通常我們會用一個類型Token來表示一個詞法元素，Token中有兩個屬性，一個用于表示這個Token的類型，另一個用于表示容，只有數(shù)字與標識符才需要使用Token

15、類型的容屬性，其它的類型因為同一類型只有一種表示的可能，所以就不需要再把容保存下來了如ADD的容+。關于標識符：DFA中的ID狀態(tài)用于識別標識符，這里的標識符包括自定義的變量，也包括函數(shù)名。在DFA的設計過程中，我們可以選擇把普通標識符與保存字做為不同的狀態(tài)，也可以用使用同一個狀態(tài)。我們現(xiàn)在的設計就使用了一個ID狀態(tài)表示所有的標識符，而在識別到一個ID之后，我們在看是否是一個保存字，這樣在返回Token對象時設置不同的類型。對于INT和NUMBER:這個計算器的所有計算都使用的是double類型的數(shù)字，所在雖然我們的詞法可以識別到INT，但我們定義Token的類型時，就只定義一個NUMBER類

16、型，INT或NUMBER狀態(tài)確定的單詞都返回NUMBER這個類型的Token對象。前面的邏輯中有一個貪婪批配的原那么，這個原那么在某些語言的詞法中會有一些特例不適用，例如在C+和JAVA中都有一個運算符“，這個運算符代表右移，但在C+11標準中可以寫出這樣的代碼std:vectorstd:vector，在JDK5及以上版本也可以這樣寫ListList，這里如果按貪婪批配就錯了。所以必須在詞法分析中參加上下文的判斷才能決定是按兩個來識別還是按一個來識別上下文的判斷是語法分析的局部了，但對于復雜的詞法構造在沒有一個統(tǒng)一的詞法解析算法可以處理的情況下就得借助更高級的方法了?，F(xiàn)在剩下的就是寫代碼了。如

17、果我把代碼貼在這里就太長了，不太適宜。所以下面我只描述一下描述DFA的思路：思路一：直接靜態(tài)代碼來描述，類似這樣的方式把狀態(tài)機的每個路徑都描述出來：IFS=STARTANDc=1THENS=INT.ELSIF，這樣就可以輸入運行了。思路二：表格驅動式的，例如列出下面的表格即可知道哪個狀態(tài)經過哪個輸入之后到達哪個新的狀態(tài)了一一下表的左標題是當前的狀態(tài)，上標題是在當前狀態(tài)上的輸入，表格中的容是經過路徑到達的狀態(tài)。思路三：結合前兩個思路一一先寫一個代碼生成工具，工具讀取“思路二中表格中的容，并生成“思路一中的靜態(tài)代碼。0-9._a-zA-Z+-*/(),STARTNTPOINTIDADDSUBMUL

18、DIVLBTRBTMAINTNTNUMBERPOINTNUMBERNUMBERNUMBERIDDIDADDSUBMULDIVLBTRBTMA下面舉一下DFA返回的Token對象的類型：NUM,FUN,VAR,ADD,SUB,MUL,DIV,LBT,RBT,MA這里前三個與DFA的狀態(tài)名不同：NUM代表INT狀態(tài)和NUMBER狀態(tài)兩個狀態(tài)識別出的詞法元素。FUN和VAR者B是ID狀態(tài)識別出的元素，如果這個ID是一個函數(shù)名，那么Token為FUN類型，否那么即為VAR類型。其它類型與DFA的狀態(tài)是對應的。最后說一下DFA的接口：假設DFA有一個方法叫做parse,那么這個方法的參數(shù)只有一個字符串用

19、于傳入表達式即可。如果我們寫的DFA是用于解析長文本的而不僅僅是解析這個簡短的算術表達式，那么可以考慮參數(shù)為輸入流。parse方法的返回可以考慮返回一個Token的游標，游標供語法分析程序調用；也可以考慮解析完所有的詞法元素返回一個Token的列表。因為目前比擬通用的語法分析算法只需要向前看一個Token對象，所以游標就足夠了。因為語法分析程序有可能會把已讀出來的Token放回去，下次再用，所以游標可考慮加一個putBack方法一一也可以考慮不實現(xiàn)這個方法，而由語法分析程序自己緩存當前用不到的詞法元素一一如果DFA返回的是list就簡單一些，語法分析器可以前后前后移動0fset即可。DFA返回

20、list的方式實現(xiàn)雖然簡單一點，但對于要解析的數(shù)據(jù)非常大的情況就不適用了尤其數(shù)據(jù)是從網絡上以流的方式傳過來的，這樣我們根本不知道什么時候這個流會完畢，所以還是需要一個元素就返回一個元素的做法比擬平安對于我們現(xiàn)在做的計算器的程序來說，隨便怎么做都可以了。語法分析語法分析是把詞法分析過程返回的tokenList轉換為語法樹的過程。詞法分析的結果是為語法分析效勞的，語法分析自然也是為下一步的語義分析做準備的，在這一節(jié)中，我們只講一下語法樹是怎么構造的，下一節(jié)語義分析的局部再講如何使用語法樹。語法樹是一個樹形的數(shù)據(jù)構造，樹的每個根節(jié)點表示一個語法構造，子節(jié)點表示構成根這個大語法構造的小語法構造。這樣不

21、斷劃分更小的語法構造直到無法再分的子節(jié)點，其實就是一個整體與局部的關系。因樹形構造是要畫圖的，但我們通常的工具是文本工具，所以我們通常用類似以下文本形式來表示樹形構造：NODE1-NODE2NODE3NODE2-NODE4這個表示的意思是：NODE1為根節(jié)點，NODE1有兩個子節(jié)點NODE2和NODE3，NODE2又有一個子節(jié)點NODE4。這樣即可用文本的形式表示樹形構造了。這種表示形式叫“巴科斯式，英文簡稱為BNF下文中有需要表示這個名稱的地方，我就直接用BNF三個字母來代替了。下面我們看一下這個計算器的BNF對于復雜語言的BNF描述要寫幾十頁，但我們的計算器就只有這么幾行：點擊(此處)折疊

22、或翻開exp-termexp-term+expexp-term-expterm-factorterm-factor*termterm-factor/termfactor-varNamefactor-numberfactor-numberfactor-funCallfactor-(exp)funCall-funName(params)params-expparams-exp,params下面對這個語法構造描述一下：exp為算術表達式，即為我們要分析的表達式整體。term是可做加法或減法的項。我們可看到exp有三行表示基構造，這三行是或的關系，即：exp可能是一個term,也可能是一個term加上

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

24、表達式。funName是函數(shù)名，params是函數(shù)調用的參數(shù)。funCall的構造為：函數(shù)名后跟著一個括號，再跟著一個或多個參數(shù)，再跟著一個括回。params由兩個產生式，因每個參數(shù)都可以是單獨的算術表達式，所以一個exp節(jié)點即可表示一個參數(shù)，如果有多個參數(shù)，那么exp后成要跟著一個逗號，之后再跟著其它的參數(shù)。這種表示方法相對于樹形的表示來說，有一個優(yōu)點，即：相比照擬容易表示或，比方factor這個節(jié)點可能由變量名來表示，也可能由數(shù)字來表示，如可能是，這樣我們如果畫圖的話，如何表示多種可能中只選其中一種的情況呢？上面的表示是對語法構造的抽象表示，抽象的東西還是具體化為我們的代碼中的數(shù)據(jù)構造的。

25、我們的目的是把我們的算術表達式變成符合語法樹描述的樣子，舉個例子來說：（1+2）*3轉成語法語法樹就是下列圖所示的樣子：圖中藍色的局部為語法樹的葉子節(jié)點，也就是不能再分解的節(jié)點。這些葉子節(jié)點正是詞法分析局部的詞法元素。下面我們看一下來看一下構造這個樹的步驟:上面的圖中只有三種非葉子節(jié)點的類型exp、term、factor以及幾個葉子節(jié)點的類型number、*、+、（、），所以下面我只以這幾個為例做一下描述，其它的節(jié)點類型的解析步驟是類似的因+*（）這幾個符號在描述中會不太好看，所以下文中我改用add、mul、lbt、rbt來表示。節(jié)點的類型：我們可以為每種節(jié)點類型單獨創(chuàng)立一個類，如：exp類型

26、的節(jié)點即為Exp類型的對象，term類型的節(jié)點即為Term類型的對象也可以考慮只用一個類型TreeNode,而用Node中的一個屬性type來表示不同的節(jié)點類型。我選擇用第二種方式來表示節(jié)點的類型，這樣對于子節(jié)點的表示也相對簡單的直接用一個list即可。對于number類型的節(jié)點，還需要一個屬性來表示數(shù)字的容，所以TreeNode類中除了type字段之外，還要有一個content字段varName或funName類型也是需要content字段的，用于表示變量名或函數(shù)名。為每個非葉子節(jié)點寫一個函數(shù)來解析這個語法構造，如：parseExp、parseTerm、parseFactor;因為我們每個語

27、法構造或子語法構造者B是TreeNode類型的對象為根的樹，所以這幾個函數(shù)的返回值類型為TreeNode。每個函數(shù)的構造化代碼與BNF中的描述可完全對應得上，比方：exp有三個產生式：exp-term和exp-term+exp和exp-term-exp,刃B么parseExp的代碼可以按下面的步驟來寫：創(chuàng)立一個類TreeNode的對象expNode,并指定其類型為exp。調用parseTerm函數(shù)解析出expNode的第一個子元素termNode。向前看下一個詞法元素如果還有下一個的話：如果為add或sub類型的Token，那么創(chuàng)立第二個子元素opNode這個元素的類型為add或sub，之后再

28、遞歸調用parseExp解析第三個子元素。如果不為add或sub類型的Token,那么一定是出錯了。反回expNode。term有三個產生式：term-factor和term-factor*term和term-factor/term,這三個產生式與exp的三個產生式是同一個格式的，所以代碼也幾乎是一樣的。factor有五個產生式，但我們現(xiàn)在這個例子用不到變更和函數(shù)，所以只看其中的三個：factor-number和factor-number和factor-（exp）,那么parseFactor的代碼可以這樣寫：創(chuàng)立一個類TreeNode的對象factorNode，并指定其類型為factor。向前

29、看一個詞法元素：如果是num類型的Token,那么創(chuàng)立一個number類型的TreeNode對象彳故為factorNode的子節(jié)點這個節(jié)點的content值為當前這個Token的值。如果是sub類型的Token,那么再從tokenList中讀出一個num,創(chuàng)立一個number類型的TreeNode做為factorNode的子節(jié)點這個節(jié)點的content值為當前這個Token的值把符號位反過來。如果是lbt類型的，那么先創(chuàng)立一個lbt類型的TreeNode做為factorNode的第一個子節(jié)點，再調用parseExp函數(shù)來獲得第二個子節(jié)點，再向前看一個Token，如果是rbt類型的，那么創(chuàng)立一個

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

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

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

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

34、術表達式的語法樹可以用以更簡單的構造，例如：表達式(10+pow(2,3)*sqrt(4)-1的語法樹可以表示成下面的圖形：1這個圖顯然比正統(tǒng)的語法解析方式的結果樹要小很多一一因為這個樹中只有終結符號,exp、term、factor等非終結符號是不存在的。對于這樣的語法樹的語義分析也更簡單，后面講語義分析時再講一下如何解析這個袖珍版本的語法樹。這個樹的構造即：所有的葉子節(jié)點都是操作數(shù)，所有的根節(jié)點都是操作符一一同時大家也可以注意到括號不見了，實際上括號在語法樹中也是不必要的。至于這個語法樹如何構造就留個懸念，不在這里講了。語義分析語義分析是把語法樹轉成中間代碼，再由中間代碼轉成目標代碼。但對于簡單的分析來說，我們省略中間代碼的步驟，直接讀語法樹生成目標代碼目標代碼即為前面講過的ASM代碼。雖然對于復雜的語言來說語義分析這個局部是非常復雜，但對于語法與設計都很簡單的語言來說語義分析這個局部簡直簡單到可以合并到語法分析的過程中去做了，只是我們現(xiàn)在的目的是用計算器的例子來講編譯過程，所以這個局部還是簡單講一講。我之所以說這個計算器的語義分析可以合并到語法分析中是因為計算器的構造中沒有上下文的判斷，所以語法分析不報錯的話，語義分析就一定沒有問題了。我們還是以在語法分析中的（1+2）*3的例子來講語義分析，這個表達式的語法樹還是這個：語法分析是構造語法樹，語義分析是讀語法樹，所以語