軟件工程設(shè)計(jì)模式uml程序設(shè)計(jì)實(shí)踐

采用正確的語言有可能使某個(gè)程序的書寫變得容易許多。正是由于這種情況，在實(shí)際程序員的里都許多西，僅像C這一類的通用語言，還有可編程的s、語言以及許多面向特定用途的語言。好記法的不僅表現(xiàn)在傳統(tǒng)的程序設(shè)計(jì)中，也體現(xiàn)在各種特定問題領(lǐng)域。正則表達(dá)式使我們能以非常緊湊的形式(或許還有點(diǎn)像)；HTML使我們能定義交互式文檔的編排格式，其中還常常嵌入其他語言，如JavaScriptPostScript能把整個(gè)文檔—例如這本書—如iulac，以計(jì)其中表達(dá)，有關(guān)，或者格式排的制等。如果你發(fā)現(xiàn)自己為某些平庸的事情寫了太多代碼，或者你需要表述某些過程卻遇到了很大麻煩，那么你正在使用的很可能是一種不適當(dāng)?shù)恼Z言。如果合適的語言不存在，那么這很可能就是個(gè)機(jī)會，需要你自己來建立一種。發(fā)明語言并不意味著是建立某種像Java那樣復(fù)雜的東西，許多棘手的問題常?？梢酝ㄟ^改變描述方式的辦法來解決。請考慮一下printf一類函數(shù)的格式描述串，那就可以看作是一種控制數(shù)據(jù)打印方式的、緊湊的、描述能力很強(qiáng)的語言。在本章中我們要討論怎樣通過記法去解決問題。這里還要展示一些技術(shù)，這些技術(shù)可以用于實(shí)現(xiàn)你自己的語言。我們還要探索用程序來寫其他程序的可能性，這是記法使用的一種形式，也是很常見的。實(shí)際上，這種技術(shù)并不難使用，遠(yuǎn)不像許多程序員所認(rèn)為的那樣。在我們最希望對計(jì)算機(jī)說的東西()與為了使一個(gè)工作能夠完成而必須說的東西之間，存在著一條鴻溝。能把這條鴻溝填得越窄，當(dāng)然就越好。好的記法使我們能更容易說出自己想說的東西，又不太容易因?yàn)椴划?dāng)心而說出錯(cuò)誤的東西。確實(shí)也有這樣的情況，好的記法能給人提供新的見識，幫助我們解決看起來非常的問題，甚至引導(dǎo)我們得出新的發(fā)現(xiàn)。小語言是指那些針對較窄的領(lǐng)域而使用的特定記法，它們不僅提供了某種好界面，還能print的格式控制序列是一個(gè)很好的例子：格式串里的每個(gè)%標(biāo)記著一個(gè)位置，要求在這里插入printf省缺的標(biāo)志或域?qū)捳f明之后，最后一個(gè)字符指明了所要求的參數(shù)類型。這種記法非常緊湊，既直觀又容易書寫，實(shí)現(xiàn)起來也很方便。作為其替代物的 C++的iostream和Java的java.io看起來更笨拙，究其原因，雖然它們擴(kuò)充到了用戶定義類型，提供了類型檢查，但卻沒能提供一種特殊的記法。也有些非標(biāo)準(zhǔn)的printf實(shí)現(xiàn)，它們允許人們在內(nèi)部功能之外增加自己的方式。如果你使用其他數(shù)據(jù)類型，經(jīng)常要做它們的輸出轉(zhuǎn)換，有這種功能就非常方便。例如，一個(gè)編譯程序可能想用%L輸出行號和文件名；一個(gè)圖形系統(tǒng)可能用%P表示點(diǎn)，而用%R表示矩形。在第4章里我們看到為提取價(jià)格行情而設(shè)的字母數(shù)字的神秘序列，采用的也是類似想法，是為編排的組合而提供一種緊湊記法。現(xiàn)在我們在C和C++里做些類似的例子。假設(shè)我們需要從一個(gè)系統(tǒng)向另一個(gè)系統(tǒng)傳送一種8章我們已經(jīng)了解到，最清晰的一種解法可能就是把數(shù)據(jù)包轉(zhuǎn)換為正文表示。當(dāng)然，標(biāo)準(zhǔn)網(wǎng)絡(luò)規(guī)程所使用的多半是二進(jìn)制格式，為的是效率或者數(shù)據(jù)規(guī)?！，F(xiàn)在的問題是：應(yīng)該如何去寫處理數(shù)據(jù)包的代碼，使它能夠可移植、高效率，而且又很容易使用？為使這個(gè)討論更實(shí)在些，設(shè)想我們在系統(tǒng)間傳遞的是包含8位、16位和32位數(shù)據(jù)項(xiàng)的包。ANSIC，8位數(shù)據(jù)總可以在char里，16位可以放進(jìn)short，而32位放進(jìn)long，因此我們就用這些數(shù)據(jù)類型表示有關(guān)的值。實(shí)際中可能存在許多不同種類的包。例如，在第一種21字節(jié)的值，以及一個(gè)4字節(jié)的數(shù)據(jù)項(xiàng)：對于實(shí)際規(guī)程，需要成打的這種例程，它們都是某個(gè)東西的一種變形。利用處理基本類型(如short、long等)的宏或者函數(shù)可以簡化這些例程。但是，即使是按這種方式去做，這么多重復(fù)性代碼也是很容易寫錯(cuò)的。它們既難閱讀，也難進(jìn)行。這些代碼的內(nèi)在重復(fù)性實(shí)際上提醒了我們，記法可能會有所幫助。我們可以從printf用有關(guān)的想法，定義一個(gè)小語言，使每種包在這里都可以用一個(gè)簡潔的串描述，用這個(gè)串刻畫數(shù)據(jù)包的編排形式。包中連續(xù)的各個(gè)元素用編碼表示，用c表示8s表示16第第9 l表示32第一個(gè)包()在實(shí)踐中，數(shù)據(jù)包開始處的信息可以告訴接受方怎樣對其他部分進(jìn) 接受方讀這種包，提取其第一個(gè)字節(jié)，并依據(jù)它對包的其余部 下面是packbuf中。我 就像sprintf、strcpy及其他類似函數(shù)一樣，pack而言是足夠大的，調(diào)用它的程序必須保證這個(gè)條件。這里也不企圖去檢查格式與參數(shù)表之間不匹配的情況。這個(gè)pack函數(shù)使用了stdarg.h頭文件的功能，比第4章的eprintf用得。利用va_arg順序地提取各個(gè)參數(shù)：va_arg的第一個(gè)參數(shù)是va_list類型的變量，必須調(diào)用va_start對它預(yù)先做設(shè)置；va_arg的第二個(gè)參數(shù)是函數(shù)參數(shù)的類型(這也是為什么va_arg是宏，而不是函數(shù)的根本原因)。在處理完成后，應(yīng)該調(diào)用va_end。雖然‘cs’對應(yīng)的參數(shù)分別是char和short值，這里必須用int方式提取它們，原因在于char和short是用函數(shù)參數(shù)表最后的...表示的，在這種情況下，C語言將自動(dòng)把它們提升到int。開啟數(shù)據(jù)包的工作也可以同樣處理：不是為敲開每種數(shù)據(jù)包格式寫一段單獨(dú)代碼，而是寫一個(gè)帶有格式描述的unpack。這種做法把所有數(shù)據(jù)變換都集中到了一個(gè)地方：第9 像scanfunpack也必須給它的調(diào)用者返回多個(gè)值，因此它的參數(shù)是那些指向準(zhǔn)備存儲結(jié)果的變量的指針。函數(shù)返回?cái)?shù)據(jù)包的字節(jié)數(shù)，可以用于錯(cuò)誤檢查。由于所有值都是無符號的，而且我們堅(jiān)持不超出ANSIC對各種數(shù)據(jù)類型定義的大小，上面這些代碼總能以可移植的方式傳遞數(shù)據(jù)，甚至在那些具有不同大小的short和long的機(jī)器之間。例如，只要使用pack的程序不試圖把32位無法表示的值當(dāng)作long傳出去，傳遞的值就一定能正確接收。如果它這樣做了，那么實(shí)際傳送的將是數(shù)據(jù)的低32位。如果真的需要傳要調(diào)用unpack_type2，必須先確認(rèn)遇到的正是一個(gè)類型2的數(shù)據(jù)包，這意味著在接收程序以這種方式做程序設(shè)計(jì)也可能拖得很長。實(shí)際上有一種緊湊寫法，那就是定義一個(gè)函數(shù)指針的表，其中各個(gè)項(xiàng)是所有的開包函數(shù)，以數(shù)據(jù)包的類型編號作為下標(biāo)：表中的每個(gè)函數(shù)處理一種數(shù)據(jù)包，檢查結(jié)果，并啟動(dòng)對包的下一步處理過程。有了這個(gè)表之后，接收程序的工作就非常簡單了：這樣，每種數(shù)據(jù)包的處理代碼都非常緊湊，而且只寫在一個(gè)地方，很容易。這也使接收程序基本上獨(dú)立于傳輸規(guī)程，同時(shí)又是清晰和快速的。上面的例子來源于為實(shí)現(xiàn)某個(gè)產(chǎn)品網(wǎng)絡(luò)規(guī)程而寫的實(shí)際代碼。當(dāng)作者認(rèn)識到這種方式能工作之后，數(shù)千行重復(fù)的、充滿錯(cuò)誤的代碼被縮減成幾百行非常容易的代碼。記法消解的力量實(shí)在太大了。 練習(xí)9-2擴(kuò)展pac和unpack，使它們能處理字符串。一個(gè)可能的方式是在格式串里包含有關(guān)字符串長度的描述。擴(kuò)充函數(shù)，使它們能利用計(jì)數(shù)值處理重復(fù)的數(shù)據(jù)項(xiàng)。這與字符串的格式編碼方式又會有什么相互影響？練習(xí)9- 上面C程序里的函數(shù)指針表是C++虛函數(shù)機(jī)制 。在C++里重寫pack++練習(xí)9-4 寫一個(gè)printf令行版本，它按第一個(gè)參數(shù)指明的格式，打印其第二個(gè)及后面練習(xí)9-5 寫一個(gè)程序，它應(yīng)能實(shí)現(xiàn)電子表格程序或者Java的DecimalFormat格式規(guī)范，能按照模式顯示數(shù)值。模式里指明必的或可選的數(shù)、小數(shù)點(diǎn)和逗號的位置等等。作為明，下面的格式：描述的是有兩個(gè)小數(shù)位的數(shù)，小數(shù)點(diǎn)左邊至少有一個(gè)數(shù)字，在千位數(shù)字后面有一逗號，這里12345.67將被表示為12,345.67，而.4將表示為____0.40(這里的下劃線表示的是實(shí)際空格)。完全的規(guī)范請參看DecimalFormat的定義，或者某種電子表格程序。pack和unpack的格式描述串是非常簡單的記法，它們可用于定義數(shù)據(jù)包的編排形式。我們的下一論題是一種稍微復(fù)雜一點(diǎn)，但是更具表達(dá)能力的記法，正則表達(dá)式，它能夠描述正文的各種模式。我們已經(jīng)在本書中許多地方零星地用過正則表達(dá)式，但還沒有給它準(zhǔn)確的定義。正則表達(dá)式是我們很熟悉的東西，不需要多少解釋也能理解。雖然正則表達(dá)式在Unix程序設(shè)計(jì)環(huán)境里隨處可見，但在其他的系統(tǒng)里使用得卻沒有這么廣泛，因此，在這一節(jié)里，我們想顯示正則表達(dá)式的某些?？赡苣闶诸^沒有正則表達(dá)式函數(shù)庫，我們也要在這里給第9 正則表達(dá)式有多種不同的風(fēng)格，但它們在本質(zhì)上都是一樣的，是一種描述文字字符模式(如數(shù)字、字母)而提供的縮寫形式等等。人們最熟悉的一個(gè)例子就是所謂“通配符”，它用在命令處理器或者外殼中，用于描述被配的典用令*：用的是一個(gè)模式，該模式將與一些文件相匹配，只要文件名是以“.exe”結(jié)尾的某個(gè)字符串。對于這種模式的作用，不同系統(tǒng)之間也可能有細(xì)微差別，程序與程序間也可能這樣，這也不足為奇。對于正則表達(dá)式，不同程序的處理確實(shí)存在差別，這可能使人認(rèn)為它不過是某種信手拈來的東西。實(shí)際上，正則表達(dá)式也是一種語言，在語言中所有能說的東西都有嚴(yán)格的意義。進(jìn)一步說，正則表達(dá)式的正確實(shí)現(xiàn)的運(yùn)行速度很快。理論和工程實(shí)踐的結(jié)合方式不同有可能造成很大的差異，第2章里提過這方面的例子，講過特殊算法的作用。一個(gè)正則表達(dá)式本身也是一個(gè)字符序列，它定義了一集能與之匹配的字符串。大部分字符只是簡單地與相同字符匹配，例如正則表達(dá)式abc將匹配同樣的字符序列，無論它出現(xiàn)在什么地方。在這里還有幾個(gè)元字符(metacharacter)Unix通行的正則表達(dá)式中，字符^$^x只能與位于字符串開始處的xx$只能匹配結(jié)尾的x，^x$x，而^$只能匹配空串。字符“.”能與任意字符匹配。所以，模式x.y能匹配xay、x2y等等，但它不能匹配或xaby。顯然^.$寫在方括號[]里的一組字符能與這組字符中的任一個(gè)相匹配。這樣[ ]能與這些就是基本構(gòu)件，對它們可以用括號結(jié)成組，用|表示兩個(gè)里面選一個(gè)，用表示零次或+表示一次或多次出現(xiàn)，而本身，而。最有名的正則表達(dá)式工具就是前面已經(jīng)多次提到過的grepgrep將一個(gè)正則表達(dá)式作用于輸入的每一行，打印出所有包含匹配字符串的行。這是一個(gè)非常簡單的規(guī)范，但是，借助于正則表達(dá)式的，它能夠gre參數(shù)的那些正則表達(dá)式，其語法形式與用于表示文件名集合的通配符差別很大，這種差異正反映出它們的不同用途。哪些文件里用到類加上各種標(biāo)志開關(guān)，如打印匹配行的行號、對匹配計(jì)數(shù)、做區(qū)分大小寫的匹配、在相反的意義下工作(選擇那些不匹配的行)以及這些基本想法的許多其他變形，grep被使用得如此廣泛，以至它已經(jīng)成為基于工具的程序設(shè)計(jì)的典型實(shí)例。grep或者它的等價(jià)物。有的系統(tǒng)提供了一個(gè)正則表達(dá)式庫，通常稱為regex或regexpgrep版本。如果這些都沒有，要實(shí)現(xiàn)正則表達(dá)式的一個(gè)適當(dāng)子集也不是件難事。下面我們要給出正則表達(dá)式的一個(gè)實(shí)現(xiàn)，同時(shí)給出一個(gè)grep^$和，用表示位于讓我們從匹配函數(shù)本身入手。這個(gè)函數(shù)的工作就是確定一個(gè)正文串的什么地方與一個(gè)正則表達(dá)式匹配：如果正則表達(dá)式的開頭是^，那么正文必須從起始處與表達(dá)式的其余部分匹配。否則，我們就沿著串走下去，用matchhere看正文是否能在某個(gè)位置上匹配。一旦發(fā)現(xiàn)了匹配，工作就完成了。注意這里do-while的使用，有些表達(dá)式能與空字符串匹配($能夠在字符串的末.*0個(gè))。所以，即使遇到了空字符串，我們也還需要調(diào)用matchhere。如果正則表達(dá)式為空，就說明我們已經(jīng)到達(dá)了它的末端，因此已經(jīng)發(fā)現(xiàn)了一個(gè)匹配；如果表達(dá)式的最后是$，匹配成功的條件是正文也到達(dá)了末尾；如果表達(dá)式以一個(gè)圓點(diǎn)開始，那么它能與任何字符匹配。否則表達(dá)式一定是以某個(gè)普通字符開頭，它只能與同樣的字符匹配。這里把出現(xiàn)在正則表達(dá)式中間的^或$注意，當(dāng)matchhere第9 *。這時(shí)我們調(diào)用matchstar，其第一個(gè)參數(shù)是星號的參數(shù)(在上面的例子里是x)，隨后的參數(shù)是位在這里又遇到了do-hle。之所以這樣寫，原因同樣是*也能與0個(gè)字符匹配。在這個(gè)循環(huán)里，檢查正文能否與表達(dá)式的剩余部分匹配，只要被檢查正文的第一個(gè)字符與星號的參數(shù)匹配，這是一段完全可以接受的、并不太復(fù)雜的實(shí)現(xiàn)程序。它也說明正則表達(dá)式不需要高級的技術(shù)就可以投入使用。grep的版本，它調(diào)令C程序在成功結(jié)束時(shí)返回一個(gè)0值，對各種失敗都返回非0序grep里，就像一般的Unix版本一樣，成功被定義為至少發(fā)現(xiàn)了一個(gè)匹配行，如果存在匹配就返回012(通過eprintf)。這些返回函數(shù)grep掃描一個(gè)文件，對其中的每個(gè)行調(diào)用主程序在無法打開文件時(shí)并不直接結(jié)束。這個(gè)設(shè)計(jì)是一種選擇，考慮到人們經(jīng)常會做的某些事，如：既而發(fā)現(xiàn) 下的某個(gè)文件無法打開。讓grep在報(bào)告了問題后繼續(xù)工作下去可能是更合適的，這里不應(yīng)該立即放棄，因?yàn)槟菢幼鼍蜁仁褂脩粢粋€(gè)個(gè)地輸入文件名，以回避那些出了問題，gre在一般情況下打印出文件名和匹配的行，但當(dāng)它讀標(biāo)準(zhǔn)輸文件時(shí)就不輸出文件名。這種設(shè)計(jì)看起來好像很奇怪，其實(shí)它反映的是實(shí)際使用中的一種習(xí)慣，gre的工作常常是做選擇，附加上的文件名就將成為贅物。如果用它檢索許多文件，人們要做的通常是發(fā)現(xiàn)某些東西的所有出現(xiàn)，這時(shí)文件名就成為很有幫助的東西了。請比較：和這些想法已經(jīng)接觸到grep為什么變得如此大眾化的基礎(chǔ)，它也說明了另一個(gè)問題：好的記法只有與人們的工程經(jīng)驗(yàn)相結(jié)合，才能產(chǎn)生出自然而又有效的工具。我們的matchgrep而言，這是一種很好的默認(rèn)行(搜索和替換)，實(shí)現(xiàn)最左最長的匹配就更是合適的。例如，給定的文本是“aaaaaa*能與文本開始的空字符串匹配，但是，看起來最好還是讓它匹配所有的五個(gè)amatch能找到最左最長的匹配串，matchstar的能與帶星號字符匹配的串，只有在串的剩余部分不能與模式的剩余部分匹配時(shí)才往后退。第9 對于grep而言，發(fā)現(xiàn)的匹配是什么并不重要，因?yàn)樗恍枰獧z查匹配的存在性，并打印出相應(yīng)的整個(gè)行。由于最左最長匹配需要做許多附加工作，這對grep而言并不是必須的，但是對于實(shí)現(xiàn)一個(gè)替換操作而言，這種功能就是最基本的了。如果不考慮正則表達(dá)式的形式，我們的grep還是能和系統(tǒng)提供的東西相比美的。不過，這里也存在表達(dá)式，它們可能導(dǎo)致指數(shù)式的行為。例如在用模式a*a*a*a*a*b去匹配輸入串a(chǎn)aaaaaaaac的時(shí)候。實(shí)際上，指數(shù)式行為也出現(xiàn)在某些商品的實(shí)現(xiàn)中。在Unix里有一個(gè)grep的變體，名字是egrep，它使用一種非常復(fù)雜的匹配算法，在部分匹配失敗后它能夠避免進(jìn)行回溯，這樣就能保證線性的性能。怎樣使match能處理所有的正則表達(dá)式？為此就必須包括：像[a-zA-Z]那樣的字符組與各個(gè)字母的匹配，能夠把元字符引起來(例如需要查找正文中的一個(gè)圓點(diǎn))以及選擇(abc或def)等。要做的第一步，應(yīng)該是把模式翻譯到某種表示形式，使它很容易查看。在與一個(gè)字符做比較時(shí)，如果每次都要檢查整個(gè)字符組，是非常費(fèi)時(shí)間的，用一個(gè)基于位向量的預(yù)先做出的表示形式，就能很有效地實(shí)現(xiàn)字符組。對于完全的正則表達(dá)式，帶有括號和選擇，實(shí)現(xiàn)起來必定更加復(fù)雜。在本章后面部分要講到的某些技術(shù)可以用在這里。練習(xí)9-6match的執(zhí)行性能與strstr練習(xí)9-7寫一個(gè)非遞歸的matchhere練習(xí)98給grep-v-i表示對字母做區(qū)分大小寫的匹配，-n表示在輸出中指明行號。行號應(yīng)該如何輸出？它們是否應(yīng)該與被匹配的練習(xí)9-9擴(kuò)充match，增加+(一個(gè)或多個(gè))和?(0個(gè)或一個(gè))。模式a+bb?應(yīng)該匹配一個(gè)或多練習(xí)9-10當(dāng)^和$不出現(xiàn)在表達(dá)式的開頭或結(jié)尾，或者*不是緊跟在普通文字字符或圓點(diǎn)的后面時(shí)，目前的match實(shí)現(xiàn)都不使用它們作為元字符的特殊意義。一種更習(xí)慣的實(shí)現(xiàn)是在元字符前放一個(gè)反斜線符號，表示將它引起來。修改mtc，使之能以這種方式處理反斜線符號。 符匹配。要使字符組使用更方便，還應(yīng)該再加上范圍描述，例如[a-z]能匹配所有的小寫字母；練習(xí)9-12改造match，使用最左最長匹配的matchstar版本；再修改它，使它能返回被匹配字符串的開始和結(jié)束位置。用這個(gè)match寫一個(gè)程序gres，它與grep類似，但打印的是練習(xí)9-13修改match和grepUnicode字符的UTF-8串。由于UTF-8和Unicode都是ASCII的超集，這種修改是向上兼容的。除了被檢索的正文，正則表達(dá)式本身也需要改造，使之能正確使用UTF-8。現(xiàn)在字符組又該如何實(shí)現(xiàn)呢？練習(xí)9-14寫一個(gè)正則表達(dá)式的自動(dòng)測試程序，它應(yīng)能生成測試表達(dá)式和被檢索的測試串。wk是另一種可編程工具，它帶有一種很小的、特定的模式匹配語言，主要用于對輸入3wk程序能自動(dòng)讀入輸入文件，把每個(gè)行$1到$NF，這里的NF是一行中域的個(gè)數(shù)。通過對許多常見工作提供相關(guān)的默認(rèn)行為方式，使人可以用wk做出許多很有用的單行程序。例如，下面就是一個(gè)完整的wk程序，它打印各個(gè)輸入行里的詞，一個(gè)詞一行。再看看另一方向的東西。下面是fmt的一個(gè)實(shí)現(xiàn)，該程序用詞填起每個(gè)輸出行，每行不超過60個(gè)字符?？招袑?dǎo)致分段。第9 我們常用fmt對電子郵件或其他短文件重新做分段整理。我們也用它對第3章Markov程序的輸可編程工具常常于一個(gè)小語言，該語言可能是為在某個(gè)較窄領(lǐng)域里自然地表達(dá)問題的解而設(shè)計(jì)的。Unix工具eqneq的輸入語言接近數(shù)學(xué)家讀數(shù)學(xué)的表達(dá)方式：寫為piover2。TEX采用了類似形式，它對上面的記法是\pi\over2。對于你要去解決的問題，如果存在一種自然的或人們熟悉的記法，那么就應(yīng)該使用它，或者是修改它，不要總是從頭開始。wk是由另一個(gè)程序獲得的靈感，該程序利用正則表達(dá)式在流通記錄中標(biāo)記出反常wk包含了變量、表達(dá)式和循環(huán)等等，這使它成了一個(gè)真正的程序設(shè)計(jì)語言。Perl和cl在開始設(shè)計(jì)時(shí)，也是為了將小語言的方便性和表達(dá)能力與大語言的結(jié)合到一起。它們都是真正的通用程序設(shè)計(jì)語言，雖然最常見的應(yīng)用是處理正文。這類工具的通用名稱是語言，因?yàn)樗鼈兪菑脑缙诹罱忉屍靼l(fā)展起來的，其可編程能力受到一定限制，只能執(zhí)行包裝起來的程序。語言創(chuàng)造性地使用正則表達(dá)式，不僅僅是式匹配—即識別某種特定模式的存在—也用于標(biāo)識需要做變換的正文區(qū)域。在下面的cl程序里，兩個(gè)regsub(regularexpressionubstitution，正則表達(dá)式代換)種這是第4章給出的行情提取程序的一個(gè)擴(kuò)充，它按給定的第一個(gè)參數(shù)值取得URLhttp://(如果存在的話)；第二個(gè)替換把遇到的第一個(gè)/換成空格，這就把參數(shù)分成了兩個(gè)域。linde命令從串里取出第一個(gè)域(用下標(biāo)0)。括在[]里面的正文將被作為cl$x用變量x在典型的情況下，這個(gè)將產(chǎn)生大量輸出，其中許多是由<和>括起來的HTML標(biāo)志。用Perl做正文替換非常方便，所以我們的下一個(gè)工具是個(gè)Perl，它利用正則表達(dá)式和替換，去在字符串的正文里，把與正則表達(dá)式匹配的(最左最長)串替換為，最后的g符序列\(zhòng)s是一個(gè)縮寫形式，表示所有的空白字符(空格、制表符、換行一類東西)；\n表示換行字符。串“&;”是HTML里的一個(gè)字符，就像第2章說明的那些，它定義一個(gè)不允許斷把所有這些東西放到一起，就構(gòu)成了一個(gè)能力不強(qiáng)但也可以工作的網(wǎng)絡(luò)瀏覽器，實(shí)現(xiàn)它只要寫一個(gè)單行的外殼程序：它能提取網(wǎng)頁，丟掉其中所有的控制和格式信息，然后按照自己的規(guī)矩重新進(jìn)行格式化。這是從網(wǎng)絡(luò)上快速獲取頁面的一種途徑。注意，在這里我們以串聯(lián)方式同時(shí)使用了多種語言：cl、Perl和wk，每種語言都有特別適合的工作，在每種語言里都有正則表達(dá)式。記法的就在于對每個(gè)問題都可能有最合適的工具。用cl完成通過網(wǎng)絡(luò)獲取正文的工作十分方便；Perl和wk適合做正文的編輯和格式化；當(dāng)然，還有正則表達(dá)式，它最適合用來刻畫作為查找和修改對象的正文片段。這些語言放在一起，其遠(yuǎn)大于它們中的任何一個(gè)。把工作分解成片段有時(shí)是很值得做的，如果這樣做有可能使你得益于某些正確的記法。一個(gè)程序怎樣才能從它的源程序代碼形式進(jìn)入執(zhí)行？如果這個(gè)語言足夠簡單，就像出現(xiàn)在printf常容易，可以立即就開始做。在設(shè)置方面的時(shí)間開銷和執(zhí)行深度之間有一種此消彼長的關(guān)系。如果語言更復(fù)雜些，人們通常就會希望做一些轉(zhuǎn)換，把源代碼轉(zhuǎn)換為一種對執(zhí)行而言既方便又有效的內(nèi)部表示形式。處理原來的源代碼需要用一些時(shí)間，但這可以從隨后的快速執(zhí)行中得到回報(bào)。有些程序里綜合了轉(zhuǎn)換和執(zhí)行的功能，它們能讀入源代碼正文，對其做轉(zhuǎn)換后運(yùn)行之，這種程序稱作“解wk和Perl是解釋性的，許多其他語言和語言也是這樣。也存在著另一種組合方式，這就是我們在本節(jié)里準(zhǔn)備研究的：把程序編譯成某種計(jì)算機(jī)(虛擬機(jī))的指令，而這種虛擬機(jī)可以用任何實(shí)際計(jì)算機(jī)進(jìn)行模擬。虛擬機(jī)綜合了普通解釋和編譯的許多優(yōu)點(diǎn)。如果語言很簡單，要弄清程序的結(jié)構(gòu)并把它轉(zhuǎn)換為某種內(nèi)部形式，并不需要做多少處理工作。當(dāng)然，如果語言里存在著一些復(fù)雜性—有說明、嵌套結(jié)構(gòu)、遞歸定義的語句或表達(dá)式、—分析程序(parser)常常是借助于某個(gè)分析程序自動(dòng)寫出來的，這種工具也被稱為編yacc或bison(語言的語法)出發(fā)，轉(zhuǎn)換出(典型情況是)一個(gè)C或C程序。這個(gè)程序經(jīng)過編譯后，就能把該語言的語句轉(zhuǎn)換到對應(yīng)的內(nèi)部形式。當(dāng)然，由語法描述出發(fā)能生成一個(gè)剖析程序，這也是好記法的一個(gè)例證。由分析程序生成的表示形式通常是樹，其內(nèi)部結(jié)點(diǎn)包含著運(yùn)算符號，葉結(jié)點(diǎn)包含的是運(yùn)算對象。下面這個(gè)語句：第9 可能產(chǎn)生下面這個(gè)分析樹(或稱語法樹一旦這種樹構(gòu)造好了，我們就有許多可能的方法來處理它。最直接的方法(也是wk所采用的)是直接在樹中運(yùn)動(dòng)，并在這個(gè)過程中求出各個(gè)結(jié)點(diǎn)的值。要完成對這種整數(shù)表達(dá)式語言的求值過程，下面給出一個(gè)簡化的程序版本，它采用后序遍歷方式：前幾個(gè)分情況完成的是對最簡單的表達(dá)式求值，例如那些常量和值等；隨后的情況對算術(shù)表達(dá)式求值；其他的可能是做另一些特殊處理，如條件語句和循環(huán)等。要實(shí)現(xiàn)這些控制結(jié)構(gòu)，樹中還需要附加其他信息，以表示控制流。這里都沒有給出來。就像面處理pack和unpack那樣，我們也可以用一個(gè)函數(shù)指針的表取代這里顯示的開關(guān)語句。各運(yùn)算符對應(yīng)的函數(shù)和上面開關(guān)語句里的差不多：求值過程以運(yùn)算符為指標(biāo)，從表里得到函數(shù)指針，隨之去調(diào)用正確的函數(shù)。下面的版本將遞歸地調(diào)用其他函數(shù)。上面這兩個(gè)eval版本都是遞歸的。存在著一些去除遞歸的方法，包括一種稱為線索化代碼的巧妙技術(shù)，它能使調(diào)用棧完全癟下來。要去掉所有遞歸，最巧妙的方法是把有關(guān)函數(shù)存入一個(gè)數(shù)組，然后線性地穿過這個(gè)數(shù)組，執(zhí)行對應(yīng)的程序。這個(gè)數(shù)組實(shí)際上已經(jīng)變成了由一個(gè)小的特殊機(jī)器執(zhí)行的指令序列。我們?nèi)匀恍枰靡粋€(gè)棧來表示計(jì)算過程中部分計(jì)算出的結(jié)果。這時(shí)函數(shù)的形式也要做些改變，不過這種轉(zhuǎn)換是很容易的。這樣，我們已經(jīng)發(fā)明了一種堆棧機(jī)器，它的指令是一些小函數(shù)，而運(yùn)算對象都存在一個(gè)獨(dú)立的運(yùn)算對象棧里。這并不是一個(gè)真正的機(jī)器，但我們可以像使用真的機(jī)器一樣為它編程，同時(shí)也很容易把它實(shí)現(xiàn)為一個(gè)解釋器。不再需要通過在樹上的運(yùn)動(dòng)，對樹進(jìn)行求值，而是生成一個(gè)執(zhí)行這個(gè)程序的函數(shù)數(shù)組。數(shù)組里也應(yīng)該包含指令所使用的數(shù)據(jù)值，例如常數(shù)和變量(符號)等，因此這個(gè)數(shù)組的元第第9 下面是函數(shù)generate，它生成一些函數(shù)指針，并把它們放入以這些東西為內(nèi)容的數(shù)組處理語句a=max(b,c)在我們發(fā)明的這個(gè)堆棧機(jī)器里，上述循環(huán)實(shí)際上是以軟件方式模擬著真實(shí)計(jì)算機(jī)的硬件所做的事情。下面是幾個(gè)有代表性的運(yùn)算函數(shù)：檢查條件、分支和循環(huán)的執(zhí)行等，在運(yùn)算符函數(shù)里表現(xiàn)為直接修改程序計(jì)數(shù)器，這樣做goto運(yùn)算符就是直接設(shè)置pcpc。code數(shù)組是解釋器內(nèi)部的東西。當(dāng)然，我們也可以設(shè)想把生成出來的程序存入一個(gè)文件。如果直接把函數(shù)的地址寫出去，得的結(jié)果將是不移植的和脆弱的。我們應(yīng)該換式，1000表示addo，用1001表示pushop等等。在重新讀入程序準(zhǔn)備執(zhí)行時(shí)，再把這些常數(shù)翻譯回函數(shù)指針。如果我們查看由上面的過程產(chǎn)生的文件，它們就像是虛擬機(jī)的指令流，虛擬機(jī)的指令實(shí)現(xiàn)的是我們小語言的基本運(yùn)算符，而generate函數(shù)實(shí)際上就是個(gè)編譯程序，它把我們的語言翻譯到對應(yīng)的機(jī)器。虛擬機(jī)是一個(gè)可愛的歷史悠久的想法，最近，由于Java和Java虛擬機(jī)(JVM)的出現(xiàn)，這種想法又變得時(shí)髦起來。要從高級語言程序產(chǎn)生出一種可移植并且高效的表示形式，虛擬機(jī)方法實(shí)際上了一條康莊大道。函數(shù)generate最值得注意的地方，或許就在于它是一個(gè)寫程序的程序：它的輸出是另一個(gè)(虛擬)機(jī)器可以執(zhí)行的指令序列。編譯程序每時(shí)每刻都在做這件事：把源代碼翻譯成機(jī)器指令，所以這種想法是人人皆知的。在實(shí)踐里，寫程序的程序可能以許多不同的形式出現(xiàn)。一個(gè)最常見的例子是網(wǎng)頁TL的動(dòng)態(tài)生成。T第9 它還可以包含JavaScript代碼。網(wǎng)頁常常是由Perl或者C(例如，某些查詢結(jié)果或者定向)根據(jù)外來需求確定。我們對這本書里的各種圖形、表格、數(shù)學(xué)表達(dá)式以及索引等使用了多種特殊的語言。作為另一個(gè)例子，PostScript也是一種程序設(shè)計(jì)語言，它可以由文字處理程序、畫圖程序和許許多多其他程序生成。在處理的最后階段，本書就被表示為一個(gè)大約有57000行的PostScript一個(gè)文檔是一個(gè)靜態(tài)的程序，使用某個(gè)程序語言作為記法，表達(dá)各種問題領(lǐng)域是一種非常有力量的思想。許多年以前，程序員就夢想著有朝一日計(jì)算機(jī)能幫他們寫所有的程序，當(dāng)然這可能都只是一個(gè)夢。但是，今天的計(jì)算機(jī)已經(jīng)在日復(fù)一日地為我們寫程序，經(jīng)常是在寫那些我們原來從未想到還可能表達(dá)為程序的東西。最常見的寫程序的程序是編譯器，它能把高級語言程序翻譯成機(jī)器代碼。然而，把代碼翻譯到主流程序設(shè)計(jì)語言常常也很有用。面的章節(jié)里，我們曾提到的分析程序能C程序。C常常被作為一種“高級的匯編語言”使用。有些通用的高級語言(例如Modula-3和C++)的第一個(gè)編譯程序產(chǎn)生的就是代碼，這種代碼隨后用標(biāo)準(zhǔn)C編譯系統(tǒng)編譯處理。這種方式有不少優(yōu)點(diǎn)，包括效率—因?yàn)檫@些程序原則上可以運(yùn)行得像C程序一樣快，可移植性—C的系統(tǒng)上。這大大促進(jìn)了這些語言的早期。作為另一個(gè)例子，VisualBasic的圖形界面生成一組VisualBasic賦值語句，完成用戶通過鼠標(biāo)在屏幕上選擇的那些對象的初始化工作。許多其他語言也有“可視化的”開發(fā)環(huán)境和盡管各種程序的如此強(qiáng)大，盡管有這么多極好的例子，記法問題還是沒有得到它應(yīng)有的尊重，仍然很少被程序員們使用。實(shí)際中確實(shí)存在著大量的用程序生成小規(guī)模代碼的機(jī)會，所以，你自己應(yīng)該學(xué)會從這里獲得一些益處。下面是生成或者Cn9操作系統(tǒng)由一個(gè)頭文件生成它的錯(cuò)誤信息，該文件里包含一些名字和注釋；這些注這方有多點(diǎn)先，enum值和它們所表示的字符串之間的關(guān)系在上自成文檔，很容易做到對自然語言的獨(dú)立性。此外，信息只出現(xiàn)一次，只有“一個(gè)真理點(diǎn)”，所有其他代碼都由此生成。這樣，如果需要做更新，那么就只有一個(gè)地方需要考慮。如果這些信息出現(xiàn)在許多地方，很難避免在某些時(shí)候它們之間失去同步性。最后，我們很容易對.c文件做出適當(dāng)安排，使得在這個(gè)頭文件改變時(shí)，所有有關(guān)的文件都重新建立和重新編譯。當(dāng)某個(gè)錯(cuò)誤信息必須改變時(shí)，需要做的所有事情就是修改這個(gè)頭文件，并重新編譯整個(gè)操作系統(tǒng)。這樣所有信息都能得到更新。正則表達(dá)式又參與了這里的行動(dòng)。所有第一個(gè)域是標(biāo)識符后跟著逗號的東西都被選中，第一個(gè)代換刪掉直到注釋里第一個(gè)非空字符之前的所有東西，第二個(gè)代換刪去注釋結(jié)尾和它前面的所有空格。作為編譯系統(tǒng)測試工作的一部分，AndyKoenig開發(fā)了一種寫C代碼的方便方法，以檢查如果用我們的C++編譯系統(tǒng)處理到第二個(gè)測試實(shí)例，它打印出的正是我們所期望的，能與對每個(gè)這種代碼片段都提交給編譯系統(tǒng)，然后將產(chǎn)生的輸出與所期望的診斷信息做比較，這個(gè)過程通過s和wk程序的結(jié)合來管理，出現(xiàn)時(shí)將指明是哪個(gè)測試實(shí)例使編譯系統(tǒng)的輸出與期望的不同。由于在注釋里用的是正則表達(dá)式，輸出可以有些自由度，根據(jù)情況不同，可以把它們寫成或多或少具有某些寬容性。使用帶語義的注釋不是什么新想法，PostScript里就有這種東西。在PostScript第第9 盒(boundingbox)(liteprogramming)，就是說，把一個(gè)程序和它的文檔集成在一起。這樣，通過某種過程，其中的文檔可以按自然順序打印出來供人閱讀，另一個(gè)過程則以正確順序安排它去進(jìn)行編譯。 練習(xí)9-15有一個(gè)歷史很久遠(yuǎn)的有關(guān)計(jì)算的故事，要求寫出一個(gè)程序，執(zhí)行后恰好產(chǎn)生其自身原來的形式。這是用程序?qū)懗绦虻囊粋€(gè)非常特殊而又很巧妙的例子。請?jiān)谀阕约鹤钕矚g的語言里試一試?，F(xiàn)在向下降幾個(gè)層次，我們同樣也能寫這樣的宏，它們在編譯時(shí)能夠產(chǎn)生代碼。在這本書里我們始終在告誡讀者，應(yīng)該使用宏和條件編譯，因?yàn)樗鼈児膭?lì)的是一種破綻的程序設(shè)計(jì)風(fēng)格。但是，宏也確實(shí)有它自己的位置，有時(shí)正文替換恰恰就是問題的正確解決方法。這里有一個(gè)例子，是關(guān)于如何利用CC的宏預(yù)處理裝配起同樣風(fēng)格的重復(fù)出現(xiàn)的代碼片段。在第7章里我們提到過估計(jì)語言基本結(jié)構(gòu)速度的程序，它就利用了C的預(yù)處理功能，通過把具體代碼裝入一段框架，組裝起一大批測試?yán)?。有關(guān)測試的基本構(gòu)架是封裝起來的一段代碼，其中有一個(gè)循環(huán)。在循環(huán)開始時(shí)設(shè)置時(shí)鐘，隨后將代碼段運(yùn)行許多次，最后停下時(shí)鐘并報(bào)告結(jié)果。所有重復(fù)出現(xiàn)的代碼段都被包裹在幾個(gè)宏里面，實(shí)際被計(jì)時(shí)的代碼則被作為參數(shù)傳遞給宏?；镜暮昃哂腥缦滦问剑簩懺谧詈蟮姆葱本€符號使宏可以延伸到多行。這個(gè)宏將被用在“語句”里，應(yīng)用的形式大致是下面的樣子：宏處理功能也可以用于生成產(chǎn)品代碼。有一次，BartLocanthi作程序。這種操作被稱為bitblt或rasterop。要想把它們做得速度很快是十的，因Locanthi把所有組合情況歸結(jié)到一個(gè)循環(huán)，它可以獨(dú)立地進(jìn)行優(yōu)化。在此之后，他用宏替換構(gòu)造出每種情況，就像前面性能測試的例子那樣，然后把各種變形安排在一個(gè)大的開關(guān)語句里面。原始的源代碼只有幾百行，宏處理的結(jié)果就變成了數(shù)千行。這樣通過宏展開得到的代碼并不是最優(yōu)的，這是由于問題本身的復(fù)雜性。但是這種做法又非常實(shí)際，也很容易完成。另一方面，作為一段高性能代碼，它也具有相對的可移植性。 練習(xí)7-7要求寫一個(gè)程序去度量C++里的代價(jià)。使用本節(jié)想法重新練習(xí)9-17練習(xí)7-8要求做一個(gè)Java的代價(jià)模型，在Java中沒有宏的功能。我們可以通過另外寫一個(gè)程序的方式來解決這個(gè)問題，在這里可以采用你所選定的任何語言(或幾個(gè)語言)。令這個(gè)這幾節(jié)在談?wù)搶懗绦虻某绦?。面的所有例子里，生成出來的程序都具有源代碼的形式，它還需要經(jīng)過編譯或者解釋才能運(yùn)行。實(shí)際上也可能產(chǎn)生出能夠立即投入執(zhí)行的代碼，只要我們生成的不是源代而是機(jī)器指令這種做法通常被稱為“運(yùn)行中”的編譯，或者“即時(shí)”編譯。前一個(gè)詞出現(xiàn)得更早，而現(xiàn)在后一個(gè)詞卻更流行，包括該詞 (JustInime)的首字母縮詞JIT。雖然這樣編譯產(chǎn)生代碼必定是不可移植的—只能運(yùn)行在一種類型的處理器上—但它計(jì)算過程中必須求出c，將它除以2，用得到的結(jié)果與b比較，選出其中較大的一個(gè)。如果用本divo里對除零的檢查，因?yàn)?不是0，有關(guān)的檢查毫無意義。但是，無論確定采用什么樣的設(shè)計(jì)，我們在對虛擬機(jī)的實(shí)現(xiàn)0這也就是動(dòng)態(tài)代碼生成可以起作用的地方。如果直接從表達(dá)式出發(fā)構(gòu)造代碼，而不只是簡單地串起預(yù)先定義的一些操作，在那些已知除數(shù)不是零的地方，是完全可以避免再做除零檢查的。實(shí)際上還可以再前進(jìn)一步，如果整個(gè)表達(dá)式就是常數(shù)，例如max(3*3,4/2)，我們可以在產(chǎn)生代碼的過程中對它求一次值，然后直接用常數(shù)9取代它。如果表達(dá)式出現(xiàn)在一個(gè)循環(huán)里，那么循環(huán)的每次執(zhí)行都將節(jié)省時(shí)間。只要循環(huán)的次數(shù)足夠多，我們就能把為弄清表達(dá)式和生成代碼所花費(fèi)的額外時(shí)間都節(jié)省回來。這里的關(guān)鍵思想還是記法。記法給了我們一種表達(dá)問題的一般性方法，而這種記法的編譯程序可以針對特定計(jì)算的細(xì)節(jié)生成專門代碼。例如，在處理正則表達(dá)式的虛擬機(jī)里，我們最好有一個(gè)匹配文字型字符的運(yùn)算：當(dāng)我們?yōu)樘囟Ｊ缴纱a時(shí)，由于li l的值是固定的，例如就是‘x’，那么我們最好第9 與此同時(shí)，我們不希望為每個(gè)文字字符值預(yù)先定義一個(gè)特殊運(yùn)算，而是想把問題弄得更簡單些，只有在表達(dá)式實(shí)際需要的時(shí)候才生成這種代碼。把這個(gè)思想推廣到整個(gè)的運(yùn)算集合，就可以寫出一個(gè)運(yùn)行時(shí)的編譯器，它把當(dāng)時(shí)處理的正則表達(dá)式翻譯成一段為此表達(dá)式而特別優(yōu)化了的代碼。1967年，KenThompson在IBM7094機(jī)器上做正則表達(dá)式的實(shí)現(xiàn)時(shí)，所做的實(shí)際上就是這件事。他的程序?qū)Ρ磉_(dá)式里的生成一些小塊的二進(jìn)制7094代碼，再把它們串聯(lián)在一起，最后通過調(diào)用來運(yùn)行結(jié)果程序，就像調(diào)用普通函數(shù)一樣。類似技術(shù)也可以用到圖形系統(tǒng)里，創(chuàng)建一些屏幕更新的特定指令序列。由于在圖形處理中存在太多的特殊情況，與其事先把它們都寫出來，或在更一般的代碼中加入大量條件測試，還不如對每種實(shí)際發(fā)生的情況動(dòng)態(tài)地構(gòu)造相關(guān)代碼。后面這種方法更有效。如果要展示實(shí)際的運(yùn)行時(shí)編譯系統(tǒng)的構(gòu)造過程，就有可能使我們的討論涉及到過多的特定指令集合的細(xì)節(jié)。但是，顯示一下這種系統(tǒng)如何工作還是很值得的。在閱讀本節(jié)余下的部分時(shí)，你主要應(yīng)該了解其中的思想和見解，而不是具體的實(shí)現(xiàn)細(xì)節(jié)。要將這些代碼弄成運(yùn)行時(shí)編譯，須做一些修改。首先，cod數(shù)組將不再是函數(shù)指針的數(shù)組，而應(yīng)該是可執(zhí)行指令的數(shù)組。到底這些指令的類型是char或int或long，要看我們的編譯所面對的處理器的情況，這里假定它是int。在代碼生成之后，我們準(zhǔn)備像函數(shù)一樣調(diào)用它。這里將不再需要虛擬的程序計(jì)數(shù)器，因?yàn)樘幚砥鞅旧碛兴膱?zhí)行循環(huán)，它將為我們遍歷這些代碼，一旦計(jì)算完成，它就會返回，就像正常的函數(shù)一樣。此外，我們還可以有些選擇，是自己為機(jī)器一個(gè)運(yùn)算對象棧，還是直接使用處理器的堆棧。這兩種方法各有長短。在這里我們?nèi)匀皇褂靡粋€(gè)獨(dú)立的棧，以便把注意力集中到代碼本身的細(xì)節(jié)方面。現(xiàn)在的實(shí)現(xiàn)大致是這個(gè)樣子：必須做的?，F(xiàn)代計(jì)算機(jī)的速度非?？?，部分原因就在于它們擁有為指令和數(shù)據(jù)而使用的各種緩沖器，而且還有內(nèi)部的流水線，這使許多順序指令的執(zhí)行可以互相。緩存和流水線都期望遇到的指令流是靜態(tài)的。如果我們要求它執(zhí)行剛剛生成的那些代碼，處理器很可能會被搞糊涂。因此，在執(zhí)行新生成的代碼之前，CPU需要騰空其流水線，刷新其緩存。這些都是對具體機(jī)器有高度依賴性的操作，對各種特定類型的計(jì)算機(jī)，flushcaches的實(shí)現(xiàn)肯定是不同的。最值得注意的表達(dá)式是(void(*)(void))code，這是一個(gè)模子(Cast)，它把包含著新生成的指令序列的數(shù)組地址轉(zhuǎn)換成一個(gè)函數(shù)指針，通過它就可以像函數(shù)一樣調(diào)用這些代碼。從技術(shù)上看，生成代碼本身并沒有太大，但要想有效地完成這個(gè)工作還有許多工程性的事項(xiàng)。讓我們從某些基本構(gòu)件開始。和前面一樣，在編譯過程中需要code數(shù)組和它的一個(gè)下標(biāo)。為了簡單起見，這里把它們都定義為全局的，這也是前面一直采用的方式。此后，我們就可以寫一個(gè)編排指令的函數(shù)了：指令本身可以通過與具體處理器相關(guān)的宏或者小函數(shù)來定義，它們填充指令字中各個(gè)域，裝配起各種指令。假設(shè)我們有一個(gè)名為popreg的函數(shù)，它生成的代碼是從堆棧里彈出一個(gè)值，并將它存入處理器的寄存器；另一個(gè)函數(shù)叫pushreg，它生成的代碼從一個(gè)寄存器取出值，addop使用這些基本功能，它看起來大致是下面的樣子，(像ADDINST)或者其編排形式(定義有關(guān)格式的各種SHIFT位置)：cast，也