第五章編程經驗——符號表 · ANSI C 面向對象編程

# 第五章編程經驗——符號表 > 來源：https://github.com/oxnz/ooc/blob/master/tex/chapter0x05.tex > 譯者：[oxnz](https://github.com/oxnz) 一個結構體明智的加長，以此來共享基本結構的功能，可以幫助省去笨重的`union`的使用。特別在具有動態綁定，我們得到了一種統一的且完美健壯的方式處理消息傳遞。一旦基本機制就位，一個新的擴展類就可以重用基本代碼容易的添加。作為一個例子，我們將會添加關鍵字、常量、變量和數學函數到第三章開始的小計算器中。所有這些對象存在一個符號表中并且共享相同的名稱搜索技術。 ## 掃瞄標識符在3.2節中我們實現了函數`scan()`，從主程序獲取一行輸入并在每次調用返回一個輸入符號。如果我們想引進關鍵字，命名常量等等，我們需要擴展`scan()`。像浮點數一樣，我們提取字符數字串以供深入分析： ``` #define ALNUM "ABCDEFGHIJKLMNOPQRSTUVWXYZ" \ "abcdefghijklmnopqrstuvwxyz" \ "_" "0123456789" static enum tokens scan (const char * buf) { static const char * bp; … if (isdigit(* bp) || * bp == '.') … else if (isalpha( *bp) || *bp == '_') { char buf[BUFSIZ]; int len = strspn(bp, ALNUM); if (len >= BUFSIZ) error("name too long: %-.10s…", bp); strncpy(buf, bp, len), buf[len] = '\0', bp += len; token = screen(buf); } ... ``` 一旦我們有了一個標識符，我們讓新函數`screen()`來決定它的`token`值應當是什么。如果有必要，`screen()`將會存放一個解析器可以識別的符號描述到全局變量`symbol`中。 ## 使用變量一個變量參與兩個操作：它的值被用作一個表達式的操作數，或者表達式的賦值對象。第一中操作是對3.5節中一個簡單的`factor()`擴展。 ``` static void * factor (void) { void * result; ... switch (token) { case VAR: result = symbol; break; ... ``` `VAR`是一個當`screen()`發現適當的標識符的時候放到`token`中的唯一值。有關標識符的附加信息被放到全局變量symbol中。在這種情況下，`symbol`包含一個節點來標示變量作為表達式樹中的一個葉子。`screen()`要么找到變量再符號表中或者使用描述`Var`去創建它。識別一個賦值有點復雜。如果我們的計算器允許如下兩種語法的聲明，它將會是舒適的： ``` asgn : sum | VAR = asgn ``` 不幸的是，`VAR`也可以出現在`sum`的左端，也就是說，使用我們遞歸下降的技術如何識別C風格嵌入賦值不是立即就能清楚的。因為我們想要學到如何操作關鍵字，我們設置如下的語法： > 這里有一個技巧：對`sum`做簡單嘗試。如果返回是下一個輸入符號是`=`，`sum`必定是一個變量葉子節點，我們就可以創建這個賦值。 ``` stmt : sum | LET VAR = sum ``` 這被翻譯成如下函數： ``` static void * stmt (void) { void * result; switch (token) { case LET: if (scan(0) != VAR) error("bad assignment"); result = symbol; if (scan(0) != '=') error("expecting ="); scan(0); return new(Assign, result, sum()); default: return sum(); } /* this i s comet */ } ``` 在主程序中我們調用`stmt()`來替代`sum()`，并且我們的識別器已經準備好操作變量。`Assign`是一個新的類型描述，來計算一個`sum`的值并賦值給一個變量。 ## 篩子--`Name` 賦值具有如下語法： ``` stmt : sum | LET VAR = sum ``` `LET`是關鍵字的一個例子。在構建篩子的過程中我們仍然可以決定什么標識符將標示`LET: scan()`從輸入行提取一個標識符并傳遞給`screen()`，是它在符號表中查找并返回`token`的適當值，至少一個變量，一個節點在`symbol`中。識別器丟棄`LET`但是插入變量作為葉子節點在樹中。對于另一個符號，例如一個算數函數的名稱，我們可能想要適用`new()`到`screener`返回的符號來獲取一個新的節點。因此，我們的符號表入口應當對與大部分具有相同的函數動態綁定與我們樹節點。對于一個關鍵字，一個`Name`需要包含輸入字符串和`token`值。稍后我們想要繼承`Name`；因此，我們定義結構在`Name.r`中： ``` struct Name { /* base structure */ const void * type; /* for dynamic linkage */ const char * name; /* may be malloc-ed */ int token; }; ``` 我們的符號從不死亡：他們的名字是預定義的常量字符串還是存儲的用戶自定義變量動態字符串是沒有關系的--我們將不會回收他們。在我們可以定義一個符號之前，我們需要輸入它到符號表。這不能通過調用`new(Name, ...)`來處理，因為我們想要支持更多比`Name`復雜的符號，并且我們想要隱藏符號表的實現。相反的，我們提供一個函數`install()`，它需要一個`Name`對象并把它插入到符號表中。這里給出符號表接口文件`Name.h`： ``` extern void * symbol; /* -> last Name found by screen() */ void install (const void * symbol); int screen (const char * name); ``` 識別器必須插入像`LET`的關鍵字到符號表中，在他們被`screener`發現之前。這些關鍵字可以被定義進一個常量表結構中--它對`install()`沒有影響。下面的函數被用來初始化識別： ``` #include "Name.h" #include "Name.r" static void initName (void) { static const struct Name names [] = { { 0, "let", LET }, 0 }; const struct Name * np; for (np = names; np->name; ++np) install(np); } ``` 注意`names[]`，關鍵字表，不需要被存儲。我們適用`Name`的標示來定義`names[]`，也就是說，我們包含`Name.r`。由于關鍵字`LET`被丟棄，我們不提供動態綁定的方法。 ## 父類的實現--`Name` 通過名字搜索符號是一個標準問題。不幸的是，ANSI標準沒有定義一個合適的庫函數來解決它。`bsearch()`--有序表中的二分查找--比較接近，但是如果我們想要插入一個單獨的新符號，我們不得不調用`qsort()`來設置階段給后續搜索。 UNIX系統很可能提供兩三個函數家族來處理動態增長表。`lsearch()`--線性搜索一個數組并在`end(!)`添加--不是完全高校的。`hsearch()`--一個結構體哈希表由一個文本和一個信息指針組成--維護一個固定大小的表并且強制一個尷尬的結構體入口。`tsearch()`--一個二叉樹具有任意比較和刪除--是最常用的家族但是很沒有效率，如果初始符號從一個有序序列中安裝。在一個UNIX系統上，`tsearch()`有可能是最好的折衷。對于一個可移植的實現具有二元線程樹可以在`[Sch87]`找到。然而，如果這個家族不可用，或者如果我們不能保證一個隨機的初始化，我們應當查看一個簡單的設備來實現。一個小心實現的`bsearch()`可以很容易的被擴展來支持存儲的數組插入： ``` void * binary (const void * key, void * _base, size_t * help, size_t width, int (* cmp) (const void * key, const void * elt)) { size_t nel = * nelp; #define base (* (char **) & _base) char * lim = base + nel * width, * high; if (nel > 0) { for (high = lim - width; base <= high; nel >>= 1) { char * mid = base + (nel >> 1) * width; int c = cmp(key, mid); if (c < 0) high = mid - width; else if (c > 0) base = mid + width, --nel; else return (void *) mid; } ``` 到這里為止，這是一個任意數組的二元搜索。`key`只想要找的對象；`base`初始值是一個具有`*nelp`個元素的表的開始位置，每個元素`width`字節；并且`cmp`是一個函數用來比較`key`和一個表中的元素。在此我們要么找到一個元素并返回它的位置，要么`base`現在是`key`應當出現在表中的位置地址。我們繼續如下： ``` memmove(base + wdith, base, lim - base); } ++ * nelp; return memcpy(base, key, width); #undef base } ``` `memmove()`移動數組的末尾，`memcpy()`插入`key`。我們假定數組之外還有空間并且我們通過`nelp`紀錄我們已經加入了一個元素--`binary()`和標準函數`bsearch()`只需要地址而不是變量的值包含餓了表中元素的個數。 > `memmove()`復制字節即使源和目標區域重疊；`memcpy()`并不如此，但是它更具效率給出一個通用搜索和入口的方式，我們可以很輕易的管理我們的符號表。首先我們需要比較一個key和表中的元素： ``` static int cmp (const void * _key, const void * _elt) { const char * const * key = _key; const struct Name * const * elt = _elt; return strcmp(* key, (* elt) -> name); } ``` 作為一個鍵值，我們只傳遞一個指向輸入符號文本的指針的地址。表中的元素當然是`Name` 結構體，并且我們只查看他們的`.name`成員。搜索和入口通過適用適當的參數對`binary()`進行調用來實現。由于我們事先不知道符號個數，我們確保一直有空間讓我們擴招表： ``` static struct Name ** search (const char ** name) { static const struct Name ** names; /* dynamic table */ static size_t used, max; if (used >= max) { names = names ? realloc(names, (max *= 2) * sizeof * names) : malloc((max = NAMES) * sizeof * names); assert(names); } return binary(name, names, & used, sizeof * names, cmp); } ``` `NAMES`是一個定義的常量具有初始分配的表項；每次我們用完，我們都是表的大小加倍。 `search()`適用指向要查找的文本的地址指針作為參數并且返回表項的地址。如果文本未找到，`binary()`就插入`key`--也就是說，只有指向文本的指針，而不是一個`struct Name`--到表中。這個策略是為了`screen()`的利益，它只新建一個表元素，如果一個輸入中的標識符是未知的： ``` int screen (const char * name) { struct Name ** pp = search(& name); if (* pp == (void *) name) /* entered name */ * pp = new(Var, name); symbol = * pp; return (* pp) -> token; } ``` `screen()`讓`search()`查找要顯示的輸入符號。如果指符號文本的指針被插入符號表，我們需要使用一個新標識符的項目描述替換它。對于`screen()`，一個新的標識符必須是一個變量。我們假定這里有一個類型描述`Var`知道如何構建`Name`結構體來描述變量并且我們讓`new()`做剩下的工作。其他的情況，我們讓`symbol`指向符號表項并且返回它的`.token`值。 ``` void install (const void * np) { const char * name = ((struct Name *) np) -> name; struct Name ** pp = search(& name); if (* pp != (void *) name) error("cannot install name twice: %s", name); * pp = (struct Name *) np; } ``` `install()`比較簡單。我們接受一個`Name`對象并且讓`search()`在符號表中找到它。`install()`被假定來只處理新符號，所以我們應當總是能夠插入對象替換它的名字。否則，如果`search()`真的找到一個符號，我們就有麻煩了。 ## 子類的事先--Var `screen()`調用`new()`來創建一個新的變量符號并且返回它到識別器，并插入它到一個表達式樹中。因此，`Var`必須創建可以項節點行為的符號表項，也就是說，當定義`struct Var`的時候，我們需要擴展一個`struct Name`來繼承在符號表中存在的能力并且我們必須支持動態綁定的函數可以適用于表達式節點。我們描述接口在`Var.h`中: ``` const void * Var; const void * Assign; ``` 一個變量具有一個名字和一個值。如果我們計算一個算術表達式的值，我們需要返回`.value`成員。如果我們刪除一個表達式，我們一定不能刪除變量節點，因為它存活在符號表中： ``` struct Var { struct Name _; double value; }; #define value(tree) (((struct Var *) tree) -> value) static double doVar (const void * tree) { return value(tree); } static void freeVar (void * tree) { } ``` 就如在4.6節中討論的，通過提供一個值的訪問函數來簡化代碼。創建一個變量需要分配一個`struct Var`，插入一個變量名的動態副本，并且標識值`VAR`被識別器規定： ``` static void * mkVar (va_list ap) { struct Var * node = calloc(1, sizeof(struct Var)); const char * name = va_arg(ap, const char *); size_t len = strlen(name); assert(node); node-> _.name = malloc(len + 1); assert(node -> _.name); strcpy((void *) node-> _.name, name); node -> _.token = VAR; return node; } static struct Type _Var = { mkVar, doVar, freeVar }; const void * Var = & _Var; ``` `new()`照料插入`Var`類型描述到節點中，在符號被`screen()`返回之前或者任何的使用。就技術而言，`mkVar()`是`Name`的構建子。然而，只有變量名需要被動態存儲。因為餓哦我們決定在我們的計算器中構建子負責分配一個對象，我們不能讓`Var`構建子調用一個`Name`構建子來維護`.name`和`.token`成員--一個`Name`構建子將會分配一個`struct Name`而不是一個`struct Var`。 ## 賦值賦值是一個二元操作。識別器保證我們具有一個變量作為做操作數和`sum`作為右操作數。因此，我們世紀需要實現的是實際賦值操作，也就是說，動態綁定進類型描述的`.exec`成員： ``` #include "value.h" #include "value.r" static double doAssign (const void * tree) { return value(left(tree)) = exec(right(tree)); } static struct Type _Assign = { mkBin, doAssign, freeBin }; const void * Assign = & _Assign; ``` 我們共享`Bin`的構建子和析構子，因此，在算數操作的實現中必須是全局的。我們也共享`struct Bin`和訪問函數`left()`和`right()`。所有這些使用`value.h`導出并且實現文件`value.r`。我們自己的訪問函數`value()`對于`struct Var`故意的允許修改，如此賦值就可以被很優雅的實現。 ## 另一個子類--常量誰會喜歡輸入`pi`或者其他數學常量的值呢？我們從Kernighan和Pike's hoc [K&P84]得到線索并且預定義一些常量給我們的計算器。下面的函數需要被調用在初始化識別器期間： ``` void initConst (void) { static const struct Var constants [] = { /* like hoc */ { &_Var, "PI", CONST, 3.14159265358979323846 }, ... 0 }; const struct Var * vp; for (vp = constants; vp -> _.name; ++ vp) install(vp); } ``` 變量和常量幾乎是一樣的：都具有名稱和值并且存活在符號表中；都返回他們的值在一個算數表達式的使用中；并且都不應當被刪除，當我們刪除一個算數表達式的時候。然而，我們不應當給常量賦值，所以我們需要同意一個新的標識符值`CONST`，識別器在`factor()`中接受就像`VAR`一樣，但是不允許在`stmt()`的賦值的左邊。 ## 數學函數--Math ANSI-C定義了許多數學函數例如`sin()`,`sqrt()`,`exp()`等等。作為另一個繼承的練習，我們將添加庫函數使用一個單個`double`參數并且具有一個`double`結構到我們的計算器。這些函數工作的就如同一元運算符一樣。我們可以定義一個新的類型給節點給每個函數并且收集大多數功能從`Minus`和`Name`類，但是這里有一個更簡單的方法。我們擴展`struct Name`到`struct Math`如下： ``` struct Math { struct Name _; double (* funct) (double); }; #define funct(tree) (((struct Math *) left(tree)) -> funct) ``` 額外的給函數名稱用于輸入和標識符給識別，我們存儲像`sin()`的庫函數的地址在符號表項中。在初始化期間我們調用下面的函數來輸入所有的函數描述到符號表中： ``` #include <math.h> void initMath (void) { static const struct Math functions [] = { { &_Math, "sqrt", MATH, sqrt }, ... 0 }; const struct Math * mp; for (mp = functions; mp -> _.name; ++ mp) install(mp); } ``` 一個函數調用是一個因子就好像使用一個減號標記一樣。對于識別我們需要擴展我們的語法對因子： ``` factor : NUMBER | - factor | ... | MATH ( sum ) ``` `MATH`是公共標識符對所有函數輸入通過`initMath()`。這個翻譯到下面的附加`factor()`在識別器中： ``` static void * factor (void) { void * result; ... switch (token) { case MATH: { const struct Name * fp = symbol; if (scan(0) != '(') error("expecting ("); scan(0); result = new(Math, fp, sum()); if (token != ')') error("expecting )"); break; } ``` `symbol`首先包含符號表元素對一個函數例如`sin()`。我們保存這個指針并且構建表達式樹對于函數參數通過調用`sum()`。然后我們使用`Math`，類型描述給函數，并且讓`new()`構建下面的節點給表達式樹：我們讓一個二元節點的左邊只想符號表元素給函數并且我們附加參數樹在右邊。這個二元節點具有`Math`作為類型描述，也就是說，方法`doMath()`和`freeMath()`將會被調用來分別執行和刪除節點。 Math節點仍然使用`mkBin()`構建，因為這個函數不關心指針的后代。`freeMath()`，然而，可能只會刪除右子樹： ``` static void freeMath (void * tree) { delete(right(tree)); free(tree); } ``` 如果我們仔細看上圖，我們可以看到一個`Math`節點的執行是非常容易的。`doMath()`需要調用存儲在符號表中元素可以被訪問的作為左后代二元節點從之被調用： ``` static double doMath (const void * tree) { double result = exec(right(tree)); errno = 0; result = funct(tree)(result); if (errno) error("error in %s: %s", ((struct Math *) left(tree)) -> _.name, strerror(errno)); return result; } ``` 唯一的問題是抓住數字錯誤通過檢測`errno`變量在ANSI-C頭文件`errno.h`中聲明。這個完成了數學函數的實現給計算器。 ## 總結機遇一個函數`binary()`來搜索和插入一個有序數組，我們實現了一個符號表包含了就誒夠體具有名稱和標識符值。繼承允許我們插入其他結構體到表中而不需要改變函數搜索和插入。這種方式的高雅變得明顯一旦我們考慮一個傳統的定義一個符號表元素出于我們的目的： ``` struct { const char * name; int token; union { /* based on token */ double value; double (* funct) (double); } u; }; ``` 對于關鍵字，`union`是沒有必要的。用戶定義的函數講會要求一個更詳細的描述，并且引用`union`的部分是討厭的。繼承允許我們適用符號表功能到新的項而不改變已經存在的代碼。動態綁定在許多方式幫助保持實現的簡單性：常量符號表元素，變量和函數可以被綁定進表達式樹中而不用擔心我們不慎刪除他們；一個執行函數參考自身值有它自己安排節點。 ## 練習新關鍵字是必須的用來實現例如`while`或者`repeat`循環，`if`語句等等。識別被`stmt()`處理，但是這個對于大部分情況，只有一個問題編譯器構建，而不是繼承。一旦我們決定語句描述，我們將創建節點類型例如`While`，`Repeat`或者`IfElse`，并且關鍵字在符號表中不需要知道他們的存在。更有趣的是函數具有兩個參數的例如`atan2()`在ANSI-C數學庫中。從這里看出符號表，這個函數被處理僅僅類似簡單函數，但是對于表達式樹我們需要開發一個新的節點類型使用三個后代。用戶定義的函數具有一個現實的有意思的問題。如果我們表示單獨的參數通過`$`并且我們使用一個節點類型`Parm`來只想函數項在符號表中從那里我們可以暫時存儲參數值只要我們不允許遞歸，就是簡單的。函數具有參數名和幾個參數是比較困難的，當然了。然而，這是一個好的練習`inverstigate`繼承的好處和動態綁定的好處。我們將在第11章中返回到這個問題。