手把手教你寫(xiě)腳本引擎（五）——簡(jiǎn)單的高級(jí)語(yǔ)言（3，符號(hào)表）

陳梓瀚

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

vczh@163.com

http://m.shnenglu.com/vczh/

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

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

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

所以我個(gè)人比較偏向于第二種做法。我們?yōu)槊恳粋€(gè)類(lèi)型創(chuàng)建一個(gè)唯一的ID。譬如說(shuō)int 是0啦，int(int,int)是1啦，int*是2什么的。比較兩個(gè)類(lèi)型是否相等就直接拿ID去比較，ID相等則類(lèi)型相等，ID不相等則類(lèi)型不相等。在實(shí)際操作上怎么做呢？我們知道語(yǔ)義分析的過(guò)程中會(huì)產(chǎn)生出一堆（理論上可以為無(wú)窮多的）新類(lèi)型。每一種類(lèi)型都有一些屬性。譬如說(shuō)基本類(lèi)型是有限的，可以用enum來(lái)表達(dá)。而函數(shù)類(lèi)型需要返回值和參數(shù)類(lèi)型表。于是我們拿屬性去要一個(gè)ID的時(shí)候，符號(hào)表首先檢查這個(gè)類(lèi)型是否已經(jīng)存在，存在則返回對(duì)應(yīng)的ID，不存在則創(chuàng)建一條新的記錄，然后綁定一個(gè)新的ID。譬如CMinus的類(lèi)型表采用如下接口分配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);

};

如果我們已知一個(gè)類(lèi)型的ID，求其指針類(lèi)型的ID，就調(diào)用GetPointer(TypeID)。經(jīng)過(guò)這一套函數(shù)的處理，我們總是可以不用擔(dān)心是否在什么地方讓兩個(gè)ID指向了相同的類(lèi)型，或者一個(gè)類(lèi)型不小心擁有了多個(gè)ID，十分好管理。

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

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

int A=0;

int B(int C,int D)

{

  int E=0;

}

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

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

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

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

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