詞法分析器的面向?qū)ο箝_發(fā)

1、詞法分析器的面向?qū)ο笤O(shè)計(jì)摘要：編譯程序的開發(fā)和面向?qū)ο笏枷氲恼莆帐怯?jì)算機(jī)專業(yè)本科實(shí)踐教學(xué)的重要內(nèi)容之一。但是，將面向?qū)ο蟮能浖_發(fā)方法應(yīng)用到具體的軟件開發(fā)中就顯得較為抽象與困難，尤其是面向?qū)ο蟮木幾g程序的開發(fā)。本文將傳統(tǒng)的CRC建模方法加以改進(jìn)，提出利用CRCR卡（Class-Responsibility-Collaboration-Relationship，CRCR）進(jìn)行建模的過程。遵循面向?qū)ο箝_發(fā)的指導(dǎo)思想，由淺及深，逐層深入，將面向?qū)ο蟮拈_發(fā)具體化、明確化。最終得到面向?qū)ο蟮脑~法分析器的高層模型。使讀者更加清晰地理解了詞法分析過程以及對軟件開發(fā)中的面向?qū)ο蠓椒ń⑵湔w概念，并對面向?qū)ο?/p>

2、方法進(jìn)行軟件開發(fā)有較為全面與清晰的認(rèn)識。關(guān)鍵詞：面向?qū)ο?軟件開發(fā) 詞法分析器 CRC建模 編譯原理第一部分 面向?qū)ο蟮乃枷氲暮唵谓榻B首先我們將簡單介紹一下面向?qū)ο蟮乃枷搿Ｒ惶岬矫嫦驅(qū)ο笏枷?，我們首先想到的便是面向?qū)ο蟮乃拇筇匦裕撼橄蟆⒗^承、多態(tài)和封裝。首先介紹一下什么是封裝和數(shù)據(jù)隱藏。封裝，定義為對象同時(shí)包含屬性和行為。數(shù)據(jù)隱藏則是封裝的一個(gè)主要部分。而實(shí)現(xiàn)數(shù)據(jù)隱藏的主要途徑就是接口。那么什么是接口呢？接口其實(shí)就是類的公共方法。大家請看圖1。圖1圖1中的黑匣子就是封裝的一個(gè)良好表現(xiàn)。我們將對象的方法和數(shù)據(jù)放在類這個(gè)黑匣子里，從外面是看不見它內(nèi)部的構(gòu)造的。只有通過接口才能在黑匣子（對象）與黑匣

3、子之間傳遞消息。接下來我們看到圖2。 圖2對于intSquare(求平方)這個(gè)類，它包含了一個(gè)私有的成員變量：squareValue和兩個(gè)成員方法：一個(gè)公共的getSqure()方法，一個(gè)私有的calculateSquare()方法。而這個(gè)公共的getSqure()方法就是這個(gè)類的接口。這個(gè)類的對象，通過這個(gè)公共方法與別的對象互發(fā)消息。這樣一種機(jī)制就是數(shù)據(jù)隱藏。而在這里我們需要注意到一個(gè)問題：我們在這里提到的接口和Interface接口是兩個(gè)不一樣的概念。Interface指的是特定于一種編程語言的一種語法構(gòu)造，比如說java里就存在這樣一種語法構(gòu)造。而我們這里說的接口是指類的公共方法，兩者是

4、有區(qū)別的。其次，我們來看看什么是繼承。代碼復(fù)用被稱為是面向?qū)ο笤O(shè)計(jì)中最強(qiáng)大的一個(gè)特性，而繼承就是提供代碼復(fù)用的一個(gè)主要途徑。所謂繼承，其實(shí)就是一個(gè)is-a關(guān)系，即“是什么”的關(guān)系。請看圖3。圖3我們知道Dog的眼睛是有顏色的，Cat的眼睛是有顏色的，我們能獲取Dog的眼睛顏色，也能獲取Cat的眼睛顏色，于是我們將eyeColor這個(gè)變量與getEyeColor()抽象成一個(gè)Mammal類，并且讓Dog與Cat繼承這個(gè)Mammal類，實(shí)現(xiàn)了代碼的復(fù)用。我們可以說Dog is-a Mammal，Cat is-a Mammal。這就是所謂的繼承。再次，我們來介紹什么是多態(tài)。多態(tài)雖然是與繼承緊密相連，

