A symbol table is used by computer systems as a way of centralizing information and reducing the size of programs. These tables work like the key to a secret code; a symbol or string is placed next to another, generally much larger, piece of information. When a program reads a symbol that is associated with the symbol table, the program references the table and takes the information rather than the symbol. This allows large pieces of information or commonly repeated structures to only have one entry, reducing the overall size of the program.
The concept behind a symbol table is very simple. A single table contains a wide range of information used by a program, each with its own entry and unique associated symbol. This information could be strings of code, debugging information, memory locations, literally anything that the program could use in order to function. Rather than include that information within the program, the code simply references the table using its unique symbol.
Machine-language instructions are a unit of execution in a computer system. Machine language instructions can be further subdivided into micro instructions within a computer processor and are themselves subdivisions of high-level language statements and expressions.
A compiler translates source code into machine-language instructions. In some cases, particularly in UNIX environments, development environments or compiler construction courses, compilers translate source code into human-readable assembly-language code. Sometimes entire systems are written in assembly language and sometimes just a subroutine. The C programming language has a construct that permits assembly code within a statement.
An assembler translates assembly-language code into machine-language instructions. An assembler operates on a source file and produces an object-code file. These represent two forms of the same program unit. Assembly instructions may refer to operands that are not defined in the same unit. These are called external references. Assembly programs may contain storage locations that are referred to from other program units. These are called external definitions.
A linker combines two or more object-code files to produce either another object file or an executable file. Theoretically, the only difference between an object file and an executable file is that the executable has no unresolved external references. In fact, there may be references in the executable file that are not resolved until load time.
Relocation occurs both when a linker combines object files and when a loader copies an executable file into memory in preparation for execution.
符號(hào)表對(duì)于一個(gè)編譯器的重要性無(wú)論如何強(qiáng)調(diào)都不過(guò)分。在編譯過(guò)程中，編譯器使用符號(hào)表來(lái)記錄源程序中各種名字的特性信息。所謂“名字”包括: 程序名、過(guò)程名、函數(shù)名、用戶定義類型名、變量名、常量名、枚舉值名、標(biāo)號(hào)名等，所謂“特性信息”包括: 上述名字的種類、類型、維數(shù)、參數(shù)個(gè)數(shù)、數(shù)值及目標(biāo)地址（存儲(chǔ)單元地址）等。
符號(hào)表上的操作包括填表和查表兩種。當(dāng)分析到程序中的說(shuō)明或定義語(yǔ)句時(shí), 應(yīng)將說(shuō)明或定義的名字, 以及與之有關(guān)的特性信息填入符號(hào)表中，這便是填表操作。查表操作被使用得更為廣泛，需要使用查表操作的情況有：填表前查表，檢查在程序的同一作用域內(nèi)名字是否重復(fù)定義；檢查名字的種類是否與說(shuō)明一致；對(duì)于那些類型要求更強(qiáng)的語(yǔ)言，要檢查表達(dá)式中各變量的類型是否一致；生成目標(biāo)指令時(shí)，要取得所需要的地址或者寄存器編號(hào)，等等。符號(hào)表的組織方式也有多種多樣，你可以將程序中出現(xiàn)的所有符號(hào)組織成一張表，也可以將不同種類的符號(hào)組織成不同的表（例如，所有變量名組織成一張表，所有函數(shù)名組織成一張表，所有臨時(shí)變量組織成一張表，所有結(jié)構(gòu)體定義組織成一張表等等）；你可以針對(duì)每一個(gè)語(yǔ)句塊、每一個(gè)結(jié)構(gòu)體都新建一張表，也可以將所有語(yǔ)句塊中出現(xiàn)的符號(hào)全部插入到同一張表；你的表可以僅支持插入不支持刪除（此時(shí)如果要實(shí)現(xiàn)作用域的話需要將符號(hào)表組織成層次結(jié)構(gòu)），也可以組織一張既可以插入又可以刪除的、支持動(dòng)態(tài)更新的表。不同的組織方式各有利弊，我希望你在看完了這篇文章并經(jīng)過(guò)自己的仔細(xì)思考之后自行權(quán)衡利弊，并做出你自己的決定。
符號(hào)表里應(yīng)該填些什么？這個(gè)問(wèn)題的答案取決于不同的程序設(shè)計(jì)語(yǔ)言的特性，更取決于編譯器的設(shè)計(jì)者本身。換句話說(shuō)：只要你覺(jué)得方便，隨便你往符號(hào)表里塞任何內(nèi)容！畢竟符號(hào)表歸根結(jié)底就是為了我們編譯器的書寫方便而設(shè)置的。單就本次實(shí)習(xí)來(lái)看，對(duì)于變量你至少要記錄變量名和變量類型，對(duì)于函數(shù)你至少要記錄返回類型、參數(shù)個(gè)數(shù)以及參數(shù)類型。符號(hào)表應(yīng)該采用何種數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)？這個(gè)問(wèn)題同樣沒(méi)有一個(gè)統(tǒng)一的答案。不同的數(shù)據(jù)結(jié)構(gòu)有不同的時(shí)間復(fù)雜度、空間復(fù)雜度以及編程復(fù)雜度，幾種最常見(jiàn)的選擇有：
符號(hào)表里所有的符號(hào)都用一條鏈表串起來(lái),插入一個(gè)新的符號(hào)只需將這個(gè)符號(hào)放在鏈表的表頭,時(shí)間效率為O(1)；在鏈表里查找一個(gè)符號(hào)需要對(duì)其進(jìn)行遍歷，時(shí)間效率為O(n)；刪除一個(gè)符號(hào)只需要將這個(gè)符號(hào)從鏈表里摘下來(lái)，不過(guò)在摘之前由于我們必須要執(zhí)行一次查找操作找到待刪除的節(jié)點(diǎn)，因此時(shí)間效率也是O(n)。
鏈表的最大問(wèn)題就在于它的查找和刪除效率太低，一旦符號(hào)表中的符號(hào)數(shù)量增大之后，查表操作將變得十分耗時(shí)。不過(guò)，使用鏈表的好處也顯而易見(jiàn)：它的結(jié)構(gòu)簡(jiǎn)單、編程復(fù)雜度極低，可以被快速地、無(wú)錯(cuò)地實(shí)現(xiàn)。如果你事先能夠確定表中的符號(hào)數(shù)目非常非常少（例如，在結(jié)構(gòu)體的定義中或者在面向?qū)ο笳Z(yǔ)言的一些短方法中），那么鏈表也是一個(gè)非常不錯(cuò)的選擇。
相對(duì)于只能執(zhí)行線性查找的鏈表而言，在平衡二叉樹(shù)上進(jìn)行的查找天生就是二分查找。在一個(gè)典型的平衡二叉樹(shù)實(shí)現(xiàn)（例如AVL樹(shù)、紅黑樹(shù)、伸展樹(shù)等）上查找一個(gè)符號(hào)的時(shí)間效率為O(logn);插入一個(gè)符號(hào)相當(dāng)于進(jìn)行一次失敗的查找找到待插入的位置，時(shí)間效率同樣為O(logn)；刪除一個(gè)符號(hào)可能需要做更多的維護(hù)操作，但其時(shí)間效率仍然維持在O(logn)級(jí)別。
平衡二叉樹(shù)相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)而言具有很多優(yōu)勢(shì)，例如較高的搜索效率（在絕大多數(shù)應(yīng)用中O(logn)的搜索效率已經(jīng)完全可以被接受了）以及較好的空間效率（它所占用的空間隨樹(shù)中節(jié)點(diǎn)的增長(zhǎng)而增長(zhǎng)，不像散列表那樣每一張表都需要大量的空間占用）。平衡二叉樹(shù)的缺點(diǎn)是編程復(fù)雜太高，成功寫完并調(diào)試出一個(gè)能用的紅黑樹(shù)所需要的時(shí)間不下于你完成本次實(shí)習(xí)所需的時(shí)間。不過(guò)如果你真的想要使用紅黑樹(shù)，其實(shí)并不需要自己動(dòng)手寫，從其他的地方（例如，Linux內(nèi)核代碼中）尋找一個(gè)別人寫的紅黑樹(shù)一樣是可行的。
散列表代表了一個(gè)數(shù)據(jù)結(jié)構(gòu)可以達(dá)到的搜索效率的極致，一個(gè)好的散列表實(shí)現(xiàn)可以讓插入、查找和刪除的平均時(shí)間效率都達(dá)到O(1)。同時(shí)，與紅黑樹(shù)等操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)不同，散列表在代碼實(shí)現(xiàn)上竟是如此令人驚訝地簡(jiǎn)單：申請(qǐng)一個(gè)大數(shù)組、計(jì)算一個(gè)散列函數(shù)的值、然后根據(jù)這個(gè)值將該符號(hào)放到數(shù)組相應(yīng)下標(biāo)的位置即可。對(duì)于符號(hào)表來(lái)說(shuō)，一個(gè)最簡(jiǎn)單的hash函數(shù)只需要把符號(hào)名中的所有字符相加，然后對(duì)符號(hào)表的大小取模。你可以自己去尋找一些更好的hash函數(shù)，這里我提供一個(gè)不錯(cuò)的選擇，由P.J.Weinberger所提出：
|
需要注意的是，該方法對(duì)符號(hào)表的大小有要求——必須是2的某個(gè)乘冪。這個(gè)乘冪到底是多少，留給需要采用這種方法的你在理解這段代碼的含義之后自己思考。
如果出現(xiàn)沖突，則可以通過(guò)在相應(yīng)數(shù)組元素下面掛一個(gè)鏈表的方式（稱為open hashing或者close addressing方法，推薦使用）或者再次計(jì)算散列函數(shù)的值從而為當(dāng)前符號(hào)尋找另一個(gè)槽的方式（稱為open addressing或者rehashing方法）來(lái)解決。如果你還知道一些更加fancy的技術(shù)，例如Multiplicative hash function以及Universal hash function，那將會(huì)使你的散列表的元素分布更加平均一些。
由于散列表無(wú)論在搜索效率還是在編程復(fù)雜度上的優(yōu)異表現(xiàn)，它也成為了符號(hào)表的實(shí)現(xiàn)中最常被采用的數(shù)據(jù)結(jié)構(gòu)。
目前為止我仍然沒(méi)有找到對(duì)這個(gè)名字合適的翻譯。雖然散列表的平均搜索效率很高，但在最壞情況下它會(huì)退化為O(n)的線性查找，而且?guī)缀跞魏未_定的散列函數(shù)都存在某種最壞的輸入。另外，散列表所要申請(qǐng)的內(nèi)存空間往往要比輸入程序中出現(xiàn)的所有符號(hào)的數(shù)量還要多，未免有些浪費(fèi)——如果我們?yōu)檩斎氤绦蛑谐霈F(xiàn)每一個(gè)符號(hào)都分配一個(gè)單獨(dú)的編號(hào)和單獨(dú)的空間，豈不是既省空間又不會(huì)出現(xiàn)沖突嗎？
Multiset discrimination所基于的就是這種想法。在詞法分析部分，我們統(tǒng)計(jì)輸入程序中出現(xiàn)的所有符號(hào)（包括變量名、函數(shù)名等等），然后把這些符號(hào)按照名字進(jìn)行排序，最后開(kāi)一張與符號(hào)總數(shù)一樣大的散列表，某個(gè)符號(hào)的散列函數(shù)即為該符號(hào)在我們之前的排序里的序號(hào)。類似的想法在自然語(yǔ)言處理中也有應(yīng)用。
聯(lián)系客服
