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

陳梓瀚

華南理工大學(xué)軟件本科05級

vczh@163.com

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

符號表的結(jié)構(gòu)的復(fù)雜度跟語言的語義規(guī)則的復(fù)雜度有關(guān)。對于C#來說，每一個符號都附帶了一大堆信息，譬如位置啦，所在的namespace啦，類型啦什么的。對于JavaScript來說，符號表幾乎是不需要的，因?yàn)闁|西都動態(tài)了，編譯時幾乎不檢查內(nèi)容。語義分析的輸出是符號表，代碼生成的輸入是符號表和語法樹。因此語法樹除了放語法相關(guān)的內(nèi)容，語義相關(guān)的內(nèi)容最好放到符號表里面（譬如說表達(dá)式的類型啦，語句的scope結(jié)果啦）。關(guān)于一個現(xiàn)實(shí)中的符號表組織可以看CMinus的語義分析結(jié)果。

首先我們要解決類型的表達(dá)問題。一門復(fù)雜的語言的類型有很多種。這里的種類指的不是int和string的區(qū)別，而是函數(shù)類型、結(jié)構(gòu)類型這種區(qū)別。每一種類型還有很多附帶的屬性。在語義分析的過程中，我們經(jīng)常要比較兩個類型是否一致。于是符號表的類型表達(dá)要設(shè)計(jì)成易于讀取、修改和比較。

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

所以我個人比較偏向于第二種做法。我們?yōu)槊恳粋€類型創(chuàng)建一個唯一的ID。譬如說int 是0啦，int(int,int)是1啦，int*是2什么的。比較兩個類型是否相等就直接拿ID去比較，ID相等則類型相等，ID不相等則類型不相等。在實(shí)際操作上怎么做呢？我們知道語義分析的過程中會產(chǎn)生出一堆（理論上可以為無窮多的）新類型。每一種類型都有一些屬性。譬如說基本類型是有限的，可以用enum來表達(dá)。而函數(shù)類型需要返回值和參數(shù)類型表。于是我們拿屬性去要一個ID的時候，符號表首先檢查這個類型是否已經(jīng)存在，存在則返回對應(yīng)的ID，不存在則創(chuàng)建一條新的記錄，然后綁定一個新的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，就調(diào)用GetPointer(TypeID)。經(jīng)過這一套函數(shù)的處理，我們總是可以不用擔(dān)心是否在什么地方讓兩個ID指向了相同的類型，或者一個類型不小心擁有了多個ID，十分好管理。

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

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

int A=0;

int B(int C,int D)

{

  int E=0;

}

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

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

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

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

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