概述

佛法有云：“實(shí)相無相，即見如來”。筆者理解，實(shí)際上所謂“實(shí)相”就是事物的本質(zhì)，也就是說我們理解事物的本質(zhì)不能僅從外觀或主觀感受來臆測，而應(yīng)該透過其外在表現(xiàn)而達(dá)到其本質(zhì)，就是所謂的“即見如來”。

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),羅莊企業(yè)網(wǎng)站建設(shè),羅莊品牌網(wǎng)站建設(shè),網(wǎng)站定制,羅莊網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,羅莊網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

   那么簡單而來說，如果我們想利用一點(diǎn)掌握的編譯技術(shù)，自主開發(fā)一個(gè)腳本的解析或解釋引擎，應(yīng)從哪里下手？或則說腳本解釋技術(shù)的“實(shí)相”是什么？

如想入門，個(gè)人理解應(yīng)至少對“遞歸”的概念和實(shí)踐有所了解或基本掌握。那么開啟這扇大門的鑰匙就是對于表達(dá)式的解析，毫不夸張地說，對于表達(dá)式完美地解析或解釋是成功開發(fā)類似解釋腳本的一半（可能至少是一半）。你在開發(fā)的過程中也可體會(huì)到運(yùn)用“遞歸”的美妙之處。

   什么事表達(dá)式？我也曾經(jīng)千百次地問自己，表達(dá)式的準(zhǔn)確定義是什么？百度上給出的答案是：

由數(shù)字、算符、數(shù)字分組符號(括號)、自由變量和約束變量等以能求得數(shù)值的有意義排列方法所得的組合。約束變量在表達(dá)式中已被指定數(shù)值，而自由變量則可以在表達(dá)式之外另行指定數(shù)值。

個(gè)人認(rèn)為上述的定義算是能基本上表達(dá)出了其含義。

   簡而言之，表達(dá)式就是由算符、常量（可能還有字符串常量）、變量按一定法則進(jìn)行組合，它最終會(huì)有一個(gè)值；那么這個(gè)法則是什么？很神秘！但其實(shí)也不太神秘，所有編譯原理的書中都會(huì)提到所謂的“算符優(yōu)先文法”——從直觀上講所謂算符優(yōu)先文法就是算符可以連續(xù)出現(xiàn)在表達(dá)式中，而常量或變量不能連續(xù)出現(xiàn)，否則就不是合法的“算符優(yōu)先文法”。就是這么簡單！

簡單表達(dá)式解析

   我們先來看一個(gè)簡單的例子：

   10-(2+3)

   就是小學(xué)生也知道上例是如何計(jì)算的！答案是5而不是11，為什么？只要學(xué)習(xí)過一丁點(diǎn)數(shù)學(xué)知識的人都清楚括號的優(yōu)先級是高于其他算符的；那么如果我們用計(jì)算機(jī)程序來處理應(yīng)該是怎么樣的步驟呢？

   好的，我們先模擬一個(gè)所謂叫“堆棧”的東西（有計(jì)算機(jī)常識的人都知道，堆棧的特點(diǎn)就是“先進(jìn)后出”或者“后進(jìn)先出”）；然后我們再構(gòu)造一個(gè)所謂的算符優(yōu)先表（不太嚴(yán)格），目前它只有幾個(gè)符號，包括“+”，“-”，“(”，“)”和“#”，而且我們假定“#”默認(rèn)的優(yōu)先級最低，這時(shí)我們有如下表格（縱向表示算符在左，而橫向算符在右）：

算符	+	-	(	)	#
+	>	>	<	>	>
-	>	>	<	>	>
(	<	<	<	=	>
)	>	>	-	>	>
#	<	<	<	<	=

   現(xiàn)在我們構(gòu)造這個(gè)堆棧如下：

#

   初始時(shí)，棧底只有算符“#”，為了方便起見我們在表達(dá)式10-(2+3)的尾部追加一個(gè)符號“#”，解析過程如下：

1.發(fā)現(xiàn)輸入的不是算符，而是常數(shù)10，而且棧頂是“#”，將10入棧；

2.讀入算符“-”，由于其優(yōu)先級高于“#”，進(jìn)棧；