5、依托與繼承的思想，卻被單獨(dú)看做是面向?qū)ο蠹夹g(shù)中最強(qiáng)大的優(yōu)點(diǎn)。如果一個(gè)類的某一方法被定義為abstract，則其子類必須為其提供一個(gè)實(shí)現(xiàn)。每個(gè)類能以不同的方式對同一個(gè)方法做出響應(yīng)，這樣一個(gè)過程就叫做多態(tài)。比如說如果我要求你畫出一個(gè)“形狀”，你一定不知所措。但是如果讓你畫出一個(gè)圓形，這很容易實(shí)現(xiàn)，再讓你畫出一個(gè)矩形，這也輕而易舉。那大家來看下面的圖4。圖4Shape是一個(gè)抽象類，它包含一個(gè)抽象方法draw()，有兩個(gè)子類繼承它，并且為draw提供了兩種不同的實(shí)現(xiàn)。這就是多態(tài)。最后，我們來了解什么是組合。構(gòu)建類有且只有兩種方法：一者為繼承，一者即為組合。組合指的是對象由其他對象構(gòu)建或者組合而成。相對

6、于繼承，組合可以被定義是一種has-a關(guān)系，即一種歸屬關(guān)系。組合被分為兩種類型，一者為聚集，一者為關(guān)聯(lián)。他們的區(qū)別在于：聚集相對于組合，是一種更加強(qiáng)烈的歸屬關(guān)系。聚集可以被認(rèn)為是“什么是什么的一部分”，而關(guān)聯(lián)通常被看做是“什么調(diào)用了什么的服務(wù)”。我們來看圖5。表示聚集的UML圖表示關(guān)聯(lián)的UML圖 我們可以說主板是計(jì)算機(jī)的一部分，RAM是計(jì)算機(jī)的一部分，于是主板與RAM與計(jì)算機(jī)是聚集關(guān)系。而我們說客戶機(jī)調(diào)用服務(wù)器的服務(wù)，所以客戶機(jī)與服務(wù)器之間是關(guān)聯(lián)關(guān)系。/第一部分好像寫得太口語化了，應(yīng)該需要改。第二部分 OO分析與設(shè)計(jì)的指導(dǎo)思想面向?qū)ο笏枷霃乃Q生之初就被認(rèn)為是一種較為抽象而模糊的概念，而面向?qū)?/p>

7、象的分析與設(shè)計(jì)常常被混為一談，而無法做到真正的分析與設(shè)計(jì)的分離。所以我們對面向?qū)ο蟮姆治雠c設(shè)計(jì)的指導(dǎo)思想的要求只在于它能指導(dǎo)我們做出一些切實(shí)可行的分析設(shè)計(jì)，最終得到有效的結(jié)果。而一般來說，一個(gè)可靠的面向?qū)ο蠓治雠c設(shè)計(jì)通常包括以下八個(gè)步驟：完成適當(dāng)?shù)姆治鼋⒁环菝枋鱿到y(tǒng)的工作陳述從這個(gè)工作陳述中收集需求開發(fā)一個(gè)用戶界面原型明確類確定各個(gè)類的職責(zé)確定個(gè)各類如何相互交互創(chuàng)建一個(gè)高層模型來描述要構(gòu)建的系統(tǒng)為了更好地應(yīng)用這八個(gè)步驟來指導(dǎo)我們的分析與設(shè)計(jì)，現(xiàn)引入以下幾點(diǎn)概念：快速原型模型(Rapid Prototyping Model)快速原型模型是一種軟件開發(fā)模型，在文檔驅(qū)動(dòng)的瀑布模型的基礎(chǔ)之上，迅速構(gòu)

8、造一個(gè)可以運(yùn)行的軟件原型，通過反復(fù)迭代，使開發(fā)人員與用戶達(dá)成共識，幫助開發(fā)人員與用戶更好地明確需求，減少不必要的模糊與錯(cuò)誤。統(tǒng)一建模語言(Unified Modeling Language,UML)UML是一種面向?qū)ο蟮慕ＵZ言，它是運(yùn)用統(tǒng)一的、標(biāo)準(zhǔn)化的標(biāo)記和定義實(shí)現(xiàn)對軟件系統(tǒng)進(jìn)行面向?qū)ο蟮拿枋龊徒?。因?yàn)樗且环N圖示化的語言，非常便于描述抽象的類與類的相互關(guān)系。需求項(xiàng)目符號列表需求項(xiàng)目符號列表其實(shí)就是將需求以符號列表的形式羅列出來。這種表現(xiàn)形式比簡單地用大段文字去描述需求要簡潔明了很多。CRC建模(Class-Responsibility-Collaboration,CRC)類-職責(zé)-協(xié)作建

