基于編譯原理的計算器設計與實現

基于編譯原理的計算器設計與實現一方面看一下這個計算器的功能：CALC>seta=1;b=2CALC>setc=3CALC>calc(10+pow(b,c))*sqrt(4)-135.0CALC>exit如上所示，這個計算器的功能非常簡樸：用set命令設立上下文中的變量。用calc命令計算一個表達式的值。用exit命令退出計算器。我們把編譯的重點放在calc命令后面的計算表達式的解析，其它的部分我們可以簡樸解決（如set命令可以這樣簡樸解決：先按分號分隔得到多個賦值解決，再按等號分隔就可以在上下文中設立變量了，并不需要復雜的編譯過程）。如上的演示例子中，我們使用編譯技術解決的部分是(10+pow(b,c))*sqrt(4)-1，其它部分我們只使用簡樸的文本解決。麻雀雖小，但五臟俱全，這個計算器包含編譯技術中最必要的部分。雖然這次我們只是實現了一個計算器，但所使用的技術足以實現一個簡樸的腳本語言的解釋器了。這個計算器分為如下幾個部分：詞法分析：把表達式的文本，解析成詞法元素列表(tokenList)。語法分析：把tokenList解析成語法樹(syntaxTree)。語義分析：把語法樹轉成匯編語言的代碼(asm)匯編器：把匯編代碼翻譯為機器碼（字節(jié)碼）。虛擬機：執(zhí)行字節(jié)碼。一般的編譯步聚中不包含“匯編器”和“虛擬機”，而這里之所以包含這兩個部分是由于：通常編譯器會直接由中間代碼生成機器碼，而不是生成匯編代碼，而這里我之所以要生成匯編代碼的因素是“調試的時候匯編的可讀性很好”，假如直接生成目的代碼，則會非常難用肉眼來閱讀。自己實現虛擬機的因素是：現有的機器（涉及物理機和虛擬機以及模擬器）的指令雖然也很豐富，但似乎都沒有直接計算“乘方”或“開方”的指令，自已實現虛擬機可以任意設計計算指令，這樣可以減少整個程序的復雜度。因匯編器與虛擬機并不是編譯原理的部分，所以下文中并不會描述其實現細節(jié)，但由于計算器代碼編譯后的目的代碼就是匯編代碼，所以需要把匯編指令做一下說明（以下把這個匯編語言簡稱為ASM）。

