第三章編程的悟性——算術表達式 · ANSI C 面向對象編程

# 第三章編程的悟性——算術表達式 > 來源：http://blog.csdn.net/besidemyself/article/details/6423491 > 譯者：[besidemyself](http://my.csdn.net/besidemyself) 動態連接就其本身而言是一項強大的編程技術，并不是去寫一些帶有龐大的`switch` 語句去處理很多特例的函數。我們可以寫很多小的函數，對于每個`case` 語句，安排適當的函數被動態連接調用。這樣做通常簡化了編程工作并且會使得代碼容易擴展。作為一個例子，我們將寫一個小的程序去讀并評估由浮點數字，括號，常用操作符，減號，等組成的算術表達式。正常情況下我們寧愿使用編譯器產生器工具`lex`和`yacc` 去建立這部分的程序去剖析算術表達式。這不是一本關于編譯器建立的書，然而，就僅僅此次我們將自己寫這次的代碼。 ## 3.1 主循環程序的主循環從標準輸入讀取一行數據，初始化以便數字和操作符能被提取出來，空格被忽略，調用一個函數去確認正確的算術表達式并存儲之，最終處理所存儲的表達式。如果出錯了，我們簡單的讀取下一行數據。如下為主循環： ```c #include <setjmp.h> int main (void) { volatile int errors = 0; char buf [BUFSIZ]; if (setjmp(onError)){ ++ errors; } while (fgets(buf, sizeof buf, stdin)){ if (scan(buf)) { void * e = sum(); if (token){ error("trash after sum"); } process(e); delete(e); } } return errors > 0; } void error (const char * fmt, ...) { va_list ap; va_start(ap, fmt); vfprintf(stderr, fmt, ap), putc('/n', stderr); va_end(ap); longjmp(onError, 1); } ``` 錯誤恢復點被使用`setjmp()` 所定義。如果`error()` 在程序中的某個位置被調用，`longjmp()` 伴隨著從 `setjmp()` 另外一個返回而繼續執行。在這種情況下，結果是一個值被傳進 `longjmp()` ，錯誤累加，而且下一個輸入行被讀取。如果遇到錯誤，程序的出口代碼將報告錯誤。 ## 3.2 掃描器在主循環中，一旦一個輸入行被讀入到`buf[]` 中，它將被傳進 `scan()`, 此函數對于每一個調用把下一個輸入符號放入變量`token` 。在最后一行，`token` 的值為0： ```c #include <ctype.h> #include <errno.h> #include <stdlib.h> #include “parse.h” static double number; /* if NUMBER: numerical value */ static enum tokens scan (const char * buf) { static const char * bp; if (buf){ bp = buf; /* new input line */ } while (isspace(* bp & 0xff)){ ++ bp; } if (isdigit(* bp & 0xff) || * bp == '.') { errno = 0; token = NUMBER, number = strtod(bp, (char **) & bp); if (errno == ERANGE){ error("bad value: %s", strerror(errno)); } } else{ token = * bp ? * bp ++ : 0; } return token; } ``` 我們調用 `scan()` ，可傳遞輸入行緩沖的地址，或傳進一個空指針得以繼續工作在當前的行。空格被忽略，并且遇到第一個為數字或小數點，我們就是用一個ANSI-C 的函數 `strtod()` 開始提取出浮點數字。若為其他的任何字符將被返回，并且我們不會預先在輸入緩沖傳遞一個空字節。 `scan()` 的結果被存儲在全局變量`token` ——這樣簡化了識別程序（識別器）。如果我們偵測出一個數字，我們將返回唯一的值 `NUMBER` 并使得在全局變量`number` 中實際的值有效。 ## 3.3 識別器在最高水平,表達式通過函數`sum()` 被識別，`sum()` 函數內部調用`scan()` 并返回一個表示，這個表示可通過調用 `process()` 被處理并通過`delete()` 被回收。如果我們不使用`yacc`(是Unix/Linux上一個用來生成編譯器的編譯器（編譯器代碼生成器）），我們將通過遞歸下降的方法識別表達式，合乎語義的規則被翻譯成等價的C函數。例如：一個`sum` 是一個產物，接下來被0跟隨，或更多的組，每個由額外的操作符和另外的產物組成，一個語義規則如下： ``` sum：product {+|- product}… ``` 被翻譯成C函數如下： ```c static void * sum (void) { void * result = product(); const void * type; for (;;) { switch (token) { case '+': case '-': scan(0),product();continue; return; } } ``` 對于每一個語義規則有一個C函數，以便于這些規則能夠相互調用，這些不同的分支被轉換成`switch` 或 `if` 語句，迭代的語法將在C中翻譯成循環。僅僅一個問題就是我們必須避免無限的遞歸。 `token` 總是包含下一個輸入的符號。如果我們識別出它，我們必須調用`scan(0)` ## 3.4 處理器我們如何來處理表達式呢？如果我們僅僅想用一些用數字表示的值執行簡單的算術。我們可以擴展識別函數并且一旦識別出操作符和操作碼就計算出結果如：`sum()` 應該會期望從每一個對 `product()` 的調用期望一個`double` 類型的結果，盡可能的執行加或減法，并且返回結果，再次作為一個`double` 類型函數的值。如果我們想要建立一個系統用來處理更加復雜的表達式，我們需要存儲表達式以便于后續處理。在這種情況下，我們能夠不僅僅執行算術，而且可以允許決定并且有條件的評估一個表達式的一部分，且可用存儲的表達式作為用戶的函數包含在其他表達式中。我們所需要的是一個合理通用的方式代表一個表達式。比較常規的技術是使用一個二叉樹在每一個節點上存儲 `token`. ```c struct Node { enum tokens token; struct Node * left, * right; }; ``` 然而，這樣并不是很靈活。我們需要介紹一個`union` 去創建一個節點，在這個節點上我們可存儲一個數，并且我們在這些節點代表的一元操作符上浪費了空間。此外，`process()` 和 `delete()` 將包含`witch` 分支，并`witch` 分支會隨著我們增加的符號而增多。 ## 3.5 信息隱藏應用迄今為止我們學到的，我們絕不去揭示節點結構。相反，我們先在頭文件 `value.h`中放置一些聲明如下： ```c const void * Add; … void * new (const void * type, ...); void process (const void * tree); void delete (void * tree); ``` 現在我們可以編寫代碼 `sum()` 如下： ```c #include "value.h" static void * sum (void) { void * result = product(); const void * type; for (;;) { switch (token) { case '+': type = Add; break; case '-': type = Sub; break; default: return result; } scan(0); result = new(type, result, product()); } } ``` `product()` 與 `sum()` 有相同的結構，并且調用一個函數 `factor()` 去識別數字，符號，且`sum`被賦予了括號： ```c static void * factor (void) { void * result; switch (token) { case '+': scan(0); return factor(); case '-': scan(0); return new(Minus, factor()); default: error("bad factor: '%c' 0x%x", token, token); case NUMBER: result = new(Value, number); break; case '(': scan(0); result = sum(); if (token != ')') error("expecting )"); } scan(0); return result; } ``` 尤其在 `factor()` 中，我們需要特別小心的保持掃描器（scanner）是不變的：`token` 必須總是包含下一個輸入的符號。一旦`token` 被使用，我們需要調用 `scan(0)`。 ## 3.6 動態連接識別器是完善的。`value.h` 對于算術表達式完全隱藏了求值程序，且與此同時指定了我們必須所實現的。 `new()` 攜帶描述符，如`Add` 和合適的參數如指針對加的操作且返回一個表示和的指針。 ```c struct Type { void * (* new) (va_list ap); double (* exec) (const void * tree); void (* delete) (void * tree); }; void * new (const void * type, ...) { va_list ap; void * result; assert(type && ((struct Type *) type) -> new); va_start(ap, type); result = ((struct Type *) type) -> new(ap); * (const struct Type **) result = type; va_end(ap); return result; } ``` 我們使用動態連接并傳遞一個對指定節點例程的調用，在例程中的`Add` 分支處，必須常見一個節點，并且傳進兩個指針。 ```c truct Bin { const void * type; void * left, * right; }; static void * mkBin (va_list ap) { struct Bin * node = malloc(sizeof(struct Bin)); assert(node); node -> left = va_arg(ap, void *); node -> right = va_arg(ap, void *); return node; } ``` 注意，只有 `mkBin()` 知道它創建的是什么。所有我們要求的是各個節點對于動態連接是以一個指針開始。這個指針被 `new()` 傳進一遍于`delete()` 能夠調用到它指定節點的函數： ```c void delete (void * tree) { assert(tree && * (struct Type **) tree && (* (struct Type **) tree) -> delete); (* (struct Type **) tree) -> delete(tree); } ``` 動態連接很優雅的避免了復雜難解的節點。`.new()` 精確的創建了每個類型描述符的右節點：二元操作符擁有兩個子孫。一元操作符擁有一個子孫，且值節點僅僅包含了值。`delete() `是一個非常簡單的函數因為每個節點處理它自己的銷毀過程：二元操作符刪除兩個子樹并且釋放他們自己的節點，一元操作符僅僅刪除一個子樹，且值節點僅僅釋放自己。變量和常量甚至可以留到后面——對于`delete()` 的回應他們簡單的什么也不做。 ## 3.7 A Postfix Writer 到目前為止我們還沒有真正的決定 `process()` 將要真正做什么。如果我們想要發布一個表達式的后綴版，我們將要對 `struct Type` 增加一個字符串以便于顯示出實際的操作符，且 `process()` 將要安排一個單獨的被`tab` 鍵縮進的行： ```c void process (const void * tree) { putchar('/t'); exec(tree, (* (struct Type **) tree) -> rank, 0); putchar('/n'); } ``` `exec()` 處理動態連接 ```c static void exec (const void * tree, int rank, int par) { assert(tree && * (struct Type **) tree && (* (struct Type **) tree) -> exec); (* (struct Type **) tree) -> exec(tree, rank, par); } ``` 每一個二元操作符被使用如下函數發出： ```c static void doBin(const void *tree) { exec(((struct Bin *) tree) —> left); exec(((struct Bin *) tree) —> right); printf(" %s", (* (struct Type **) tree) —> name); } ``` 類型描述符如下綁定： ```c static struct Type _Add = { "+", mkBin, doBin, freeBin }; static struct Type _Sub = { "—", mkBin, doBin, freeBin }; const void * Add = & _Add; const void * Sub = & _Sub; ``` 應該很容易猜測一個數值是怎樣被實現的。它被代表作為一個結構體攜帶`double` 類型的信： ```c struct Val { const void * type; double value; }; static void * mkVal (va_list ap) { struct Val * node = malloc(sizeof(struct Val)); assert(node); node —> value = va_arg(ap, double); return node; } ``` 處理組成的打印值： ```c static void doVal (const void * tree) { printf(" %g", ((struct Val *) tree) —> value); } ``` 我們已經做了——沒有子樹要刪除，因此我們可以使用庫函數 `free()` 直接的刪除值節點： ```c static struct Type _Value = { "", mkVal, doVal, free }; const void * Value = & _Value; ``` 一元操作符如`Minus` 將留作練習。 ## 3.8 算術如果我們想做算術運算，我們讓執行的函數返回一個`double` 類型的值，然后讓`process()` 打印這個值： ```c static double exec (const void * tree) { return (* (struct Type **) tree) —> exec(tree); } void process (const void * tree) { printf("/t%g/n", exec(tree)); } ``` 對于每個節點的類型，我們需要一個執行函數來計算和返回這個節點的值。這里有兩個實例： ```c static double doVal (const void * tree) { return ((struct Val *) tree) —> value; } static double doAdd (const void * tree) { return exec(((struct Bin *) tree) —> left) + exec(((struct Bin *) tree) —> right); } static struct Type _Add = { mkBin, doAdd, freeBin }; static struct Type _Value = { mkVal, doVal, free }; const void * Add = & _Add; const void * Value = & _Value; ``` ## 3.9 插入輸出也許對于處理算術表達式的突出點是帶小括號的形式打印。這通常是有點滑稽的，依照誰來負責發出括號。此外對于操作符的名字用于前綴輸出，我們增加了兩個數值到`struct Type`中。 ```c struct Type { const char * name; /* node’s name */ char rank, rpar; void * (* new) (va_list ap); void (* exec) (const void * tree, int rank, int par); void (* delete) (void * tree); }; ``` `.rank` 是優先的操作符，以1開始，此外 `.rpar` 被設置用于操作符，如減操作，此操作如果用于相等的優先級的操作就要求他們的右操作被附上括號。 ``` $ infix 1 + (2 — 3) 1 + 2 — 3 1 — (2 — 3) 1 — (2 — 3) ``` 這個證實了我們需要如下的初始化： ```c static struct Type _Add = {"+", 1, 0, mkBin, doBin, freeBin}; static struct Type _Sub = {"—", 1, 1, mkBin, doBin, freeBin}; ``` 滑稽的部分是對于二元節點得去決定它是否必須要增加括號。一個二元節點如加法，被給予它自己較高的優先級并且一個標記指示在相等的優先級中括號是否是必須的。`doBin()` 去判別是否使用括號: ```c static void doBin (const void * tree, int rank, int par) { const struct Type * type = * (struct Type **) tree; par = type —> rank < rank || (par && type —> rank == rank); if (par) putchar(’(’); exec(((struct Bin *) tree) —> left, type —> rank, 0); printf(" %s ", type —> name); exec(((struct Bin *) tree) —> right, type —> rank, type —> rpar); if (par) putchar(’)’); } ``` 與高優先級的操作符比若我們有一個較低優先級，或者如果我們被要求在相等的優先級情況下輸出括號，我們就打印括號。在任何情況下，如果我們的描述有 `.rpar` 的設置，我們要求僅僅我們的所有操作輸出額外的括號如上：保持打印的實例程序是較容易寫的。 ## 3.10 總結三種不同的處理器證實了信息隱藏的優越性。動態連接幫助我們把一個問題分解成很簡單的函數功能點。最終的程序是很容易擴展的——試著去增加C語言中的比較和如`?:`的操作符吧。