LLVM平臺，短短幾年間，改變了眾多編程語言的走向，也催生了一大批具有特色的編程語言的出現，不愧為編譯器架構的王者，也榮獲2012年ACM軟件系統獎 —— 題記
版權聲明：本文為 西風逍遙游 原創文章，轉載請注明出處 西風世界 [http://blog.csdn.net/xfxyy_sxfancy](http://blog.csdn.net/xfxyy_sxfancy)
# 棧式符號表的構建
棧式符號表對于一款編譯器，無疑是核心的組件。
無論你在做什么符號掃描，那么都離不開符號表，如何得知一個符號是否定義，以及它的類型，那么唯有查看符號表中的記錄。
棧式符號表并不復雜，但思想精妙，本文，將介紹一款棧式符號表的原理及簡單構建。
### 源代碼的例子
首先我們來看一段C代碼
~~~
int a[3] = { 100, 10, 1};
int work() {
if (a[0] == 100) { // 這里的a指向的是全局符號a
int a = 99999; // 重新定義了局部符號 下圖的符號表是掃描到這里后的情況
for (int i = 0; i< 10; ++i) {
a /= 3; // 由于局部符號優先級較高，引用局部符號
}
return a; // 局部符號
}
return a[0]; // 局部符號生命周期已過，找到全局符號
}
~~~
于是我們發現，符號表在局部聲明變量后，將局部符號增加了，這和全局符號并不沖突，而是優先級不同，越靠近棧頂，越先發現
### 用C++的map和stack構建符號表
如果考慮效率的話，最佳選擇是用C語言構建符號表，這樣操作起來會更快，但我們畢竟目前考慮開發的簡便型而言，用C++的map就可以方便地實現符號表。
首先我們做一個局部符號表，由于其中不會有重復的符號名，所以我們只要簡單的將其存放起來即可。
然后符號表還需要記錄很多類型信息、指針信息等，我們設計一個結構體表示它們：
~~~
enum SymbolType
{
var_t, type_t, struct_t, enum_t, delegate_t, function_t
};
struct id {
int level;
SymbolType type;
void* data;
};
~~~
我們目前是簡單起見，由于還不知道都可能放哪些東西，例如數組符號，肯定要包含數組長度、維度等信息，各種變量都會包含類型信息，所以我們這里放了一個void*的指針，到時候需要的化，就強制轉換一下。
這里其實定義一個基類，需要存儲的內容去多態派生也是可以的，沒做主要是因為可能存放的東西類型很多，暫時先用一個void*，這樣可能方便一點。
于是我們的局部符號表就有了：
~~~
class IDMap
{
public:
IDMap();
~IDMap();
id* find(string& str) const; // 查找一個符號
void insert(string& str, int level, SymbolType type, void* data); // 插入一個符號
private:
map<string,id*> ID_map;
};
~~~
我想查找和插入都是C++中map的基礎函數，大家應該很輕松就能實現吧。
再弄一個棧來存儲一個IDMap：
~~~
class IDTable
{
public:
IDTable();
id* find(string& str) const;
void insert(string& str,SymbolType type, void* data);
void push(); // 壓棧和彈棧操作，例如在函數的解析時，需要壓棧，一個函數解析完，就彈棧
void pop();
int getLevel(); // 獲取當前的層級，如果為0，則說明是只有全局符號了
private:
deque<IDMap> ID_stack;
};
~~~
這里用deque而沒用stack的原因是，deque支持隨機訪問，而stack只能訪問棧頂。
尋找時，就按照從棧頂到棧底的順序依次尋找符號：
~~~
id* IDTable::find(string& idname) const {
for (auto p = ID_stack.rbegin(); p != ID_stack.rend(); ++p) {
const IDMap& imap = *p;
id* pid = imap.find(idname);
if (pid != NULL) return pid;
}
return NULL;
}
~~~
插入時，就往棧頂，當前最新的符號表里面插入：
~~~
void IDTable::insert(string& str,SymbolType type, void* data) {
IDMap& imap = ID_stack.back();
imap.insert(str,getLevel(), type, data);
}
~~~
這樣，一款簡易的棧式符號表就構建好了。
### 附1：Github參考源碼
[idmap.h](https://github.com/sunxfancy/RedApple/blob/master/src/idmap.h)
[idmap.cpp](https://github.com/sunxfancy/RedApple/blob/master/src/idmap.cpp)
[idtable.h](https://github.com/sunxfancy/RedApple/blob/master/src/idtable.h)
[idtable.cpp](https://github.com/sunxfancy/RedApple/blob/master/src/idtable.cpp)
### 附2：Graphviz的繪圖源碼
Graphviz繪圖真的非常爽，上面的數據結構圖就是用它的dot畫的，想了解的朋友可以參考我之前寫的 [結構化圖形繪制利器Graphviz](http://blog.csdn.net/xfxyy_sxfancy/article/details/49641825)：
~~~
digraph g {
graph [
rankdir = "LR"
];
node [
fontsize = "16"
shape = "ellipse"
];
edge [
];
"node0" [
label = "<f0> stack | <f1> | <f2> | ..."
shape = "record"
];
"node1" [
label = "<f0> 全局符號 | a | work | | ..."
shape = "record"
]
"node2" [
label = "<f0> 局部符號 | a | | ..."
shape = "record"
]
"node0":f1 -> "node1":f0 [
id = 0
];
"node0":f2 -> "node2":f0 [
id = 1
];
}
~~~
