如何解析表達式

概述

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

   那么簡單而來說，如果我們想利用一點掌握的編譯技術，自主開發一個腳本的解析或解釋引擎，應從哪里下手？或則說腳本解釋技術的“實相”是什么？

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

   什么事表達式？我也曾經千百次地問自己，表達式的準確定義是什么？百度上給出的答案是：

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

個人認為上述的定義算是能基本上表達出了其含義。

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

簡單表達式解析

   我們先來看一個簡單的例子：

   10-(2+3)

   就是小學生也知道上例是如何計算的！答案是5而不是11，為什么？只要學習過一丁點數學知識的人都清楚括號的優先級是高于其他算符的；那么如果我們用計算機程序來處理應該是怎么樣的步驟呢？

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

   現在我們構造這個堆棧如下：

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

1.發現輸入的不是算符，而是常數10，而且棧頂是“#”，將10入棧；

2.讀入算符“-”，由于其優先級高于“#”，進棧；

3.讀入“(”，經查表得知當其在右側時，它比任何算符的優先級都高，故還是將其壓入棧中；

4.同理，當程序讀入2時也將其入棧；

5.讀入“+”時，發現其優先級還是高于棧中的最近一個符號“(”，二話不說，進棧；

6.讀入3，入棧；

7.當讀到符號“)”時我們發現其優先級是低于棧中最近一個算符“+”，這時計算2+3的值，將得數5再入棧，去成對的括號；

8.讀入符號“#”，發現其優先級是低于棧中離它最近的一個算符“-”，計算10-5的值，將結果“5”再入棧；

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

通過總結上述過程，我們就發現在解析表達式的時候，無非就是做如下幾個動作：

1.如是操作數（變量或常量）則進棧；

2.如是算符，則和棧頂（略去操作數）的算符比較優先級；

3.高于則進棧（編譯中的術語叫做“移進”）；

4.低于或等于則計算（編譯中的術語叫做“規約”）。

四則運算表達式解析

那么上述算法對于更復雜一點的表達式也適用么？當然，現在我們構造一個完整的四則運算的算符優先表，如下：

綜合表達式解析

好了，經過上述的分析和實踐，我們發現解析一個表達式也不是那么復雜或者令人望而生畏的事！那么，在實際運用中，表達式中還可能出現如下情況：

1.不一定是數值常量，還可能是字符串常量（當然它們一般無法進行算數運算）或變量；

2.算符不僅僅是四則運算的算符，還有可能是關系運算、邏輯運算、賦值運算等等；

3.可能不是簡單的變量，而是某個數組的元素；

4.可能不是簡單的變量或某個數組的元素，而是函數調用！

好的，對于第一和第二種情況，本節會給出解決方法，而對于后兩種情況，由于其狀況較為復雜，我們將單獨來解決它們。

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

表達式中的變量

其實，其后續的章節中會介紹對于變量和常量處理的不同。可以認為，與常量不同，變量在腳本或程序運行是有“家”的，它的家就是運行時堆棧。

由于作者無意于將此腳本解釋或解析系統做得像C/C++那樣的強類型語言，而傾向于實現得像Perl那樣的弱類型腳本語言即可，故系統內的變量類型只有標量和向量兩種；而且在將源代碼進行預編譯時，系統會將變量的地址進行翻譯，但前提是變量必須被定義，這在后續章節中會有描述（處理變量申明語句）。

如果變量未聲明而是用的話，系統會在預編譯時就給出無法繼續的提示，這和一些不用聲明就能使用的腳本語言系統不同，請讀者務必注意（其實聲明的目的也就是為了區分下這些變量是標量還是向量）。

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

值得注意的一點是，由于本系統打算支持正則匹配，故也支持類似像$1、$2等的臨時正則變量（后續正則匹配臨時變量會覆蓋前期的正則匹配臨時變量，這個同Perl是一樣的）。

復雜算符的處理

那么復雜算符是如何處理的呢？

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

1.括號：包括( )和[ ]（數組的下標運算）；

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

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

4.邏輯運算符：或（||）、與（&&）；其中與的優先級要高于或；

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

6.其它符號：#，優先級最低。

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

最后，需要申明的是我們也暫時不打算支持取結構，故取成員運算符“.”（優先級最高）也不會出現在下表中。

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

下面我們來看一個較為復雜的表達式解析結果，現假定表達式中出現的變量均已定義，且沒有函數調用：

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

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

上述表達式的解析結果看起來是這樣的：

tmp0=c+a

tmp1=b>tmp0

tmp2=tmp1<a

tmp3=b<3

tmp4=a==b

tmp5=tmp3&&tmp4

tmp6=tmp2||tmp5

可能讀者會注意到，為什么會多出這么多以“tmp”開頭的變量？這實際上是系統在進行規約時自動生成的臨時變量；在實際系統中這些臨時變量可能會有特殊的標識，以便于和其它普通變量進行區分。

另外，我們在前面提到過，在實際解釋時系統會將用戶定義變量a、b、c替換為這些變量在堆棧上的相對地址，這就是為什么我們在匯編語言中經常看到類似如下代碼的原因：

.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位平臺上生成，與之對應的C源程序如下：

void main()

{

 int a = 1,b=2;

 a = a+b;

}

簡單解釋下，rbp是堆棧基指針，而-8(%rbp)和-4(%rbp)就是分別存放了變量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

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

最終表達式的解析結果被存儲在臨時變量@@tmp6中（約定，臨時變量是不和普通變量存儲在一個堆棧中）。

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

另外，其實在解釋過程或預編譯過程中就將變量的名稱用地址進行替換，是絕大多數編譯系統或腳本解釋系統都會做的，因為這樣的好處就在于可以明確區分相同變量名但其作用域不同而出現的混亂——“最近作用域原則”；而且在運行時，可以利用其下標直接訪問棧上存儲的內容。

當然，上述表達式的解析也并非最優，而且許多編譯系統可以對表達式進行優化（存在相同的子表達式），但這已經是所謂的“高級”技術，也不是本文討論的范圍。

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