3.讀入“(”，經(jīng)查表得知當(dāng)其在右側(cè)時(shí)，它比任何算符的優(yōu)先級都高，故還是將其壓入棧中；

4.同理，當(dāng)程序讀入2時(shí)也將其入棧；

5.讀入“+”時(shí)，發(fā)現(xiàn)其優(yōu)先級還是高于棧中的最近一個(gè)符號“(”，二話不說，進(jìn)棧；

6.讀入3，入棧；

7.當(dāng)讀到符號“)”時(shí)我們發(fā)現(xiàn)其優(yōu)先級是低于棧中最近一個(gè)算符“+”，這時(shí)計(jì)算2+3的值，將得數(shù)5再入棧，去成對的括號；

8.讀入符號“#”，發(fā)現(xiàn)其優(yōu)先級是低于棧中離它最近的一個(gè)算符“-”，計(jì)算10-5的值，將結(jié)果“5”再入棧；

9.表達(dá)式解析完畢，檢查棧中是否是僅包含兩個(gè)元素，其一是得數(shù)，其二是原先壓入棧中的算符“#”，如果是則解析正確，否則失??！

通過總結(jié)上述過程，我們就發(fā)現(xiàn)在解析表達(dá)式的時(shí)候，無非就是做如下幾個(gè)動(dòng)作：

1.如是操作數(shù)（變量或常量）則進(jìn)棧；

2.如是算符，則和棧頂（略去操作數(shù)）的算符比較優(yōu)先級；

3.高于則進(jìn)棧（編譯中的術(shù)語叫做“移進(jìn)”）；

4.低于或等于則計(jì)算（編譯中的術(shù)語叫做“規(guī)約”）。

四則運(yùn)算表達(dá)式解析

那么上述算法對于更復(fù)雜一點(diǎn)的表達(dá)式也適用么？當(dāng)然，現(xiàn)在我們構(gòu)造一個(gè)完整的四則運(yùn)算的算符優(yōu)先表，如下：

算符	+	-	*	/	(	)	#
+	>	>	<	<	<	>	>
-	>	>	<	<	<	>	>
*	>	>	>	>	<	>	>
/	>	>	>	>	<	>	>
(	<	<	<	<	<	=	>
)	>	>	>	>	-	>	>
#	<	<	<	<	<	<	=

綜合表達(dá)式解析

好了，經(jīng)過上述的分析和實(shí)踐，我們發(fā)現(xiàn)解析一個(gè)表達(dá)式也不是那么復(fù)雜或者令人望而生畏的事！那么，在實(shí)際運(yùn)用中，表達(dá)式中還可能出現(xiàn)如下情況：

1.不一定是數(shù)值常量，還可能是字符串常量（當(dāng)然它們一般無法進(jìn)行算數(shù)運(yùn)算）或變量；

2.算符不僅僅是四則運(yùn)算的算符，還有可能是關(guān)系運(yùn)算、邏輯運(yùn)算、賦值運(yùn)算等等；

3.可能不是簡單的變量，而是某個(gè)數(shù)組的元素；

4.可能不是簡單的變量或某個(gè)數(shù)組的元素，而是函數(shù)調(diào)用！

好的，對于第一和第二種情況，本節(jié)會(huì)給出解決方法，而對于后兩種情況，由于其狀況較為復(fù)雜，我們將單獨(dú)來解決它們。

我們約定字符串常量必須使用雙引號括起，如字符串常量中出現(xiàn)雙引號，請注意轉(zhuǎn)意（加“\”），否則系統(tǒng)無法識別。

表達(dá)式中的變量

其實(shí)，其后續(xù)的章節(jié)中會(huì)介紹對于變量和常量處理的不同?？梢哉J(rèn)為，與常量不同，變量在腳本或程序運(yùn)行是有“家”的，它的家就是運(yùn)行時(shí)堆棧。

由于作者無意于將此腳本解釋或解析系統(tǒng)做得像C/C++那樣的強(qiáng)類型語言，而傾向于實(shí)現(xiàn)得像Perl那樣的弱類型腳本語言即可，故系統(tǒng)內(nèi)的變量類型只有標(biāo)量和向量兩種；而且在將源代碼進(jìn)行預(yù)編譯時(shí)，系統(tǒng)會(huì)將變量的地址進(jìn)行翻譯，但前提是變量必須被定義，這在后續(xù)章節(jié)中會(huì)有描述（處理變量申明語句）。

如果變量未聲明而是用的話，系統(tǒng)會(huì)在預(yù)編譯時(shí)就給出無法繼續(xù)的提示，這和一些不用聲明就能使用的腳本語言系統(tǒng)不同，請讀者務(wù)必注意（其實(shí)聲明的目的也就是為了區(qū)分下這些變量是標(biāo)量還是向量）。

對于變量的樣式，一般約定其都是字符開頭，可以混合英文字符及數(shù)字，長度在一定范圍之內(nèi)，這個(gè)可以根據(jù)實(shí)際需要進(jìn)行約定。

值得注意的一點(diǎn)是，由于本系統(tǒng)打算支持正則匹配，故也支持類似像$1、$2等的臨時(shí)正則變量（后續(xù)正則匹配臨時(shí)變量會(huì)覆蓋前期的正則匹配臨時(shí)變量，這個(gè)同Perl是一樣的）。

復(fù)雜算符的處理

那么復(fù)雜算符是如何處理的呢？

先來看看表達(dá)式中還需要處理哪些類型的算符。在上面的章節(jié)中，我們討論了關(guān)于算術(shù)表達(dá)式（即算符只有數(shù)學(xué)上的四則運(yùn)算）的處理方法以及遇到表達(dá)式中含有變量該如何處理（只是簡單地涉及，并未深入），現(xiàn)在我們可以對各類算符進(jìn)行分類：

1.括號：包括( )和[ ]（數(shù)組的下標(biāo)運(yùn)算）；

2.算數(shù)運(yùn)算符號：加（+）、減（-）、乘（*）、除（/）、模運(yùn)算（%），對于乘方、開方等運(yùn)算，我們并不打算實(shí)用算符來解決，而是考慮使用函數(shù)，這在今后的章節(jié)中會(huì)有涉及；而且乘、除的優(yōu)先級較之加、減更高；

3.關(guān)系運(yùn)算符：包括等于（==）、不等于（!=）、大于（>）、大于等于（>=）、小于（<）、小于等于（<=）、匹配（^）、不匹配（!^）、正則匹配（~）、正則不匹配（!~）；它們之間的優(yōu)先級是相同的；

4.邏輯運(yùn)算符：或（||）、與（&&）；其中與的優(yōu)先級要高于或；

5.賦值運(yùn)算符：賦值（=）、自加賦值（+=）、自減賦值（-=）、自乘賦值（*=）、自除賦值（/=）、取模賦值（%=）；

6.其它符號：#，優(yōu)先級最低。

需要說明的一點(diǎn)是，為了簡便起見，我們并不打算實(shí)現(xiàn)位操作以及和位操作相關(guān)的賦值算符，有興趣的讀者可以翻看下C語言相關(guān)教材，可以看出位操作的優(yōu)先級還是非常高的（但是一般要低于算數(shù)運(yùn)算的算符優(yōu)先級別，按位取反例外）；另外，我們也不打算實(shí)現(xiàn)類似“++”或“—”等算符的語法及其語義，因其在一個(gè)復(fù)雜的表達(dá)式中存在一定的二義性。

最后，需要申明的是我們也暫時(shí)不打算支持取結(jié)構(gòu)，故取成員運(yùn)算符“.”（優(yōu)先級最高）也不會(huì)出現(xiàn)在下表中。

經(jīng)過整理，我們可以得到上述算符的優(yōu)先級別簡表（完整的優(yōu)先級表過大），此表基本上是按類別進(jìn)行組織和比較的：

算符	(	)	[	]	算術(shù)	關(guān)系	邏輯	賦值	#
(	<	=	<	-	<	<	<	<	>
)	-	>	>	-	>	>	>	>	>
[	<	-	<	=	<	<	<	<	>
]	-	>	-	>	>	>	>	>	>
算術(shù)	<	>	<	>	>	>	>	>	>
關(guān)系	<	>	<	>	<	>	>	>	>
邏輯	<	>	<	>	<	<	>	>	>
賦值	<	>	<	-	<	<	<	<	>
#	<	<	<	<	<	<	<	<	=

下面我們來看一個(gè)較為復(fù)雜的表達(dá)式解析結(jié)果，現(xiàn)假定表達(dá)式中出現(xiàn)的變量均已定義，且沒有函數(shù)調(diào)用：

b > c+a < a || a < 3 && a == b

可以看出，上述表達(dá)式既有算數(shù)運(yùn)算也有關(guān)系和邏輯運(yùn)算，且包含了a、b、c三個(gè)變量；由于進(jìn)行解析或解釋時(shí)，我們并不知道這些變量的值，因?yàn)樗鼈冇锌赡茴A(yù)先定義也有可能是運(yùn)行時(shí)輸入的，故在此階段我們只能把它們解析成更為簡單的表達(dá)式（可稱作中間代碼），以便于他人利用其它的工具，如C/C++、Pascal、Basic等高級語言，或者是類似Perl的腳本語言在運(yùn)行來進(jìn)一步解釋。