9、模，被簡稱為CRC建模。該建模方式的核心思想是通過明確類、類的職責(zé)以及類的協(xié)作關(guān)系，得到一個(gè)中間結(jié)果，即CRC卡，再由凌亂的CRC卡重新組裝，最終設(shè)計(jì)出類圖。用例場景(use-case)用例定義為系統(tǒng)對用戶請求或事件做出響應(yīng)時(shí)完成的一個(gè)事務(wù)或相關(guān)操作序列。對于每個(gè)用例，都有它交換的對象和消息。而用例場景就是就是用例在交換消息時(shí)的一組簡單講，用例就是對全部用例場景的抽象，用例場景就是從用例中實(shí)例化出來的一組活動(dòng)。舉個(gè)簡單的例子：A向B要一支鋼筆，B返回給A一支鋼筆。這就是一個(gè)可能的用例場景。創(chuàng)建用例場景的目的并不是全面記錄所有可能的場景，這是我們所辦不到的，而是幫助我們更好地該井我們所選擇的類及

10、其職責(zé)。協(xié)作圖(Collaboration Diagram )用到了用例場景，我們就希望能夠創(chuàng)建協(xié)作圖來幫助我們明確用例場景。因?yàn)閳D例永遠(yuǎn)比文字更讓人清晰且易懂。就拿剛才的例子來做圖（圖2.1）。圖2.1第三部分 面向?qū)ο蟮脑~法分析器的分析與設(shè)計(jì)這一部分我們將會(huì)將前兩部分所介紹的概念加以應(yīng)用，按照指導(dǎo)思想的思路一步步地進(jìn)行實(shí)踐，最終得到我們想要的詞法分析器的設(shè)計(jì)結(jié)果。在這一部分，我們將從兩個(gè)方面進(jìn)行介紹。首先將實(shí)踐第二部分中提到的面向?qū)ο蟮闹笇?dǎo)思想；其次，將簡單介紹在詞法分析器的開發(fā)過程中會(huì)涉及到的注意事項(xiàng)。3.1 完成適當(dāng)?shù)姆治鏊^適當(dāng)?shù)姆治?，就是指在最淺的層次進(jìn)行分析。我們可以以一個(gè)站在頂

11、層的角度來俯瞰我們的項(xiàng)目。在這個(gè)角度，我們可以問自己三個(gè)問題：我們要做的是什么？輸入是什么？輸出是什么？我們要做的就是一個(gè)詞法分析器，它的輸入就是minijava源程序，輸出即是token鏈。在這一步里，我們確實(shí)只要做這么一個(gè)淺層的分析即可，只要將原本很模糊很抽象的項(xiàng)目需求稍微具象化就已經(jīng)足夠，因?yàn)殡S著分析的深入，我們自然會(huì)一點(diǎn)一點(diǎn)地將需求明確且具體。于是我們得到了下面的示意圖（圖3.1）：圖3.13.2 建立一份描述系統(tǒng)的工作陳述工作陳述（Statement of Work，SOW）既是一份概要,在很高的層次上說明項(xiàng)目的用途,范圍與途徑。SOW幫助你沿著正確的方向安排策劃工作。一般地，一份工

12、作陳述通常包括以下5個(gè)部分：項(xiàng)目開發(fā)內(nèi)容標(biāo)準(zhǔn)，約束/限制條件（技術(shù)、時(shí)間、成本）依賴關(guān)系交付內(nèi)容驗(yàn)收標(biāo)準(zhǔn)對于我們的項(xiàng)目，其開發(fā)內(nèi)容即是開發(fā)出一個(gè)基于面向?qū)ο笏枷氲膍inijava語言詞法分析器。它在技術(shù)與成本上是沒有限制條件的，只是在時(shí)間上要求五周之內(nèi)必須交付。它存在兩個(gè)依賴關(guān)系：一是與C#外部界面有交互；二是與語法分析器之間有交互。它的交付物就是一個(gè)獨(dú)立而完整的詞法分析器。其驗(yàn)收標(biāo)準(zhǔn)是輸入minijava源程序，能輸出token鏈，如果有錯(cuò)誤，能夠打印出錯(cuò)誤。實(shí)際上，工作陳述應(yīng)該是一份描述系統(tǒng)的文檔，而介于我們的項(xiàng)目屬于小型項(xiàng)目，在這里就以符號列表的形式表現(xiàn)出來了。3.3 從這個(gè)工作陳述中收

