手把手教你寫腳本引擎（四）——簡單的高級語言（2，處理語法）
陳梓瀚
華南理工大學軟件本科05級
vczh@163.com
http://m.shnenglu.com/vczh/
有了全盤的計劃之后，我們必須先處理輸入的腳本，才能夠進行下一步的工作。字符串處理方面可以參照一下三篇文章：《構造可配置語法分析器》、《構造正則表達式引擎》以及《如何手寫語法分析器》。作為補充，這里再說一說其他的辦法。
首先是詞法分析器。我們仍然能夠使用《構造可配置語法分析器》前半部分的方法人腦畫出一張合適的DFA，這個時候我們可以手工來實現。用于詞法分析器的DFA只有兩種狀態，一種是普通狀態，另一種是終結狀態。所以我們可以很機械地將DFA用C++寫出來。
我們要為狀態編號。編號要連續，而且要從0開始，這樣的話C++的編譯器一般都會為switch-case的代碼生成一張表，用于快速跳轉。然后用下面的方法。
1：將輸入的指針Input復制出一個副本，叫Current；給出一個同類型的指針Last，將其賦值為NULL；使用一個變量Status來記錄當前的狀態。初始化狀態，一般為了方便我們把初始狀態編號成0。
2：做一個死循環不斷的計算新Status。對于某個Status我們總是能夠知道輸入什么字符跳轉到什么新的Status上去。不同的人寫出來的DFA可能會有所區別。我們首先判斷當前的Status是不是終結狀態，如果是的話將Current賦值給Last，然后繼續往下走。我們從Current指針拿出一個字符，然后計算新Status。如果Current不滿足要求那么結束循環，如果Current滿足要求那么改變Status并讓Current指向新的位置。
3：因為字符串總是有限的，所以這個循環總是會結束。結束了之后，我們檢查Last。如果Last仍然是NULL，那么代表輸入的字符串是有問題的。如果不是，那么我們所需要的一個記號就從Input開始到Last結束了。如果記號的類型有需要保留的話，那么我們只需要添加一個新的代表類型的變量，在每一次修改Last的時候修改這個保存類型的變量就行了。因為一個終結狀態只能代表一種類型的結束（反過來不成立，一種類型可能有好幾個終結狀態）。
然后是語法分析。一般來說，使用《如何手寫語法分析器》中描述的方法實現一個語法分析器的話是很容易的，但是一個主要問題就是如果一門語言很復雜，特別是操作符特別多的話，這些函數寫起來會很亂，因此每一個文法產生式的處理函數的命名和注釋就變得相當重要了。為了簡化這件事情，我們還有另一種專門用來處理操作符的方法，而且是高度可配置的。為了簡化，我僅給出二元操作符和前綴操作符的處理方法。后綴操作符不常見，需要的話自己想辦法吧，在上一篇文章中的語法定義中并沒有出現后綴操作符。
在這種方法中，我們把重點放在不包含修改優先級的括號的表達式中。遇到一個用于修改優先級的括號的時候，只要遞歸一下就好了。現在，我們通過詞法分析，已經得到了很多記號，然后就使用以下的方法來生成一顆正確的語法樹：
1：我們需要定義兩個指針，第一個用于保存根節點，第二個用于保存當前節點。在分析的過程中，根節點會經常變化，當前節點也是。
2：取出一個單元。一個單元指的是一個用括號包括起來的完整的表達式、一個函數調用、一個常量或變量和僅由前綴操作符與單元組成的整體。舉個例子，1是單元，a是單元，function(param1,param2+param3)是單元，(a*b+c*d)是單元，-(a+b)也是單元。但是-a+b就不是單元了。單元內部可能有表達式，我們可以遞歸下去。取出單元以后，就把根節點和當前節點指向這個單元。
3：一個正確的表達式總是由單元和二元操作組成的，如果在以下的步驟中出錯的話，那么可以直接確定輸入的表達式的語法不正確。我們做一個死循環一直到遇到右括號、逗號等這些結束表達式的記號為止，對于每一個輸入執行第4步。
4：取出一個二元操作符和一個單元。然后從當前節點往父節點找，一直到根節點或者父節點優先級比當前的二元操作符小的二元操作符為止。如果找到根節點，那么整個根節點將作為二元操作符的左操作數，單元作為右操作數，根節點更新，當前節點指向單元。如果不是的話，將找到的節點（這個節點的父節點的優先級比自己小）從父節點脫離，整個節點作為操作符的左操作數，單元作為右操作數，然后用這個二元操作符接上父節點。
5：當3與4進行不下去的時候，我們就得到了一棵完整的表達式語法樹了。當然，如果中間出錯的話，我們應當輸出錯誤信息。這個時候要不要繼續往下走就自己看著辦吧，因為進行錯誤恢復的話，接下去的錯誤信息會很難看，就像VC++一樣。
我給一個例子來說明如何處理這些事情。現在我們要分析1+2*3+4。這個算法將會產生一個正確的語法樹”1”，然后修改為正確的語法樹”1+2”，然后修改為正確的語法樹”1+2*3”，最后產生完整的正確的語法樹。
第一步，產生一個單元的正確的語法樹：
第二步，獲得一個二元操作符，并產生一個單元的語法樹”2”。因為當前節點往上就沒有了，所以執行4中的第一種情況：
第三步，獲得操作符”*”和一個單元的語法樹”3”。因為2的父節點的優先級比”*”小，因此執行4的第二種情況：
第四步，獲得操作符”+”和一個單元的語法樹”4”。這個時候3的父節點的優先級大于或等于”+”的優先級，因此一直往上找，一直到根節點。因為根節點的優先級仍然大于或等于”+”的優先級，因此再也上不了了，執行4的第一種情況：
字符串結束了，中間也沒有出錯，代表輸入的表達式”1+2*3+4”是正確的，我們也得到了一棵正確的語法樹。
通過之前的文章與上述兩種簡單的方法的學習，我想分析一門語言的語法也就沒什么困難的了。不過分析字符串是次要的，得到語法樹才是主要的。就算用了一種猥瑣的處理字符串的辦法得到了語法樹，那也沒關系，以后有時間再改就行了。現在我們要討論一下語法樹的數據結構問題。
在這里我們需要大膽地使用虛函數。使用單一的一個class來表達整棵語法樹是不好的，因為我們的語法樹要表達unit、表達類型聲明、函數聲明、還有各種復雜的語句。類型是遞歸的，語句是遞歸的，表達式也是遞歸的。對于一組遞歸的結構，我們要定義一個幾類，并派生出各種子類來表達各種類型的結構。這樣做的好處是我們可以很方便地處理類型檢查、其它語義分析以及生成指令。多態在這里是相當好用的，比省掉一點虛函數的空間（若干個同類型的對象只共享一張虛函數表）和一點調用的時候犧牲的速度好多了。我想用復雜的if或函數指針來代替多態估計也沒有多態快。
因為類型、表達式和語句的處理方式是類似的，因此我只為表達式建模。我們的表達式有四則運算、數組訪問以及函數調用。首先我們給出一個基類ExpBase：
class ExpBase
{
public:
TypeBase* GetType(vector<ErrorMessage>& Errors);
};
我們拿到了一個表達式之后，轉換成表達式樹，就會得到一個ExpBase了，這個時候我們進行類型檢查，只需要調用GetType就行了。各種不同的檢查由子類實現。
然后我們為運算符定義表達式節點：
enum BinOpType
{
Plus,
Minus,
Multiply,
Division,
……
};
enum SinOpType
{
Negative,
Not,
……
};
class ExpBinOp : public ExpBase
{
public:
ExpBase* ParamA;
ExpBase* ParamB;
BinOpType Operator;
};
class ExpSinOp : public ExpBase
{
public:
ExpBase* Param;
SinOpType Operator;
};
數組訪問可以加進二元操作符也可以不加，不過我個人還是傾向于不加的，因為后續的處理邏輯有很大的不同。
接下來是函數調用的表達式節點：
class ExpInvoke : public ExpBase
{
public:
ExpBase* Name;
vector<ExpBase*> Params;
};
所有的符合表達式就構造完了，但是我們仍然需要一個代表單一記號的表達式，譬如變量名啊數字等等。我們直接把一個記號放進去就好了，因為記號里面有常量的類型信、也有變量名：
class ExpToken : public ExpBase
{
public:
Token* Content;
};
表達式的數據結構就構造完了，然后我們把剩下的類型信息與語句構造萬，給出單元結構以后就結束了。
鑒于實習期間較忙，自己的時間不多，完整的代碼我就不給出來了。要是大家愿意的話可以去這里看Vczh Free Script 2.0 beta的語法樹結構。雖然少了類型族，但也還是能看得。
下一篇文章講述語義分析以及符號表的事情。語法樹不僅要代表源代碼，還需要附帶額外的信息，譬如表達式的類型、重載的選擇等等。這些在語法分析的時候很難一起產生，所以我們借助多態來簡化這個任務。
posted on 2008-08-01 23:19
陳梓瀚(vczh) 閱讀(5213)
評論(4) 編輯 收藏 引用 所屬分類:
腳本技術