上述表達(dá)式的解析結(jié)果看起來是這樣的：

tmp0=c+a

tmp1=b>tmp0

tmp2=tmp1<a

tmp3=b<3

tmp4=a==b

tmp5=tmp3&&tmp4

tmp6=tmp2||tmp5

可能讀者會(huì)注意到，為什么會(huì)多出這么多以“tmp”開頭的變量？這實(shí)際上是系統(tǒng)在進(jìn)行規(guī)約時(shí)自動(dòng)生成的臨時(shí)變量；在實(shí)際系統(tǒng)中這些臨時(shí)變量可能會(huì)有特殊的標(biāo)識，以便于和其它普通變量進(jìn)行區(qū)分。

另外，我們在前面提到過，在實(shí)際解釋時(shí)系統(tǒng)會(huì)將用戶定義變量a、b、c替換為這些變量在堆棧上的相對地址，這就是為什么我們在匯編語言中經(jīng)?？吹筋愃迫缦麓a的原因：

.globl main

      .type   main, @function

main:  

.LFB1404:

      pushq   %rbp

.LCFI0:

      movq    %rsp, %rbp

.LCFI1:

      movl    $1, -8(%rbp)

      movl    $2, -4(%rbp)

      movl    -4(%rbp), %eax

      addl    %eax, -8(%rbp)

      movl    $0, %eax

       leave

       ret