13、集需求需求是一個(gè)非常重要的東西，就好像是建筑的地基一樣，如果地基不夠深入，不夠堅(jiān)固，上層建筑很難做到堅(jiān)不可摧。而設(shè)計(jì)是一個(gè)迭代的過程，我們一定是在多次的迭代以后才能形成一個(gè)較為準(zhǔn)確的需求。我們從工作陳述中收集其以下的需求，將其以項(xiàng)目符號列表的方式展現(xiàn)出來：詞法分析器的主要目的是實(shí)現(xiàn)一個(gè)能夠完成詞法分析的程序；將源文件打開，將源文件以字符串的形式讀入到緩沖區(qū)中；對源程序的字符進(jìn)行線性分析，忽略空白字符及注釋，識別有效字符并標(biāo)識它的行號、類型、語義信息，形成token，然后鏈到Token鏈中；能識別的有效字符包括保留字、標(biāo)識符、常量、運(yùn)算符、分界符；有效識別詞法錯(cuò)誤，并能夠定位并打印錯(cuò)誤；打印to

14、ken鏈，完成詞法分析；3.4 開發(fā)一個(gè)用戶界面的原型我們采用的軟件開發(fā)模型是快速原型，這就要求我們需要開發(fā)出一個(gè)用戶界面的原型，因?yàn)楹芸赡芪覀兊挠脩魧τ?jì)算機(jī)領(lǐng)域并不了解，我們需要一個(gè)可視的界面原型，告知用戶通過需求我們設(shè)想了這么一個(gè)可能的軟件原型。通過此原型，便于與用戶共同明確需求。以下就是我們開發(fā)出的用戶原型（圖3.2）：圖3.23.5 明確類經(jīng)過反復(fù)迭代之后，我們明確了最終的需求，并且拋棄了原型，至此可以開始進(jìn)一步的設(shè)計(jì)?？梢钥吹?，現(xiàn)在我們已經(jīng)進(jìn)入了CRC建模的第一步，即明確類。明確類的一種最直觀的方法就是重點(diǎn)標(biāo)出所有名詞。于是我們將需求項(xiàng)目符號列表中的名詞重點(diǎn)標(biāo)記出來，得到了一張可能的

15、類名表。值得注意的是，設(shè)計(jì)是一個(gè)迭代的過程，我們不可能一次性得到最終的結(jié)果，必定經(jīng)過反復(fù)的協(xié)商與迭代。以下是我們得到的可能的類列表：詞法分析器 Lexer源文件 File緩沖區(qū) Buffer空白字符 Blank注釋 Note行號 Line類型 Type語義信息 Seman保留字 Keyword標(biāo)識符 Identity常量 Constant運(yùn)算符 Operator分界符 BoundaryToken Token List詞法錯(cuò)誤 Lexer Error并不是說以上舉出的所有名詞都是我們想要的類，可能會(huì)缺少，也可能會(huì)多余，這就需要我們進(jìn)行篩選。詞法分析器 Lexer我們可以把Lexer當(dāng)成是一個(gè)頂層

16、的黑盒子，從外面看不到任何內(nèi)部的構(gòu)造，讓詞法分析全部在這個(gè)黑盒子里完成。所以我們需要保留這個(gè)類。源文件 File這個(gè)類掌控著文件，必須保留。緩沖區(qū) Buffer通過緩沖區(qū)存儲(chǔ)源程序，可以節(jié)省輸入輸出的時(shí)間,所以這個(gè)類也是需要保留的?？瞻鬃址?Blank空白字符只是一類字符的名稱，太過于具體，并不能成為一個(gè)類。我們需要?jiǎng)h除它。注釋 Note就像空白字符一樣，注釋也只是一類字符，我們不需要它。行號 Line行號只是token的一個(gè)屬性，并不成為類。不需要保留。類型 Type類型也只是token的一個(gè)屬性。我們需要?jiǎng)h掉它。語義信息 Seman語義信息也只是token的一個(gè)屬性。刪除即可。保留字 Ke

17、yword保留字其實(shí)是一類token，我們想到“是什么”其實(shí)可以抽象出一個(gè)繼承關(guān)系。在這里我們將保留字劃掉，在以后讓它繼承token類。標(biāo)識符 Identity類似保留字，將其劃去。常量 Constant類似保留字，將其劃去。運(yùn)算符 Operator類似保留字，將其劃去。分界符 Boundary類似保留字，將其劃去。Token作為詞法分析器的中間結(jié)果，我們需要將這個(gè)類保留。TokenList詞法分析器的輸出結(jié)果，我們也需要保留。詞法錯(cuò)誤 LexerError當(dāng)源程序出現(xiàn)錯(cuò)誤的時(shí)候，錯(cuò)誤信息應(yīng)該被報(bào)告給LexerError類，所以錯(cuò)誤類必須被保留。這樣一來我們就保留類6個(gè)類，分別是：詞法分析器