ASM指令介紹指令助記符操作數指命說明storenumber把number放入棧頂add從棧頂取出兩個數相加，并把結果壓回棧中sub從棧頂取出一個數做為被減數，再取一個做為減數，相減之后的結果入棧mul從棧頂取出兩個數相乘，并把結果入棧div從棧頂取出一個數做為除法的分子，再取出一個做為除法的分母，相除的結果入棧pow從棧頂取出一個數做為底，再取出一個做為冪，計算結果入棧sqrt從棧頂取出一個數，把這個數開平方后的結果入棧print在控制臺打印棧頂的數字這個虛擬機是基于棧來設計的，所有的計算指令的操作數都從棧中取，store命令向棧頂添加數據。print指令用于打印當前棧頂的數據，在我們編譯的匯編代碼要做到：對的計算出結果，且計算完畢之后的結果要剛好在棧頂，這樣最后調用一個print指令即可以控制臺看到計算結果。ASM舉例：例1，假如我們要計算1-2*3，則我們寫出的匯編代碼如下（行號是為下文解釋代碼方便而放上去的，不是代碼的一部分）：點擊(此處)折疊或打開store3store2mulstore1subprint對這段代碼的說明如下：前兩行向棧頂添加兩個數字，先壓入3再壓入2，這樣棧頂的數字是2，第二個數字是3。第三行mul會從棧頂彈出兩個數字（2和3）計算乘法，并把結果（6）再壓入棧中，此時棧中只有一個數字6。第四行向棧頂壓入一個數字1，此時棧頂為1，第二個數字是6。第五行sub指令從棧頂取出兩個數字，第一個數字1做為被減數，第二個數字6做為減數，即計算1-6，并把結果壓入棧中，此時棧中只有一個數字-5。最后一行print指令不對棧做寫操作，只讀取棧頂的數字，并打印出來。在這里，我們用到兩個運算，mul和sub，這兩個運算都是二元運算，因我在設計指令的時候，先取出來的數字是第一個操作數，所以先壓入的應當是第二個操作數，這也是為什么代碼中先壓入的是3，之后是2，最后才是1。例2，假如我們要計算(10+pow(2,3))*sqrt(4)-1，則我們寫出的匯編代碼如下（行號是為下文解釋代碼方便而放上去的，不是代碼的一部分）：點擊(此處)折疊或打開store1store4sqrtstore3store2powstore10addmulsubprint對這段代碼的說明如下：這段代碼稍有點復雜，但有前一段代碼的經驗，我們可以看到，所有的操作數的先后順序是從右向左store的，所以store指令的順序是固定下來的，剩下的關鍵是操作指令應當放在哪里。操作指令也是有一個規(guī)律的，即：當前棧頂的數據剛剛好滿足某運算時，則操作指令就放在哪里，如：store1的時候沒有任何操作的操作數都在棧中。store4的時候，剛剛好sqrt的操作數都在棧中，則此時加入sqrt指令。store3store2時，剛剛好可以計算pow。store10之后，就可以計算加法了，所以此時加入add指令。add計算完畢之后，再加上之前已計算完的sqrt指令，則此時乘法的所有操作數都在棧中了，則此時加入mul指令。最后減操作也可以計算了，則加上sub指令。所有計算完畢之后打印出結果。在這個例子中，我所說的“規(guī)律”其實就是“后綴表達式”。我們平常寫的算術表達式是“中綴”的，即符號在操作數中間，如1+2，的+在1和2中間，轉為后綴形式即為12+這里由于我對于參數順序的設計是與“正?！表樞蛳喾吹?，所以1+2對于這個匯編器來說，其后綴形式就應當為21+大家是可以按照這個規(guī)律，相對簡樸的實現這個計算器——只要做好詞法分析就可以按照后綴表達式的規(guī)律直接由tokenList生成匯編代碼了——但我們的目的是用這個計算器的例子來講編譯，所以還是按步就班來講。詞法分析詞法分析的目的是把一段文本分解成詞法元素列表，例如(10+pow(2,3))*sqrt(4)-1，做詞法分析之后會分解成如下幾個詞法元素：（10+pow(2,3))*sqrt(4)-1這里只是做了一次文本解決——在解決之前，我們手里有的東西就是一串字符組成的字符串，在解決之后，我們按照一定的“規(guī)則”分解為多個單詞。算法是多種多樣的，有發(fā)明力的程序員會想出各種辦法來解決這個單詞分解的問題。在編譯原理中，普遍的方式是用如下一個狀態(tài)轉換圖來實現的在圖中，“橢圓形”的是狀態(tài)，狀態(tài)與狀態(tài)之間有一條有方向的線，這個線代表從一個狀態(tài)到另一個狀態(tài)的途徑，在這條線上面有一個花括號代表從前一個狀態(tài)到達后一個狀態(tài)的輸入（為方便表達，0-9表達從0到9十個數字，a-z表達從a到z二十六個字母等），如從START狀態(tài)開始，輸入一個數字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)的個數是有限的。對于一個復雜語言的狀態(tài)數量是這個狀態(tài)機的幾個數量級的大小。但我們現在的計算器只需要這幾個狀態(tài)就夠了。通常的DFA會由工具讀取正則方法描述而生成的，而不是直接手工構造，但對我們現在設計的計算器來說，其DFA非常小，手工構造是很方便的，所以就不用工具了。此外，假如使用工具的話，我這篇文章也不會使用現有的工具，而是自己實現一個工具。下面舉個例子：我們有一個表達式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ī)則是貪婪匹配，所以我們還要看看是否還可以匹配更多的字符。輸入第二個字符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ù)輸入+，此時從START狀態(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在的情況與辨認NUMBER的情況類似，當前的狀態(tài)也是終結狀態(tài)，但按貪婪匹配的原則還要繼續(xù)看看是否可以匹配到新的輸入。后面的b和c都在ID一個狀態(tài)里轉圈，我就不在贅述了，這樣我們就辨認到了最后一個詞法元素abc了。用如上過程的方法可以辨認任何對的的算術表達式，但尚有幾點需要特別說明：如何辨認錯誤：目前我見過的語言規(guī)范都在描述如何對的的編譯一個語言，但沒有一個規(guī)范有描述如何報錯的，所以我們目前能做的是只要按正常的走法走不通了，那就是錯了，就要報錯，并盡也許提供具體的錯誤信息。對空白的辨認：我在DFA中并沒有畫辨認空白的部分，因素是對于計算器程序來說，空白完全沒有用處，所以我只是在代碼中直接忽略這個輸入，以免狀態(tài)機無法辨認空白，同時在辨認到詞法元素之后，去掉單詞前后的空白。對于某些語言來說，空白是故意義的，需要做為詞法元素辨認出來，不能忽略掉。對于詞法元素的表達：通常我們會用一個類型Token來表達一個詞法元素，Token中有兩個屬性，一個用于表達這個Token的類型，另一個用于表達內容，只有數字與標記符才需要使用Token類型的內容屬性，其它的類型由于同一類型只有一種表達的也許，所以就不需要再把內容保存下來了（如ADD的內容一定是+）。關于標記符：DFA中的ID狀態(tài)用于辨認標記符，這里的標記符涉及自定義的變量，也涉及函數名。在DFA的設計過程中，我們可以選擇把普通標記符與保存字做為不同的狀態(tài)，也可以用使用同一個狀態(tài)。我們現在的設計就使用了一個ID狀態(tài)表達所有的標記符，而在辨認到一個ID之后，我們在看是否是一個保存字，這樣在返回Token對象時設立不同的類型。對于INT和NUMBER：這個計算器的所有計算都使用的是double類型的數字，所在雖然我們的詞法可以辨認到INT，但我們定義Token的類型時，就只定義一個NUMBER類型，INT或NUMBER狀態(tài)擬定的單詞都返回NUMBER這個類型的Token對象。前面的邏輯中有一個貪婪批配的原則，這個原則在某些語言的詞法中會有一些特例不合用，例如在C++和JAVA中都有一個運算符“>>”，這個運算符代表右移，但在C++11標準中可以寫出這樣的代碼std::vector<std::vector<int>>，在JDK5及以上版本也可以這樣寫List<List<Integer>>，這里假如按貪婪批配就錯了。所以必須在詞法分析中加入上下文的判斷才干決定是按兩個>來辨認還是按一個>>來辨認——上下文的判斷是語法分析的部分了，但對于復雜的詞法結構在沒有一個統(tǒng)一的詞法解析算法可以解決的情況下就得借助更高級的方法了。現在剩下的就是寫代碼了。假如我把代碼貼在這里就太長了，不太合適。所以下面我只描述一下描述DFA的思緒：思緒一：直接靜態(tài)代碼來描述，類似這樣的方式把狀態(tài)機的每個途徑都描述出來：IFS=STARTANDc=‘1’THENS=INT...ELSIF...，這樣就可以輸入運營了。思緒二：表格驅動式的，例如列出下面的表格即可知道哪個狀態(tài)通過哪個輸入之后到達哪個新的狀態(tài)了——下表的左標題是當前的狀態(tài)，上標題是在當前狀態(tài)上的輸入，表格中的內容是通過途徑到達的狀態(tài)。思緒三：結合前兩個思緒——先寫一個代碼生成工具，工具讀取“思緒二”中表格中的內容，并生成“思緒一”中的靜態(tài)代碼。[0-9].[_a-zA-Z]+-*/(),STARTINTPOINTIDADDSUBMULDIVLBTRBTCOMMAINTINTNUMBERPOINTNUMBERNUMBERNUMBERIDIDIDADDSUBMULDIVLBTRBTCOMMA下面舉一下DFA返回的Token對象的類型：NUM，FUN，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是一個函數名，則Token為FUN類型，否則即為VAR類型。其它類型與DFA的狀態(tài)是一一相應的。最后說一下DFA的接口：假設DFA有一個方法叫做parse，則這個方法的參數只有一個字符串用于傳入表達式即可。假如我們寫的DFA是用于解析長文本的（而不僅僅是解析這個簡短的算術表達式），則可以考慮參數為輸入流。parse方法的返回可以考慮返回一個Token的游標，游標供語法分析程序調用；也可以考慮解析完所有的詞法元素返回一個Token的列表。由于目前比較通用的語法分析算法只需要向前看一個Token對象，所以游標就足夠了。由于語法分析程序有也許會把已讀出來的Token放回去，下次再用，所以游標可考慮加一個putBack方法——也可以考慮不實現這個方法，而由語法分析程序自己緩存當前用不到的詞法元素——假如DFA返回的是list就簡樸一些，語法分析器可以前后前后移動offset即可。DFA返回list的方式實現雖然簡樸一點，但對于要解析的數據非常大的情況就不合用了——特別數據是從網絡上以流的方式傳過來的，這樣我們主線不知道什么時候這個流會結束，所以還是需要一個元素就返回一個元素的做法比較安全——對于我們現在做的計算器的程序來說，隨便怎么做都可以了。語法分析語法分析是把詞法分析過程返回的tokenList轉換為語法樹的過程。詞法分析的結果是為語法分析服務的，語法分析自然也是為下一步的語義分析做準備的，在這一節(jié)中，我們只講一下語法樹是怎么構造的，下一節(jié)語義分析的部分再講如何使用語法樹。語法樹是一個樹形的數據結構，樹的每個根節(jié)點表達一個語法結構，子節(jié)點表達構成根這個大語法結構的小語法結構。這樣不斷劃分更小的語法結構直到無法再分的子節(jié)點，其實就是一個整體與部分的關系。因樹形結構是要畫圖的，但我們通常的工具是文本工具，所以我們通常用類似以下文本形式來表達樹形結構：NODE1

->

NODE2NODE3NODE2

->NODE4這個表達的意思是：NODE1為根節(jié)點，NODE1有兩個子節(jié)點NODE2和NODE3，NODE2又有一個子節(jié)點NODE4。這樣即可用文本的形式表達樹形結構了。這種表達形式叫“巴科斯范式”，英文簡稱為BNF——下文中有需要表達這個名稱的地方，我就直接用BNF三個字母來代替了。下面我們看一下這個計算器的BNF（對于復雜語言的BNF描述要寫幾十頁，但我們的計算器就只有這么幾行）：點擊(此處)折疊或打開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加上一個exp，也也許是一個term減掉一個exp。也就是說，exp這個根節(jié)點的子節(jié)點也許只有一個節(jié)點，也也許有三個節(jié)點。factor是可做乘法或除法的項。term繼續(xù)分解的過程與exp是完全同樣的，這里就不再贅述。這里把加減法與乘除法分開為兩種語法結構的因素是，乘法與除法的優(yōu)先級高于加法與減法，按照我們現在的表達，在計算加法或減法之前必須先計算term，這樣因term是先計算的，所以優(yōu)先級就表達出來了。varName是變量名，number是數字，funCall是函數調用對于factor的組成部分就可理解為：可認為一個變量，或一個數字，或一個減號連著一個數字（負數），或一次函數調用，或用小括號括起來的表達式。funName是函數名，params是函數調用的參數。funCall的結構為：函數名后跟著一個括號，再跟著一個或多個參數，再跟著一個括回。params由兩個產生式，因每個參數都可以是單獨的算術表達式，所以一個exp節(jié)點即可表達一個參數，假如有多個參數，則exp后成要跟著一個逗號，之后再跟著其它的參數。這種表達方法相對于樹形的表達來說，有一個優(yōu)點，即：相對比較容易表達“或”，比如factor這個節(jié)點也許由變量名來表達，也也許由數字來表達，如也許是……，這樣我們假如畫圖的話，如何表達多種也許中只選其中一種的情況呢？上面的表達是對語法結構的抽象表達，抽象的東西還是具體化為我們的代碼中的數據結構的。我們的目的是把我們的算術表達式變成符合語法樹描述的樣子，舉個例子來說：(1+2)*3轉成語法語法樹就是下圖所示的樣子：圖中藍色的部分為語法樹的葉子節(jié)點，也就是不能再分解的節(jié)點。這些葉子節(jié)點正是詞法分析部分的詞法元素。下面我們看一下來看一下構造這個樹的環(huán)節(jié)：上面的圖中只有三種非葉子節(jié)點的類型（exp、term、factor）以及幾個葉子節(jié)點的類型[number、*、+、(、)]，所以下面我只以這幾個為例做一下描述，其它的節(jié)點類型的解析環(huán)節(jié)是類似的——因+*()這幾個符號在描述中會不太好看，所以下文中我改用add、mul、lbt、rbt來表達。節(jié)點的類型：我們可認為每種節(jié)點類型單獨創(chuàng)建一個類，如：exp類型的節(jié)點即為Exp類型的對象，term類型的節(jié)點即為Term類型的對象……也可以考慮只用一個類型TreeNode，而用Node中的一個屬性type來表達不同的節(jié)點類型。我選擇用第二種方式來表達節(jié)點的類型，這樣對于子節(jié)點的表達也相對簡樸的直接用一個list即可。對于number類型的節(jié)點，還需要一個屬性來表達數字的內容，所以TreeNode類中除了type字段之外，還要有一個content字段——varName或funName類型也是需要content字段的，用于表達變量名或函數名。為每個非葉子節(jié)點寫一個函數來解析這個語法結構，如：parseExp、parseTerm、parseFactor，由于我們每個語法結構（或子語法結構）都是TreeNode類型的對象為根的樹，所以這幾個函數的返回值類型為TreeNode。每個函數內的結構化代碼與BNF中的描述可完全相應得上，比如：exp有三個產生式："exp->term"和"exp->term+exp"和"exp->term-exp"，則parseExp的代碼可以按下面的環(huán)節(jié)來寫：創(chuàng)建一個類TreeNode的對象expNode，并指定其類型為exp。調用parseTerm函數解析出expNode的第一個子元素termNode。向前看下一個詞法元素（假如尚有下一個的話）：假如為add或sub類型的Token，則創(chuàng)建第二個子元素opNode（這個元素的類型為add或sub），之后再遞歸調用parseExp解析第三個子元素。假如不為add或sub類型的Token，則一定是犯錯了。反回expNode。term有三個產生式："term->factor"和"term->factor*term"和"term->factor/term"，這三個產生式與exp的三個產生式是同一個格式的，所以代碼也幾乎是同樣的。factor有五個產生式，但我們現在這個例子用不到變更和函數，所以只看其中的三個："factor->number"和"factor->-number"和"factor->(exp)"，則parseFactor的代碼可以這樣寫：創(chuàng)建一個類TreeNode的對象factorNode，并指定其類型為factor。向前看一個詞法元素：假如是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函數來獲得第二個子節(jié)點，再向前看一個Token，假如是rbt類型的，則創(chuàng)建一個rbt類型的Token做為第三個子節(jié)點（假如看到的不是rbt類型的就要報語法錯誤了）。返回factorNode。按上面描述的邏輯實現代碼是要不了多少行代碼就可以實現這個計算器的語法解析了。尚有兩個funCall和params，這兩個類型的解析與exp或term或factor差不多，就不再描述了。下面還要說一點額外的注意事項：我們現在寫代碼這種方式叫做LL(1)型，也叫遞歸向下型的語法分析，在這種語法分析方式中，我們總是先創(chuàng)建根節(jié)點，再創(chuàng)建子節(jié)點，在創(chuàng)建子節(jié)點時，我們總是由最左邊的節(jié)點開始一個一個去創(chuàng)建（如parseExp中，我們先創(chuàng)建出來的就是expNode，然后再創(chuàng)建的是termNode，之后假如尚有元素的話就會創(chuàng)建opNode和下一個expNode），這種語法解析方式是最容易用代碼實現的，所以我才使用這種方式來做，但這種解析方式有一個局限性：語法的BNF描述中不能有左遞歸。何為左遞歸呢？舉個例子來說：exp的產生式中的兩個"exp->term+exp"和"exp->term-exp"，假如改為"exp->exp+

term"和"exp->

exp-term"，也是對的，但按照這樣的產生式來寫代碼時，第一個要解析的就不是term，則還是一個exp，要解析第一個TreeNode就要遞歸調用parseExp函數了，這樣就會形成無限的遞歸了。所以我們在設計LL(1)型的文法描述時要避免左遞歸。LL(1)的文法設計在解析復雜的語言時會有語法描述上的局限性，如：C語言的一條語句開頭假如為ABC，則這個ABC也許一個變量名，也也許是行號，此時必須再向前看一個Token才干知道應當使用哪個產生式，這就變成LL(2)型了——LL后面括號中的數字代表我們在辨認語法產生式時，要向前看幾個Token——這樣的語法解析的代碼就復雜很多了。那么，有沒有實現簡單，且語法描述能力又強的解析方法呢？答案為：是有的。但本文只需要實現計算器的語法，就沒有必要喧賓奪主來花費大量的篇幅來寫其它的語法解析方式。以后假如有時間可專門再寫一個博文來講語法解析。語法分析有時也是要判斷上下文的，比如：假設在C++代碼中有這樣的一句：f<A,B>(c);這句代碼在沒有上下文的情況下是不能判斷是什么，它也許是一個函數調用（f是函數名，A和B是范形參數，c是函數的參數），也也許是一個逗號表達式（f，A，B，c都是變量或值，這一名就表達為f小于A，B大于c）——其實這是C++語法上的一個考慮不周之處，這給編譯器的設計者帶來了很大的麻煩，JAVA對于范型方法的調用就避免了C++的尷尬：JAVA中范型參數位置不在方法名與參數之間，而在方法名之前，如：<A,B>f(c)，這樣就不會與其它的JAVA語法沖突了。從這也可看出，語法的設計對語法解析程序的編寫影響是非常直接的。最后再講一點稍微偏門一點的東西：上面講的解析過程是正統(tǒng)的語法解析方式，用這樣的方式來解析計算器的算術表達式有點殺雞用牛刀的感覺。對于算術表達式的語法樹可以用以更簡樸的結構，例如：表達式(10+pow(2,3))*sqrt(4)-1的語法樹可以表達成下面的圖形：這個圖顯然比正統(tǒng)的語法解析方式的結果樹要小很多——由于這個樹中只有終結符號，exp、term、factor等非終結符號是不存在的。對于這樣的語法樹的語義分析也更簡樸，后面講語義分析時再講一下如何解析這個袖珍版本的語法樹。這個樹的構造即：所有的葉子節(jié)點都是操作數，所有的根節(jié)點都是操作符——同時大家也可以注意到括號不見了，事實上括號在語法樹中也是不必要的。至于這個語法樹如何構造就留個懸念，不在這里講了。語義分析語義分析是把語法樹轉成中間代碼，再由中間代碼轉成目的代碼。但對于簡樸的分析來說，我們省略中間代碼的環(huán)節(jié)，直接讀語法樹生成目的代碼（目的代碼即為前面講過的ASM代碼）。雖然對于復雜的語言來說語義分析這個部分是非常復雜，但對于語法與設計都很簡樸的語言來說語義分析這個部分簡直簡樸到可以合并到語法分析的過程中去做了，只是我們現在的目的是用計算器的例子來講編譯過程，所以這個部分還是簡樸講一講。我之所以說這個計算器的語義分析可以合并到語法分析中是由于計算器的結構中沒有上下文的判斷，所以語法分析不報錯的話，語義分析就一定沒有問題了。我們還是以在語法分析中的(1+2)*3的例子來講語義分析，這個表達式的語法樹還是這個：