（上述匯編代碼是由gcc4.1.2 在Cent OS5 ，x86 64位平臺(tái)上生成，與之對應(yīng)的C源程序如下：

void main()

{

 int a = 1,b=2;

 a = a+b;

}

簡單解釋下，rbp是堆?；羔?，而-8(%rbp)和-4(%rbp)就是分別存放了變量a和b，也就是它們在堆棧上的“家”（關(guān)于這方面內(nèi)容，大家不用過分關(guān)心，這個(gè)不是作者的或者本文的主要部分，有興趣的可以了解下，這里只是進(jìn)行下對比和說明）。

最終經(jīng)過處理的中間代碼可能看上去是這樣的：

@@tmp0=%sstack[3]+%sstack[1]

@@tmp1=%sstack[2]>@@tmp0

@@tmp2=@@tmp1<%sstack[1]

@@tmp3=%sstack[1]<3

@@tmp4=%sstack[1]==%sstack[2]

@@tmp5=@@tmp3&&@@tmp4

@@tmp6=@@tmp2||@@tmp5

其中，我們約定以“@@”開頭的是臨時(shí)變量，而%sstack[1]存儲(chǔ)的是變量a、%sstack[2]存儲(chǔ)的是變量b，而%sstack[3]存儲(chǔ)的是變量c（我們稱sstack為符號棧；當(dāng)然，一般用戶定義的變量是不太可能出現(xiàn)在符號棧sstack的底部附近，而應(yīng)該是一些環(huán)境變量或命令行參數(shù)，而且對于一般的x86系統(tǒng)地編譯程序而言，只會(huì)使用一個(gè)主要的堆棧，故臨時(shí)變量也有可能是存儲(chǔ)在其中，或者考慮到運(yùn)行效率，它們可能就是某些寄存器）。

最終表達(dá)式的解析結(jié)果被存儲(chǔ)在臨時(shí)變量@@tmp6中（約定，臨時(shí)變量是不和普通變量存儲(chǔ)在一個(gè)堆棧中）。

看到這里可能有讀者會(huì)問，怎么需要那么多臨時(shí)變量，如果在解釋過程中不夠用怎么辦？放心，對于不同的腳本作用域（scope），臨時(shí)變量名是可以重用的，在后續(xù)章節(jié)中會(huì)專門闡述這個(gè)問題，只需要使用一點(diǎn)點(diǎn)小“技巧”。

另外，其實(shí)在解釋過程或預(yù)編譯過程中就將變量的名稱用地址進(jìn)行替換，是絕大多數(shù)編譯系統(tǒng)或腳本解釋系統(tǒng)都會(huì)做的，因?yàn)檫@樣的好處就在于可以明確區(qū)分相同變量名但其作用域不同而出現(xiàn)的混亂——“最近作用域原則”；而且在運(yùn)行時(shí)，可以利用其下標(biāo)直接訪問棧上存儲(chǔ)的內(nèi)容。

當(dāng)然，上述表達(dá)式的解析也并非最優(yōu)，而且許多編譯系統(tǒng)可以對表達(dá)式進(jìn)行優(yōu)化（存在相同的子表達(dá)式），但這已經(jīng)是所謂的“高級”技術(shù)，也不是本文討論的范圍。

最后，簡單地說一下，在解析后的表達(dá)式中第一個(gè)被規(guī)約而生成的中間代碼就是所謂的“最左素短語”（c+a），這樣可以有助于大家理解編譯原理中的相關(guān)概念。

本文題目：如何解析表達(dá)式
分享鏈接：http://chinadenli.net/article16/gpdjdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、網(wǎng)站維護(hù)、云服務(wù)器、動(dòng)態(tài)網(wǎng)站、App開發(fā)、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)