18、Lexer源文件 File緩沖區(qū) BufferToken Token List詞法錯(cuò)誤 Lexer Error3.6 確定各個(gè)類的職責(zé)仿造之前發(fā)現(xiàn)類的方法，我們先來關(guān)注類的職責(zé)的詞性。我們發(fā)現(xiàn)類的職責(zé)通常是動(dòng)詞。于是我們將需求列表中的動(dòng)詞加以關(guān)注。但是同時(shí)又需要注意，并不是所有的動(dòng)詞都對應(yīng)著類的職責(zé)，并且可能兩個(gè)類都擁有同樣的職責(zé)，這都需要我們進(jìn)一步的分析。下面列出各個(gè)類可能的職責(zé)：Lexer開始詞法分析顯示詞法分析結(jié)果結(jié)束詞法分析File打開文件讀文件關(guān)閉文件Buffer從文件讀入字符串獲取一個(gè)字符清空TokenList構(gòu)建下一個(gè)Token將構(gòu)建的Token加入序列尾打印Token序列Tok

19、en設(shè)置/獲取 行號信息設(shè)置/獲取 類型信息設(shè)置/獲取 語義信息LexerError打印錯(cuò)誤信息值得注意的是，以上給出的設(shè)計(jì)列表其實(shí)是我們經(jīng)過反復(fù)迭代最終產(chǎn)生的結(jié)果。其實(shí)在設(shè)計(jì)之初，我們曾經(jīng)想將構(gòu)造下一個(gè)token以及將構(gòu)造的token加入tokenlist中的任務(wù)交給Lexer類，但是如果是這樣做的話，就讓Lexer集合了太多的職責(zé)，而顯得無比臃腫。就好像它是結(jié)構(gòu)化程序設(shè)計(jì)中的main函數(shù)一樣，將所有的職責(zé)都自己來扛，無法滿足我們高內(nèi)聚低耦合的訴求。所以我們最終確定的版本就拋棄了之前的想法。設(shè)計(jì)是一個(gè)迭代的過程，在這個(gè)過程中我們享受的不單單只是結(jié)果，其實(shí)在反復(fù)迭代的過程中，才恰恰蘊(yùn)含著思考的

20、快樂。3.7 確定各類如何相互交互類的交互就是要確定類的協(xié)作關(guān)系，我們來想象一下可能的用例場景：Lexer啟動(dòng)File打開文件Buffer讀入源程序Buffer向Tokenlist一個(gè)一個(gè)地送字符Tokenlist根據(jù)字符開始構(gòu)建Token,為其設(shè)置行號,類型,語義信息Tokenlist將其構(gòu)建的不同類型的Token鏈入Tokenlist當(dāng)中Tokenlist將錯(cuò)誤信息交給LexerError類LexerError類記錄錯(cuò)誤信息Lexer發(fā)出show()命令Tokenlist打印Token序列LexerError打印error位置及其類型Lexer類發(fā)出結(jié)束命令Buffer清空緩沖區(qū)下面來確定

21、一些協(xié)作關(guān)系。有個(gè)主應(yīng)用，負(fù)責(zé)發(fā)起詞法分析器。圖3.3到圖3.11表示了與上述設(shè)計(jì)有關(guān)的協(xié)作圖。圖3.3 Lexer啟動(dòng)圖3.4 Lexer讓File打開文件圖3.5 Buffer從File讀入源程序，Lexer關(guān)閉文件圖3.6 Buffer向Tokenlist一個(gè)一個(gè)地送字符圖3.7Tokenlist根據(jù)字符開始構(gòu)建Token圖3.8 Tokenlist將錯(cuò)誤信息交LexerError圖3.9 Tokenlist為Token設(shè)置行號信息，Tokenlist為Token設(shè)置類型信息，Tokenlist為Token設(shè)置語義信息圖3.10 Lexer發(fā)出show()命令，Tokenlist打印Token序列，LexerError打印error位置及其類型圖3.11 Lexer類發(fā)出結(jié)束命令，Buffer清空緩沖區(qū)至此，我們已經(jīng)完成了CRC