author: Kevin Lynx email: zmhn320#163.com date: 3.10.2009
符號(hào)表
在上一節(jié)中，當(dāng)我們的解釋器解釋執(zhí)行age=age+1這個(gè)語法樹時(shí)，會(huì)涉及到變量age的值
。實(shí)際上我們還需要個(gè)保存腳本中相關(guān)變量的模塊，當(dāng)我們的解釋器獲取到一個(gè)ID樹節(jié)點(diǎn)時(shí)
，需要從這個(gè)模塊中獲取出該變量的值，并參與運(yùn)算。
這個(gè)我稱之為符號(hào)表。我想到這里，我所說的概念很可能和教科書有點(diǎn)不一樣了。
什么是符號(hào)表？
符號(hào)表(symbol table)就如同其字面意思一樣，是一個(gè)表，更寬泛地說是一個(gè)保存符號(hào)
的容器。
腳本中諸如變量函數(shù)之類的東西都算作符號(hào)，例如age。符號(hào)表就是保存這些符號(hào)的容
器。
在kl中，符號(hào)表保存著某一個(gè)作用域里的變量。其全局符號(hào)表還保存著函數(shù)符號(hào)，對(duì)于
函數(shù)符號(hào)而言，其值為語法樹樹節(jié)點(diǎn)的指針值。當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，將該值轉(zhuǎn)換為樹節(jié)點(diǎn)，
然后執(zhí)行。當(dāng)然，這應(yīng)該算做解釋執(zhí)行一節(jié)的細(xì)節(jié)，不多說。
再明確下符號(hào)表的作用，舉例，在上一節(jié)中，涉及到這么一個(gè)例子函數(shù)：
value factor( TreeNode *node )
{
switch( node->type )
{
case ID:
/* 在這里，發(fā)現(xiàn)一個(gè)樹節(jié)點(diǎn)類型為ID，就需要根據(jù)ID對(duì)應(yīng)的名字，也就
是age，在符號(hào)表中查找age的值 */
return age；
/* ... */
}
}
以上注釋闡述了符號(hào)表的作用。
符號(hào)表的實(shí)現(xiàn)
其實(shí)不管符號(hào)表如何實(shí)現(xiàn)，對(duì)于其他模塊而言，對(duì)符號(hào)表的唯一要求就是提供幾個(gè)類似
這樣的接口：
value sym_lookup( const char *name );
void sym_insert( const char *name, value val );
也就是說，提供查找符號(hào)值，以及插入新符號(hào)的接口。
在kl中，使用了<編譯原理與實(shí)踐>中相同的符號(hào)表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。即使用了hash表，
hash數(shù)組中每個(gè)元素保存的是一個(gè)鏈表頭節(jié)點(diǎn)。每一個(gè)符號(hào)字符串通過散列函數(shù)得到hash數(shù)
組索引，然后在該索引里進(jìn)行一次線性查找。很典型的hash結(jié)構(gòu)。
另一方面，因?yàn)閗l支持全局和函數(shù)局部兩個(gè)作用域。所以kl中有一個(gè)全局符號(hào)表，用于
保存全局變量以及所有的函數(shù)符號(hào)；同時(shí)每一次進(jìn)入一個(gè)函數(shù)時(shí)，就會(huì)創(chuàng)建一個(gè)臨時(shí)的局部
符號(hào)表，用于存儲(chǔ)局部變量；后來，為了支持插件，插件函數(shù)被特定地保存在另一個(gè)全局符
號(hào)表里。
代碼導(dǎo)讀
kl中的符號(hào)表實(shí)現(xiàn)代碼在klsymtab.h/klsymtab.c中，實(shí)現(xiàn)比較簡單，無需多言。