如何解析表達式之二
責編：admin ｜2015-02-08 16:11:33關于賦值算符在表達式中的使用
其實，大家一般不會在一個表達式中使用多個賦值算符，除非不太正常，但其實很多語言的編譯或解釋系統都允許這樣做，關鍵是如何使用。賦值算符和其它算符明顯不同的一點還在于：其它算符均是自左至右進行解析，而賦值算符則恰恰相反！
我們來看如下一個簡單的例子，請你給出判斷：這個表達式到底是合法的還是非法的：
a=3+a*2+b=5
看到上面這個表達式，我們的第一反應就是書寫這個表達式的人可能腦子有問題，怎么能這些用呢？事實上這個表達式也是錯誤的（大家可以試試，一般系統都會報告類似“無法給常量賦值”等的錯誤），如果我們改一下：
a=3+a*2+(b=5)
這樣，這個表達式就是合法的了！為什么？
因為按算符的優先程度，上式中a*2最先被規約，然后是3+a*2，最后是先對變量b進行賦值，最后規約的效果實際上就相當于：
a=3+a*2+5
臨時變量的約簡
在上一章的最后部分，提到了一個比較復雜的表達式的解析，即：
b > c+a < a || a < 3 && a == b
最終，經過處理的中間代碼如下所示：
@@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
在上一章也提到，這樣生成的中間代碼并不是十分優雅、簡約，雖然我們不需要研究到底如何對代碼進行優化，甚至直接使用寄存器來替代臨時變量（那是真正編譯器干的事，不是腳本翻譯研究的對象，時刻記住我們只研究腳本的解析或解釋，至于如何使用累加寄存器、邊界對齊、機器代碼的翻譯、運行時內存優化等“高深”課題至少現在不是我們所關心的），但還是有十分簡單又比較有效的方法來減少臨時變量的數量：如果被規約的表達式中包含了臨時變量，那么就使用序號最大的臨時變量作為規約的目標。
經過一點點優化，上述的中間代碼就被變換為如下形式：
@@tmp0=%sstack[3]+%sstack[1]
@@tmp0=%sstack[2]>@@tmp0
@@tmp0=@@tmp0<%sstack[1]
@@tmp1=%sstack[1]<3
@@tmp2=%sstack[1]==%sstack[2]
@@tmp2=@@tmp1&&@@tmp2
@@tmp2=@@tmp0||@@tmp2
通過上面的例子可以看出，我們僅用了三個臨時變量（@@tmp0-@@tmp2）就替代了原來需要七個臨時變量（@@tmp0-@@tmp6）的方案，而且效果相同。
好了，其實本章的主要目的并不是對表達式解析的優化進行深入地探討，而是主要解決如下兩個問題：
1.表達式中包含了數組元素的操作；
2.表達式中包含了函數的調用。
如需要解決上述兩個問題，我們就要使用計算機界最為恐怖和逆天的方法，也是計算機科學中無處不在的核心內容之一——遞歸（Recursive）。
關于遞歸，當然有許多非常高級的議題來討論或研究它，比如令人無法捉摸的而又十分高深的理論課程——《遞歸論》，或者在《數據結構》中無所不在的基于遞歸的數據結果或遞歸算法（如二叉樹的遍歷、B樹的刪除等等），抑或是在《編譯原理》中的什么左右遞歸文法！
好了，本文的目的不是來探討這些理論問題的，我們還是看看如何使用遞歸來解決表達式解析的。
為什么需要在表達式的解析中專門提到數組的處理？在上一章中提到關于算符優先級時，關于符號“[]”就是實際上和數組相關的。
幾乎所有語言的，無論是一般高級語言還是一些通用的腳本語言都會將“[]”作為數組下標來使用。“[]”中不僅可以使用整數常量來存取數組中的元素，而且其中可以使用表達式，表達式即可以是常量表達式也可以是帶變量的表達式甚至其中再嵌套其它數組的調用或者函數調用，對于這種復雜的情況我們只有也只能求助于遞歸。
需要說明的一點是，我們實現的解釋系統中，支持一維數組，而不支持多維數組，其原因很簡單——一維數組已經夠用了！其實，在C語言中實際上也是如此，Perl也是類似的，即使你想定義一個多維數組也不可得。
言歸正傳，下面看一個含有數組的簡單表達式的解析情況：
array[0]+a+b
它生成的中間代碼如下：
@@tmp0=%sstack[9][0]+%sstack[1]
@@tmp0=@@tmp0+%sstack[2]
可以看出，這里數組array中的第一個元素是從下標0開始的，這也是我們的以及大多數語言約定的，而且這個數組變量是其所在函數符號棧的第十個元素（我們約定棧中即可以保存普通的標量，也能夠保存向量）。這個例子比較簡單，因數組下標是常量，完全沒有使用到遞歸，故其生成的中間代碼和普通表達式幾乎沒有區別，唯有小小的不同點就在于符號%sstack[9][0]表明了這是一個數組，可以理解%sstack[9]存放的不是一般變量的值，而僅僅是數組變量array的首地址而已（第一個元素的地址），其元素的值是存放在其它地方的，這里還不能說明（佛曰：說不得！），得以后在解釋腳本是如何運行時再講。
以下，再給出一個稍微復雜點的例子：
array[12+a+b]+a+b
在這個例子中，我們可以看到其數組下標中含有一個子表達式“12+a+b”，我們知道其實“[]”中所包含的表達式應該是優先被規約的，因為其優先級高，所以如遇到此類數組下標應遞歸調用表達式解析例程，這樣上述表達式的解析結果大致如下所示：
@@tmp0=12+%sstack[1]
@@tmp0=@@tmp0+%sstack[2]
@@tmp1=%sstack[9][@@tmp0]+%sstack[1]
@@tmp1=@@tmp1+%sstack[2]
通過上面生成的中間代碼可以看出，系統首先是對表達式“12+a+b”進行了規約，并將結果保存在臨時變量@@tmp0中，至于后續的解析就不用過多分析了，讀者一看就知道大概了。
表達式中的函數調用
其實，表達式中包含了函數調用是非常正常的用法，我們在處理這種情況時和處理數組中的表達式其實比較類似，但存在如下幾點不同：
1.函數調用的合法性檢查與數組處理存在一定差異；
2.在處理函數調用時，需要注意處理堆棧中的輸入參數、返回值以及返回地址；
3.在處理函數調用時，需注意處理到底是傳值還是傳引用。
下面我們就上述三個需要注意的方面分別介紹。
函數調用的合法性檢查
在系統遇到函數調用時，需要進行合法性檢查，其主要檢查的方面無非是：
1.函數是否定義？
2.函數參數的類型是否匹配？
對于第一個方面，函數是否定義的問題，我們可以這樣的順序查找一個函數是否定義：
1.該函數是否是系統內置函數？
2.該函數是否是本腳本或程序文件定義函數？
3.該函數是否在其它庫文件中被定義？（腳本中需要使用相關的語句進行引用，例如“use xxx”）
如果根據上述查找順序仍不能查到，則報錯，否則將查到的函數地址（這個地址實際上是中間代碼的行號，后面在闡述多文件解析時會給出如何翻譯）。
對于參數類型的檢查，幸好我們所做的不是強類型語言，故在這方面我們只要把握好參數是標量還是向量即可，其它的可以推遲到運行階段（例如如果某個函數的參數要求必須是數值，但你卻傳遞的是字符串，那么在解釋或編譯時倒是不一定非要進行檢查，待到運行時給出異常或者像Perl一樣給出“undef”也可）。
函數調用與堆棧使用
一般而言，系統都是利用堆棧來傳遞輸入參數、返回值并且保存返回地址的，但也不排除在一定情況下，直接使用寄存器來保存上述這些內容，但在我們的實現中，只考慮模擬堆棧來解決函數的調用和返回。
在很多高級語言中，在將參數壓入堆棧時，只有兩種做法（也只能有兩種），一種是將參數自左至右壓入堆棧，而另外一種則正相反，即將參數自右至左壓入堆棧；在高級語言中，Pascal是采用前者，而采用后者的則更多，利于C/C++（當然也可以使用第一種參數入棧方式，但需要特殊聲明）。
需要說明的一點是，我們打算單獨使用堆棧來處理函數的調用，這和一般的高級語言的處理方式還是存在一定的出入。
傳值還是引用
我們知道，在Java的函數調用中，一般都是傳遞的對于變量的引用，這樣做的好處就是可以獲得多個返回值，而且可以節省堆棧空間。
所以，在本文所提到的函數調用中，一般參數也都是引用方式（當然，如果參數只是變量就可以使用引用，但如果它是普通表達式或者常量就沒法使用引用了）。
那么，下面就給出例子來說明如何來處理是傳值還是傳遞引用。
函數調用解析
好了，經過上面的一串說明，我們終于可以處理函數調用了，下面給出一個例子來說明函數調用在表達式中的處理以及如何翻譯成中間代碼：
a +(22+array[12+a+b])+25.2+fun(f(a+b)，sin(a)，b，c，log(d))+(x+(y+z))
上面是一個較為復雜的表達式，它既含有普通的算符，又包含了數組和函數調用，而且數組下標中也是表達式，而函數調用的參數中既包括普通的變量，也包括了表達式以及嵌套的函數調用。
我們假定fun、f是用戶自定義函數，而sin、log是系統內置函數，a、b、c、d、x、y和z都是用戶定義的變量，25.2是個浮點類型的常數，最終得到的中間代碼可能是這樣的：
@@tmp0=12+%sstack[1]
@@tmp0=@@tmp0+%sstack[2]
@@tmp1=22+%sstack[9][@@tmp0]
@@tmp1=%sstack[1]+@@tmp1
@@tmp1=@@tmp1+25.2
@@tmp2=%sstack[1]+%sstack[2]
call，f，@@tmp3，@@tmp2
call，sin，@@tmp4，%sstack[1]
call，log，@@tmp5，%sstack[4]
call，fun，@@tmp6，@@tmp3，@@tmp4，%sstack[2]，%sstack[3]，@@tmp5
@@tmp6=@@tmp1+@@tmp6
@@tmp7=%sstack[6]+%sstack[7]
@@tmp7=%sstack[5]+@@tmp7
@@tmp7=@@tmp6+@@tmp7
在上述生成的中間代碼中，我們可以但到，如果數組下標或者函數參數中包含了表達式，則首先回遞歸調用表達式解析過程進行處理；我們將函數調用翻譯成如下的中間代碼形式：
call，function name，returnedvalue，argument0，…，argumentn
當然，我們可以將function name替換成所需要的函數地址，如下：
call，function address，returnedvalue，argument0，…，argumentn
其中，如果函數是系統內置、其它庫函數或者用戶自定義函數，則其地址可以增加一個前綴來表示，例如“###System：：”；使用“###”就是告訴腳本解析器這個函數需要從其它庫中來尋找，而不是本腳本文件定義的函數；另外，與其它腳本語言或者高級語言類似，用戶也需要注意庫的搜索路徑，這個問題會在腳本的運行階段來解釋。
如果不過考慮的中間代碼的兼容性，其實只使用名字來查找也是不錯的，至少這樣看來更加直觀（這個理念更加接近于動態庫的概念，即無論庫的版本如何修改，只要這個函數仍然存在我就可以使用），只不過這樣做的話會略微降低一點腳本在運行時的效率（需要根據庫文件的函數名與函數地址表進行查找）。
另外，需要說明的是通過觀察生成的中間代碼，我們也可以輕易地區分出，哪些參數需要傳值，哪些需要傳遞引用，如上述中間代碼中的一行：
最后，如果函數的參數是可變的（類似C語言中的printf函數），那么我們也需要小心處理這種樣式。
表達式解析的完整算法
以下是表達式解析完整算法的偽代碼；其中AnalysisStack就是在表達式分析時所使用的堆棧，expression是待分析的表達式串，GetNextToken是從輸入串中獲取算符或者操作數（變量、常量或者是函數調用）：
Initializethe AnalysisStack；
Push ‘#’into the AnalysisStack；
Add ‘#’to the end of expression；
While(NotEof(expression) )
{
Token = GetNextToken()；
If ( Token is a common operand )
{
Checkvalidation of operand(if it is a valid constant or defined variable)；
Push Token into the AnalysisStack；
}
Else
If ( Token isa function call )
{
Check thevalidation of function call；
Resolve thearguments；
Result = Recursivecalling the expression parser according to each argument；
Push Result into the AnalysisStack；
}
Else
If ( Tokencontains array )
{
Check validation of array；
Result = Recursivecalling the expression parser according to its index；
PushResult into the AnalysisStack；
}
Else
{
#The tokenis an operator
PreOperator= Get the operator at the top of the AnalysisStack；
If ( GetPriority(Token)<= GetPriority(PreOperator) )
{
Right =Pop from the AnalysisStack；
PreOperator = Pop from the AnalysisStack；
Left = Popfrom the AnalysisStack；
Generatethe intermediate code， like tmpvar = Left PreOperator Right；
Push tmpvar into the AnalysisStack；
}
Push Tokeninto the AnalysisStack；
}
}
If (SizeOf(AnalysisStack) ！= 2 )
{
Error；
}
Else
{
Return (Pop from the AnalysisStack)；
}
關于上述算法，有幾點值得注意：
1.關于字符串的處理：需要將字符串作為整體的Token來處理；由于字符串中可能包含任何字符，故需小心處理，包括對于字符串中也包含雙引號（本文約定雙引號是字符常量的界符）的情況；
2.關于注釋的處理：本節暫不做討論，在后續章節中討論復合語句解析時再進行；但值得注意的一點是注釋可以出現在任何的算符之間或者算符和操作數之間，而不能橫亙在操作數內，否則會認為注釋是常量或變量的一部分，從而導致錯誤；
3.關于回車換行的處理：回車換行不會作為腳本解析的分隔符號；其它與注釋類似，即回車換行可以出現在任何的算符之間或者算符和操作數之間；
4.關于臨時變量的生成和存儲：本節暫不作討論（既可以存放在符號棧上也可以單獨存儲），待后續章節再繼續闡述這個話題。
小結
通過上述章節的講解和示例，我們基本上掌握了如何解析或解釋一個較為復雜的表達式，其實其核心也無非如下兩點：第一需要搞清楚各種算符的優先級別，當然也可以自己發明算符；第二善于使用遞歸的方法將復雜的問題簡單化、重復化。
關于遞歸，在后續的章節還需要經常出場，包括對于復合語句的解析等等，故希望能熟練掌握并多加練習（當然不要搞得老是堆棧溢出），大家可以盡量考慮用遞歸來改寫一些循環語句做的工作。
另外，值得注意的一點是在有些語言中，可以在表達式中直接聲明變量，但我們并不打算這樣做。
最后，對于逗號運算符（在一般高級語言或腳本語言中，與它的優先級實際上是低于賦值運算符的），我們也并不打算支持，但讀者應該知道在這種情況下，逗號運算符是可以將多個子表達式分隔開，整個表達式的值就是最后一個表達式的值，如下：
假定：b=2，c=7，d=5，
a1=(++b，c–，d+3)；
a2=++b，c–，d+3；
那么，a1等于8，而a2卻等于3。