手把手教你寫腳本引擎（五）——簡單的高級語言（3，符號表）

陳梓瀚

華南理工大學軟件本科05級

vczh@163.com

http://www.shnenglu.com/vczh/

符號表的結構的復雜度跟語言的語義規則的復雜度有關。對于C#來說，每一個符號都附帶了一大堆信息，譬如位置啦，所在的namespace啦，類型啦什么的。對于JavaScript來說，符號表幾乎是不需要的，因為東西都動態了，編譯時幾乎不檢查內容。語義分析的輸出是符號表，代碼生成的輸入是符號表和語法樹。因此語法樹除了放語法相關的內容，語義相關的內容最好放到符號表里面（譬如說表達式的類型啦，語句的scope結果啦）。關于一個現實中的符號表組織可以看CMinus的語義分析結果。

首先我們要解決類型的表達問題。一門復雜的語言的類型有很多種。這里的種類指的不是int和string的區別，而是函數類型、結構類型這種區別。每一種類型還有很多附帶的屬性。在語義分析的過程中，我們經常要比較兩個類型是否一致。于是符號表的類型表達要設計成易于讀取、修改和比較。

我們通常由兩種解決方法。第一種方法是用一個繼承結構來表達。定義一個基類TypeBase，然后底下一堆繼承。乍一看很OOP，實際不然。語義分析的時候我們對每一種特殊的類型都有一些特殊的操作，我們還是舉那個判斷類型是否相等的操作來說明一下。我們知道OOP里面的虛函數解決了一維的分派問題。我們拿到一個Base，對Base->Method求值，總是可以根據Base的實際類型來求值。如果我們需要對兩個類型同時進行分派呢？譬如說Equal(Base1,Base2)，這種操作當且僅當Base1和Base2的實際種類相同才有比較的意義。這個時候我們改造成Base1->Equal(Base2)的話，也是免不了對Base2進行一下dynamic_cast還是什么類似的操作的。

所以我個人比較偏向于第二種做法。我們為每一個類型創建一個唯一的ID。譬如說int 是0啦，int(int,int)是1啦，int*是2什么的。比較兩個類型是否相等就直接拿ID去比較，ID相等則類型相等，ID不相等則類型不相等。在實際操作上怎么做呢？我們知道語義分析的過程中會產生出一堆（理論上可以為無窮多的）新類型。每一種類型都有一些屬性。譬如說基本類型是有限的，可以用enum來表達。而函數類型需要返回值和參數類型表。于是我們拿屬性去要一個ID的時候，符號表首先檢查這個類型是否已經存在，存在則返回對應的ID，不存在則創建一條新的記錄，然后綁定一個新的ID。譬如CMinus的類型表采用如下接口分配ID：

class VL_CMinusTypeTable : public VL_Base

{

public:

VInt GetPrimitiveType(VLE_CMinusPrimitiveType Type);

VInt GetPointer(VInt Type);

VInt GetArray(VInt Type , VInt Count);

VInt GetFunction(VInt ReturnType , VL_List<VInt , true>& ParameterTypes);

VInt CreateStruct();

VL_CMinusTypeSlot* GetType(VInt Type);

};

如果我們已知一個類型的ID，求其指針類型的ID，就調用GetPointer(TypeID)。經過這一套函數的處理，我們總是可以不用擔心是否在什么地方讓兩個ID指向了相同的類型，或者一個類型不小心擁有了多個ID，十分好管理。

第二個問題就是要保存每一個表達式的類型和語句的Scope了。我不建議將這些信息保存在語法樹里面。原因比較復雜，因為一份代碼在不同的上下文中可能有不同的意思，然后我們有一天突然有需要將這些環境中的這份代碼的語義分析結果保留下來的話，如果東西原本是存在語法樹里面的，那就完蛋了，只能去復制語法樹了。于是我建議將語法分析得不到的信息通通存進符號表。因為表達式和語句都是指針，我們只需要一些map就可以將表達式和語句的附加信息存起來了。

第三個問題是scope。一個變量或參數的作用范圍是有限的，于是我們只好創建一個scope樹，其中每一個節點都看得到父節點，至于能不能看到子節點我覺得是無所謂的。于是對于一個具體的scope來說，一個scope就變成了一個鏈表，保存了當前scope的所有符號名，然后還能知道直接或間接的父scope。下面舉個直觀的例子。假設我們有代碼：

int A=0;

int B(int C,int D)

{

  int E=0;

}

為了處理這份代碼，我們建立了三個scope。第一個是全局scope，記錄了A和B。第二個是函數scope，記錄了C和D。第三個是屬于語句的一個scope，記錄了E。于是我們用一個鏈表把他們串起來：語句scope -> 函數scope -> 全局scope。

這樣做的好處是我們查找scope會變得很方便。譬如現在的上下文是語句scope，那么它理應可以看見變量、參數、全局函數和全局變量。添加一個符號也很方便，只要當前的scope沒有這個名字，不管上面的scope有沒有我們都可以添加，添加完就把上面的scope的同名符號給覆蓋了。

一個scope其實還可以記錄其他的東西的，譬如距離最近的循環表達式啦（用來判斷break是否應該存在），所屬的函數啦（return后面要不要接表達式），還有其他的很多雜七雜八的東西。

第四個問題是如何創建符號表。之前的文章我們把語句和表達式都建立成了兩個大型的繼承結構。表達式添加一個函數叫GetType，返回一個ID。語句建立一個函數叫Validate，用來驗證語句是否合法。他們的參數都是符號表和當前的scope，這樣的話，表達式為了創建類型就會產生出一堆ID，語句為了讓表達式可以知道每一個變量的類型就要創建scope。這么一遞歸下去，符號表也有了，類型也檢查完了。所以上文才會說語義分析產生符號表。

符號表就介紹到這里了。一個高級語言所遇到的基本的問題其實都講得差不多了。接下來的文章就針對具體的問題進行講解了，譬如繼承、反射、垃圾收集等等的跟具體語言相關的問題。