C語言編譯器的設(shè)計(jì)開發(fā)-+字節(jié)代碼格式設(shè)計(jì)與實(shí)現(xiàn)

真的不掉線嗎??、?？？？？？？？？？？？C語言編譯器的設(shè)計(jì)開發(fā)字節(jié)代碼格式設(shè)計(jì)與實(shí)現(xiàn)畢業(yè)設(shè)計(jì)（論文）中文摘要C語言編譯器的設(shè)計(jì)開發(fā)摘要編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一,而且多數(shù)計(jì)算機(jī)系統(tǒng)都含有不止ー個(gè)高級(jí)語言的編譯程序,對(duì)有些高級(jí)語言甚至配置了幾個(gè)不同性能的編譯程序。從功能上看,ー個(gè)編譯程序就是ー個(gè)語言翻譯程序。它把ー種語（稱作源語言）書寫的程序翻譯成另ー種語言（稱作目標(biāo)語言）的等價(jià)的程序。比如匯編程序是ー個(gè)翻譯程序,它把匯編語言程序翻譯成機(jī)器語言程序。如果源語言是像FORTRAN,PASCAL,或C那樣的高級(jí)語言,目標(biāo)語言是像匯編語言或機(jī)器語言那樣的低級(jí)機(jī)器語言,則這種翻譯程序稱作編譯程序。ー個(gè)編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算機(jī)用戶不必考慮與機(jī)器有關(guān)的繁索細(xì)節(jié),使程序員和程序設(shè)計(jì)專家獨(dú)立于機(jī)器,這對(duì)于當(dāng)今機(jī)器的數(shù)量和種類持續(xù)不斷地增長的年代尤為重要。編譯過程劃分了詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、六個(gè)階級(jí)。另外兩個(gè)重要的工作:表格處理和出錯(cuò)處理與上述六個(gè)階級(jí)都有聯(lián)系。畢業(yè)設(shè)計(jì)（論文）外文摘要TitleTheDesignandDevelopmentofCCompilerAbstractThecompilerprocedureandtranslateoffundamentalisamoderncalculatorsystemtoconstitutetheoneoftheparts,andthesystemofmostcalculatorsallsimplytheeditandtranslatingoflanguageofahighclasstheprocedure,eveninstalledtheprocedureofeditandtranslatingofafewanddifferentfunctiontosomehighclasslanguage.Seefromthefunction,anditisprocedureofalanguagetranslationthateditandtranslatetheprocedure.Ittranslateakindoflanguage(callthesourcelanguage)procedurethatwriteintotheprocedureoftheanotherlanguage(callthetargetlanguage).Forexampleeditcollectedmaterialstheprocedureisatranslationprocedure,ittotranslateeditcollectedmaterialsthelanguageprocedureintothemachinelanguagetheprocedure.Ifhighclasslanguage,targetlanguagethatlanguageis1ikeofFORTRAN,PASCAL,ortheCissotoaseditcollectedmaterialsthelanguageormachinelanguagesooflowclassjadearticlespeech,thenthiskindoftranslationtheprocedurecalltoeditandtranslatetheprocedure.Animportancethateditandtranslateprocedurenowitmakemostcalculatorsesthecustomerneednotconsidertheheavydetailsthathaverelationwithmachine,andmaketheproceduredesigntheexpert'sindependencewithprocedureinthemachine,thequantitythatthisisforthemachinethatnowadaysagekeeponwithcategorytoconstantlyincreasetoimportance.Editandtranslatedtheprocesstodividethelinethephrasemethodtheanalysis,phrasingtheanalysis,languagetherighteousnesstheanalysis,inthecenterthecodeisborn,code,targetthecodeisborn,sixrank.Anothertwoimportanceofwork:Theformhandleswithcomeamisstohandletohaveconnectionwithabovesixranksesall.Keywordscompilerprocedure,sourcelanguage,targetlanguage,codegeneration,middlecode,synaxanalyers,lexicalanalyzers,intermediatecode,bytecode!引言（或緒論） 2編譯器的基礎(chǔ)知識(shí) ……21編譯器的發(fā)展背景 …32編譯器研發(fā)的可行性分析 33編譯過程概 53系統(tǒng)需求分析 83.1LEX概述 82C語言簡介 93軟件工程方法論的應(yīng)用 104詞法語法分析簡介 …135詞法需求分析簡…136語法需求分析簡7符號(hào)表的應(yīng)用 154系統(tǒng)設(shè)計(jì) 161系統(tǒng)設(shè)計(jì)總體流程圖 164.2語法分析體流程圖 …174.3語法分析概要設(shè)計(jì) …184.4目標(biāo)代碼的分析 214.580x86指令系統(tǒng) 244.6字節(jié)代碼設(shè)計(jì) 254.7虛擬寄存器的設(shè)計(jì) …264.8字節(jié)代碼詳細(xì)設(shè)計(jì) …275使用說明書 346結(jié)論 …… 35致謝 36參考文獻(xiàn) 37!引言（或緒論）編譯器的設(shè)計(jì)涉及到編譯程序構(gòu)造的一般原理、基本設(shè)計(jì)方法、主要實(shí)現(xiàn)技術(shù)和一些自動(dòng)構(gòu)造工具。盡管“編譯程序”是特指將高級(jí)程序設(shè)計(jì)語言翻譯成低級(jí)語言的軟件,但編譯程序構(gòu)造的基本原理和技術(shù)也廣泛應(yīng)用于一般的設(shè)計(jì)和實(shí)現(xiàn),因此,是ー門對(duì)實(shí)踐性要求較高的課程。目前,世界上存在著數(shù)千種源語言,既有Fortran和Pasca!這樣的傳統(tǒng)程序設(shè)計(jì)語言,也有各計(jì)算機(jī)應(yīng)用領(lǐng)域中出現(xiàn)的專用語言。目標(biāo)語言也同樣廣泛,目標(biāo)語言可以是另ー種程序設(shè)計(jì)語言或者是從微處理機(jī)到計(jì)算機(jī)的任何計(jì)算機(jī)的機(jī)器語言。不同語言需要不同的編譯器。根據(jù)編譯器的構(gòu)造方法或者它們要實(shí)現(xiàn)的功能,編譯器被分為一遍編譯器、多遍編譯器、裝入并執(zhí)行編譯器、調(diào)試編譯器、優(yōu)化編譯器等多種類別。從表面上看,編譯器的種類似乎千變?nèi)f化,多種多樣,實(shí)質(zhì)上任何編譯器所要完成的基本任務(wù)都是相同的。通過理解這些任務(wù),我們可以利用同樣的基本技術(shù)為各種各樣的源語言和目標(biāo)機(jī)器構(gòu)建編譯器。編譯器也可能沒有生成真正的可執(zhí)行代碼,而是生成了某種形式的匯編代碼,這必須由匯編器、鏈接器和裝入器進(jìn)行進(jìn)ー步處理。匯編器、鏈接器和裝入器可由操心系統(tǒng)提供或由編譯器自帶。在翻譯期間,中間表示或な代表了源程序和數(shù)據(jù)結(jié)構(gòu)。雖然抽象語法樹是源代碼完美充分的表達(dá),即使對(duì)于代碼生成也不過這樣,但是它與目標(biāo)代碼極不相像,在控制流構(gòu)造上尤為如此。在控制流構(gòu)造上,目標(biāo)代碼使用轉(zhuǎn)移語句而不是if和while語句。因此,編譯器編寫者可能希望從語法樹生成一個(gè)更接近目標(biāo)代碼的中間表示形式,或者用這樣一個(gè)中間表示代替語法樹,然后再從這個(gè)新的中間表示生成目標(biāo)代碼。中間代碼生成在進(jìn)行了上述的語法分析和語義分析的工作之后,有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式,這種內(nèi)部表示形式叫做中間語言或中間代碼。所謂“中間代碼”是ー種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng),這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式,重要的設(shè)計(jì)原則為兩點(diǎn):ー是容易生成;ニ是容易將它翻譯成目標(biāo)代碼。很多編譯程采用了一種近似“三地址指令”的“四元式”中間代碼,這種四元式的形式為:（運(yùn)算符,運(yùn)算對(duì)象1,運(yùn)算對(duì)象2,結(jié)果）。2編譯器的基礎(chǔ)知識(shí)ー個(gè)編譯程序就是ー個(gè)語言翻譯程序。它把ー種語（稱作源語言）書寫的程序翻譯成另ー種語言（稱作目標(biāo)語言）的等價(jià)的程序。比如匯編程序是ー個(gè)翻譯程序,它把匯編語言程序翻譯成機(jī)器語言程序。如果源語言是像FORTRAN,PASCAL,或C那樣的高級(jí)語言,目標(biāo)語言是像匯編語言或機(jī)器語言那樣的低級(jí)語言,則這種翻譯程序稱作編譯程序。2.1編譯器的發(fā)展背景編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一,而且多數(shù)計(jì)算機(jī)系統(tǒng)都含有不止ー個(gè)高級(jí)語言的編譯程序,對(duì)有些高級(jí)語言甚至配置了幾個(gè)不同性能的編譯程序。從功能上看,ー個(gè)編譯程序就是一個(gè)語言翻譯程序。它把ー種語（稱作源語言）書寫的程序翻譯成另ー種語言（稱作目標(biāo)語言）的等價(jià)的程序。比如匯編程序是ー個(gè)翻譯程序,它把匯編語言程序翻譯成機(jī)器語言程序。如果源語言是像FORTRAN,PASCAL,或C那樣的高級(jí)語言,目標(biāo)語言是像匯編語言或機(jī)器語言那樣的低級(jí)語言,則這種翻譯程序稱作編譯程序。ー個(gè)編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算機(jī)用戶不必考慮與機(jī)器有關(guān)的繁索細(xì)節(jié),使程序員和程序設(shè)計(jì)專家獨(dú)立于機(jī)器,這對(duì)于當(dāng)今機(jī)器的數(shù)量和種類持續(xù)不斷地增長的年代憂為重要。除了編譯程序外,還需要一些其它的程序才能生成一個(gè)可在計(jì)算機(jī)執(zhí)行的目標(biāo)程序。ー個(gè)源程序有時(shí)可能分成幾個(gè)模塊存放在不同的文件里,將這些源程序匯集在ー起的任務(wù),由一個(gè)叫做預(yù)處理程序的程序完成,有些預(yù)處理程序也負(fù)責(zé)宏展開,像。語言和預(yù)處理程序要完成文件合并、宏展開等任務(wù)。也就是說,ー個(gè)編譯程序的輸入可能要一個(gè)或多個(gè)預(yù)處理程序來產(chǎn)生,另外,為得到能運(yùn)行的機(jī)器代碼,編譯程序的輸出可能仍需要進(jìn)ー步地處理。詞法分析階級(jí)是編譯過程的第一個(gè)階級(jí)。這個(gè)階級(jí)的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序,對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解,從而識(shí)別ー個(gè)個(gè)單詞（也稱為單詞符號(hào)或符號(hào)）。這里所謂的單詞是指邏輯上緊密相連的ー組字符,這些字符具有集體含義。比如標(biāo)識(shí)是由字母開頭,后跟字母、數(shù)字字符序列組成的ー種單詞,。保留字是ー種單詞,此外還有算符,界符等等。語法分析是編譯過程的第二個(gè)階段。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語。如“程序”，“語句”，“表達(dá)式”等等。一般這種語法短語也稱為語法單位,可表示成語法樹。語法分析所依據(jù)的是語言的語法規(guī)則,即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序。典型的文法的語法分析器有三類:ー類是通用的語法分析方法,如Cocke-Younger-Kasami算法和Early算法,這些方法在生成編譯器時(shí)效率太低。編譯器常用的是自頂向下和自底向上的方法。

采用自頂向下的遞歸子程序法,就是對(duì)應(yīng)每個(gè)非終結(jié)符語法單元,編ー個(gè)獨(dú)立的處理子程序。語法分析從讀入第一個(gè)單詞開始,由非終結(jié)符即開始符出發(fā),沿語法描述圖箭頭指出的方向進(jìn)行分析。當(dāng)遇到非終結(jié)符時(shí),則調(diào)用相應(yīng)的處理子程序，從語真的不掉線嗎??ヽ?？？？？？？？？？？？法描述圖看也就進(jìn)入了一個(gè)語法單元，再沿當(dāng)前所進(jìn)入的語法描述圖的箭頭方向進(jìn)行分析,當(dāng)遇到終結(jié)符時(shí),則判斷當(dāng)前讀入的單詞是否與圖中的終結(jié)符相匹配,若匹配,則執(zhí)行相應(yīng)的語義程序。再讀取下ー個(gè)單詞繼續(xù)分析。遇到分支點(diǎn)時(shí)將當(dāng)前的單詞與分支點(diǎn)上的多個(gè)終結(jié)符逐個(gè)相比較,若都不匹配時(shí)可能是進(jìn)入下ー非終結(jié)符語法單位或是出錯(cuò)。自頂向下的分析算法通過在最左推導(dǎo)中描述出各個(gè)步驟來分析記號(hào)串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號(hào)是ー個(gè)前序編,而且其順序是由根到葉子。自頂向下的分析程序有兩類:回溯分析程序和預(yù)測分析程序。預(yù)測分析程序試圖利用ー個(gè)或多個(gè)先行記號(hào)來預(yù)測出輸入串中的下ー個(gè)構(gòu)造,而回溯分析程序則試著分析其他可能的輸入,當(dāng)ー種可能失敗時(shí)就要求輸入中備份任意數(shù)量的字符。雖然回溯分析程序比預(yù)測強(qiáng)大許多,但它們都非常慢,一般都在指數(shù)的數(shù)量級(jí)上,所以對(duì)于實(shí)際的編譯器并不適合。遞歸下降程序分析和LL(1)分析一般地都要求計(jì)算先行集合,它們分別稱作First集合和Follow集合。由于無需顯示地構(gòu)造出這些集合就可以構(gòu)造出簡單的自頂向下的分析程序,所以在基本算法的介紹之后我們?cè)儆懻撍鼈?。之后我償還要談到ー個(gè)由遞歸下降分析構(gòu)造的分析程序。由于代碼生成較復(fù)雜,所以編譯器一般將這ー階段分

成幾個(gè)涉及不同中間數(shù)據(jù)結(jié)構(gòu)的步驟,其中包括了某種稱作中間代碼的抽象代碼。編譯器也可能沒有生成真正的可執(zhí)行代碼,而是生成了某種形式的匯編代碼,這必須由匯編器、鏈接器和裝入器進(jìn)行進(jìn)ー步處理。匯編器、鏈接器和裝入器可由操心系統(tǒng)提供或由編譯器自帶。在翻譯期間,中間表示或IR代表了源程序和數(shù)據(jù)結(jié)構(gòu)。雖然抽象語法樹是源代碼完美充分的表達(dá),即使對(duì)于代碼生成也不過這樣,但是它與目標(biāo)代碼極不相像,在控制流構(gòu)造上尤為如此。在控制流構(gòu)造上,目標(biāo)代碼使用轉(zhuǎn)移語句而不是if和while語句。因此,編譯器編寫者可能希望從語法樹生成一個(gè)更接近目標(biāo)代碼的中間表示形式,或者用這樣ー個(gè)中間表示代替語法樹,然后再從這個(gè)新的中間表示生成目標(biāo)代碼。這種類似目標(biāo)代碼的中間表示稱為中間代碼。2.2編譯器研發(fā)的可行性分析編寫編譯器的原理和技術(shù)具有十分普遍的意義,以致于在每ー個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中,許多原理和技術(shù)都會(huì)反復(fù)用到。編譯器的編寫涉及到程序設(shè)計(jì)語言、計(jì)算機(jī)體系結(jié)構(gòu)、語言理論、算法和軟件工程等學(xué)科。幸運(yùn)的是,有幾種基本編譯器編寫技術(shù)已經(jīng)被用于構(gòu)建許多計(jì)算機(jī)的多種語言翻譯器。簡單的說,編譯器是ー個(gè)程序,它讀入用某種語言（源語言）編寫的程序并將其翻譯成一個(gè)與之等價(jià)的以另ー種語言（目標(biāo)語言）編寫的程序。作為這個(gè)翻譯過程匠ー個(gè)重要組成部分,編譯器能夠向用戶報(bào)告被編譯的源程序中出現(xiàn)的錯(cuò)誤。編譯器由兩部分組成:分析與綜合。分析部分將源程序切分成一些基本塊并形成源程序的中間表示,綜合部分把源程序的中間表示轉(zhuǎn)為所需的目標(biāo)程序。在分析期間,源程序所蘊(yùn)含的操作將被確定下來并被表示成為ー個(gè)稱為語法樹的分層結(jié)構(gòu)。語法樹的每個(gè)節(jié)點(diǎn)表示一個(gè)操作,

該節(jié)點(diǎn)的子節(jié)點(diǎn)表示這個(gè)操作的參數(shù)。許多操縱源程序的軟件工具都首先完成某種類型的分析。下邊是這類工具的示例:真的不掉線嗎??、?？？？？？？？？？？？結(jié)構(gòu)編輯器,結(jié)構(gòu)編輯器將一個(gè)命令序列作為輸入ー構(gòu)造程序。智能打印機(jī),智能打印機(jī)能夠?qū)Τ绦蜻M(jìn)行分析,打印出結(jié)構(gòu)清晰的程序。靜態(tài)檢查器,靜態(tài)檢查器讀入一個(gè)程序,分析這個(gè)程序,并在不運(yùn)行這個(gè)程序的條件試圖發(fā)現(xiàn)程序的潛在錯(cuò)誤。解釋器,解釋器不是通過翻譯來產(chǎn)生目標(biāo)程序,而是直接執(zhí)行源程序中蘊(yùn)含的操作。目前,世界上存在著數(shù)千種源語言,既有Fortran和Pasca!這樣的傳統(tǒng)程序設(shè)計(jì)語言,也有各計(jì)算機(jī)應(yīng)用領(lǐng)域中出現(xiàn)的專用語言。目標(biāo)語言也同樣廣泛,目標(biāo)語言可以是另ー種程序設(shè)計(jì)語言或者是從微處理機(jī)到計(jì)算機(jī)的任何計(jì)算機(jī)的機(jī)器語言。不同語言需要不同的編譯器。根據(jù)編譯器的構(gòu)造方法或者它們要實(shí)現(xiàn)的功能,編譯器被分為

一遍編譯器、多遍編譯器、裝入并執(zhí)行編譯器、調(diào)試編譯器、優(yōu)化編譯器等多種類別。從表面上看,編譯器的種類似乎千變?nèi)f化,多種多樣,實(shí)質(zhì)上任何編譯器所要完成的基本任務(wù)都是相同的。通過理解這些任務(wù),我們可以利用同樣的基本技術(shù)為各種各樣的源語言和目標(biāo)機(jī)器構(gòu)建編譯器。從20世紀(jì)50年代早期第一個(gè)編譯器出現(xiàn)到今,我們所掌握的有關(guān)編譯器的知識(shí)已經(jīng)得到了長足的發(fā)展。整個(gè)20世紀(jì)50年代,編譯器的編寫一直被認(rèn)為是一個(gè)極難的問題。目前我們已經(jīng)系統(tǒng)地掌握了處理編譯期間發(fā)生的許多重要任務(wù)的技術(shù)。良好的實(shí)現(xiàn)語言、程序設(shè)計(jì)環(huán)境和軟件工具也已經(jīng)被開發(fā)出來。20世紀(jì)50年代末有人開始研究編譯程序的自動(dòng)生成技術(shù),提出并研制編譯程序的編譯程序。它的功能是以任ー語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā),自動(dòng)產(chǎn)生該語言的編譯程序。目前,很多自動(dòng)生成的工具已廣泛使用,如詞法分析的生成系統(tǒng)しEX,語法分析程序的生成系統(tǒng)YACC等。20世紀(jì)60年代起,不斷有人使用自展技術(shù)來構(gòu)造編譯程序。自展的主要特征是用被編譯的語言來書寫該語言自身的編譯程序。自從1971年,PASCAL的編譯程序用自展技術(shù)生成后,起影響就越來越大。研究編譯程序是有意義在于:編譯程序構(gòu)造是計(jì)算機(jī)科學(xué)中的ー個(gè)非常成功的分支,也是最早獲的成功的分支之一;

它與文件轉(zhuǎn)換程序關(guān)系密集,且不僅僅適用于編譯程序;它包含許多在實(shí)際應(yīng)用中有用的算法。由于近幾年并行機(jī)及多處理機(jī)的發(fā)展,對(duì)軟件的并行處理技術(shù)提出了新的要求。特別是并行編譯技術(shù)發(fā)展很快,目前處理并行編譯技術(shù)有兩種方法:第一種方法,運(yùn)用重構(gòu)技術(shù)把已有的串行語言編寫的程序經(jīng)過相關(guān)分析,分解成可并行的成分,分配到多CPU或多處理機(jī)上運(yùn)行,這種技術(shù)國內(nèi)已有FORTRAN和C語言的并行重構(gòu)處理系統(tǒng),相當(dāng)成功。第二種方法,即在程序設(shè)計(jì)語言機(jī)制上允許用戶自己編寫并行程序,這當(dāng)然比編寫串行語言對(duì)編程人員提出的要求更多。即用戶自己必須知道程序各模塊之間邏輯結(jié)構(gòu)關(guān)系及調(diào)用關(guān)系乃至運(yùn)算量,以確定哪些模塊可以并行執(zhí)行。若編程者能按程序設(shè)計(jì)情況編出并行程序,無疑并行程序效率將比第一種方法要好。隨著并行技術(shù)和并行語言的發(fā)展,處理并行語言的并行編譯技術(shù)正在深入研究之中,將串行程序轉(zhuǎn)換成并行程序的自動(dòng)并行編譯技術(shù)也正在深入研究之中。代碼生成較復(fù)雜,所以編譯器一般將這ー階段分成幾個(gè)涉及不同中間數(shù)據(jù)結(jié)構(gòu)的步驟,其中包括了某種稱作中間代碼的抽象代碼。編譯器也可能沒有生成真正的可執(zhí)真的不掉線嗎??、?？？？？？？？？？？？行代碼,而是生成了某種形式的匯編代碼,這必須由匯編器、鏈接器和裝入器進(jìn)行進(jìn)ー步處理。匯編器、鏈接器和裝入器可由操心系統(tǒng)提供或由編譯器自帶。在翻譯期間,中間表示或IR代表了源程序和數(shù)據(jù)結(jié)構(gòu)。雖然抽象語法樹是源代碼完美充分的表達(dá),即使對(duì)于代碼生成也不過這樣,但是它與目標(biāo)代碼極不相像,在控制流構(gòu)造上尤為如此。在控制流構(gòu)造上,目標(biāo)代碼使用轉(zhuǎn)移語句而不是if和while語句。因此，編譯器編寫者可能希望從語法樹生成一個(gè)更接近目標(biāo)代碼的中間表示形式,或者用這樣ー個(gè)中間表示代替語法樹,然后再從這個(gè)新的中間表示生成目標(biāo)代碼。這種類似目標(biāo)代碼的中間表示稱為中間代碼。然后編譯程序再調(diào)用相應(yīng)的處理程序，將中間代碼轉(zhuǎn)換為計(jì)算機(jī)能處理的機(jī)器指令,最終得到目標(biāo)代碼。3編譯過程概述編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一,而且多數(shù)計(jì)算機(jī)系統(tǒng)都含有不止ー個(gè)高級(jí)語言的編譯程序,對(duì)有些高級(jí)語言甚至配置了幾個(gè)不同性能的編譯程序。從功能上看,ー個(gè)編譯程序就是一個(gè)語言翻譯程序。它把ー種語（稱作源語言）書寫的程序翻譯成另ー種語言（稱作目標(biāo)語言）的等價(jià)的程序。比如匯編程序是ー個(gè)翻譯程序,它把匯編語言程序翻譯成機(jī)器語言程序。如果源語言是像FORTRAN,PASCAL,或C那樣的高級(jí)語言，目標(biāo)語言是像匯編語言或機(jī)器語言那樣的低級(jí)玉器言,則這種翻譯程序稱作編譯程序。ー個(gè)編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算機(jī)用戶不必考慮與機(jī)器有關(guān)的繁索細(xì)節(jié),使程序員和程序設(shè)計(jì)專家獨(dú)立于機(jī)器,這對(duì)于當(dāng)今機(jī)器的數(shù)量和種類持續(xù)不斷地增長的年代憂為重要。除了編譯程序外,還需要一些其它的程序才能生成一個(gè)可在計(jì)算機(jī)執(zhí)行的目標(biāo)程序。高級(jí)語言程序的處理過程如圖:需處理的源程序編譯程序目標(biāo)匯編程序可再裝配的機(jī)器代碼可在裝配的目標(biāo)文件真的不掉線嗎??、?？？？？？？？？？？？絕對(duì)機(jī)器代碼ー個(gè)源程序有時(shí)可能分成幾個(gè)模塊存放在不同的文件里,將這些源程序匯集在ー起的任務(wù),由一個(gè)叫做預(yù)處理程序的程序完成,有些預(yù)處理程序也負(fù)責(zé)宏展開,像C語言和預(yù)處理程序要完成文件合并、宏展開等任務(wù)。也就是說,ー個(gè)編譯程序的輸入可能要一個(gè)或多個(gè)預(yù)處理程序來產(chǎn)生,另外,為得到能運(yùn)行的機(jī)器代碼,編譯程序的輸出可能仍需要進(jìn)ー步地處理。編譯程序完成從源程序到目標(biāo)程序的翻譯工作,是ー個(gè)復(fù)雜的整體的過程。從概念上來講,ー個(gè)編譯程序和整體工作過程是劃分成階級(jí)進(jìn)行的,每個(gè)階級(jí)將源程序的ー種表示形式換成另ー種表示形式,各個(gè)階級(jí)進(jìn)行的操場作在邏輯上是緊密連接在ー起的,如圖1所示,給出了一個(gè)編譯過的和各個(gè)階級(jí),這是ー種比較典型的劃分方法。中間代碼生成圖1將編譯過程劃分了詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、六個(gè)階級(jí)。另外兩個(gè)重要的工作:表格處理和出錯(cuò)處理與上述六個(gè)階級(jí)都有聯(lián)系。編譯過程是源程序和各種信息被子保留在種種不同的表格里,編譯各階級(jí)的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格,因此需要有表格處理的工作;如果編譯過程中發(fā)現(xiàn)源程序有錯(cuò)誤,編譯程序應(yīng)報(bào)告錯(cuò)誤的性質(zhì)和錯(cuò)誤發(fā)生的地點(diǎn),并且將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi),使得源程序的其余部分能繼續(xù)被編譯下去,有些編譯程序還能自動(dòng)校正錯(cuò)誤,這些工作稱之為出錯(cuò)處理。詞法分析階級(jí)是編譯過程的第一個(gè)階級(jí)。這個(gè)階級(jí)的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序,對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解,從而識(shí)別ー個(gè)個(gè)單詞（也稱為單詞符號(hào)或符號(hào)）。這里所謂的單詞是指邏輯上緊密相連的ー組字符,這些字符具有集體含義。比如標(biāo)識(shí)是由字母開頭,后跟字母、數(shù)字字符序列組成的ー種單詞,。保留字是一種單詞,此外還有算符,界符等等。語法分析是編譯過程的第二個(gè)階級(jí)。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單真的不掉線嗎??ヽ?？？？？？？？？？？？詞序列分解成各類語法短語,如“程序”，“語句”，“表達(dá)式”等等。一般這種語法短語,也稱為語法單位,可表示成語法樹。語法分析所依據(jù)的是語言的語法規(guī)則,即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序。詞法分析和語法分析本質(zhì)上都是對(duì)源程序的結(jié)構(gòu)進(jìn)行分析。但詞法分析的任務(wù)僅對(duì)源程序進(jìn)行線性掃描即可完成,比如識(shí)別標(biāo)識(shí)符,因?yàn)闃?biāo)識(shí)符的結(jié)構(gòu)是字母打頭的字母和數(shù)字序列,這只要順序掃描輸入流,遇到既不是字母又不是數(shù)字字符時(shí),將前面所發(fā)現(xiàn)的所有字母和數(shù)字組合在ー起而構(gòu)成單詞標(biāo)識(shí)符。但這種線性掃描則不能用于識(shí)別遞歸定義的語法成分,比如就不能用此辦法去匹配表達(dá)式中的括號(hào)。語義分析階級(jí)是審查源程序有無語義錯(cuò)誤,為代碼生成階級(jí)收集類型信息。比如語分析的ー個(gè)工作是進(jìn)行類型審查,審查每個(gè)算符是否具有語言規(guī)范允許的運(yùn)算對(duì)象,當(dāng)不符合語言規(guī)范時(shí),編譯程序應(yīng)報(bào)告錯(cuò)誤。如有的編譯程序要對(duì)實(shí)數(shù)用個(gè)數(shù)組下標(biāo)的情況報(bào)告錯(cuò)誤。又如某些語言規(guī)定運(yùn)算對(duì)象可被強(qiáng)制,那么當(dāng)二目運(yùn)算一整數(shù)和一實(shí)型時(shí),編譯程序應(yīng)將整型轉(zhuǎn)換成實(shí)型而不能認(rèn)為是源程序的錯(cuò)誤。中間代碼生成在進(jìn)行了上述的語法分析和語義分析的工作之后,有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式,這種內(nèi)部表示形式叫做中間語言或中間代碼。所謂“中間代碼”是ー種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng),這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式,重要的設(shè)計(jì)原則為兩點(diǎn):ー是容易生成;ニ是容易將它翻譯成目標(biāo)代碼。很多編譯程采用了一種近似“三地址指令”的“四元式”中間代碼,這種四元式的形式為:（運(yùn)算符,運(yùn)算對(duì)象1,運(yùn)算對(duì)象2,結(jié)果）。代碼優(yōu)化在此階級(jí)的任務(wù)是對(duì)前階級(jí)產(chǎn)生的是間代碼進(jìn)行變換或進(jìn)行改造,目的是使生成的目標(biāo)代碼更為高效,即省時(shí)間和省空間。目標(biāo)代碼生成的任務(wù)是把是間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階級(jí),它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān),這個(gè)階的工作很復(fù)雜,涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。有時(shí),常常把編譯的過程分為前端和后端,前端由那樣ー些階級(jí)組成:這些階級(jí)的工作主要依賴于源語言而與目標(biāo)機(jī)無關(guān)。通常這些階段包括詞法分析、語法分析、語義分析和中間代碼生成,某些優(yōu)化工作也可在前端做,也包括與前端每個(gè)階級(jí)相關(guān)的出錯(cuò)處量工作和符號(hào)表管理工作。后端工作指那些依賴于目標(biāo)機(jī)而一般不依賴源語言,只與中間代碼有關(guān)的那些階段,即目標(biāo)代碼生成,以及相關(guān)出錯(cuò)處理和符號(hào)表操作。若按照這種姐合方式實(shí)現(xiàn)編譯程序,可以設(shè)想,某ー編譯程序的前端加上相應(yīng)不同的后端則可以為不同的機(jī)器構(gòu)成一個(gè)源語言的編譯程序。也可以設(shè)想,不同語言編譯的前端生成同一種中間語言,再使用一個(gè)共同的后端,則可為同一機(jī)器生成幾個(gè)語言的編譯程序。ー個(gè)編譯過程可由一遍、兩遍或多遍完成。所謂“遍”,也稱作“趟"是對(duì)源程序或其等價(jià)的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。每一遍掃視可完成上述ー個(gè)階段或多個(gè)階段的工作。例如一遍可以只完成詞法分析工作;一遍完成詞法分析和語法分析工作;甚至一遍完成整個(gè)編譯工作。對(duì)于多遍的編譯程序,第一遍的輸入是用戶書寫的源程序,最后一遍是輸出是目標(biāo)語言程序,其余是上一遍的輸出為下一遍的輸入。真的不掉線嗎??、?？？？？？？？？？？？3系統(tǒng)需求分析3.1LEX概述LEX是ー個(gè)詞法分析器（掃描器）的自動(dòng)產(chǎn)生系統(tǒng),它的示意圖如下:

LEX源程序LEXLEX源程序LEXyylex輸入串yylex 單詞符號(hào)串LEX源程序是用一種面向問題的語言寫成的。這個(gè)語言的核心是正規(guī)表達(dá)式（正規(guī)式）,用它描述輸入串的詞法結(jié)構(gòu)。在這個(gè)語言中用戶還可以描述某ー個(gè)詞形被識(shí)別出來時(shí)要完成的動(dòng)作,例如在高級(jí)語言的詞法分析器中,當(dāng)識(shí)別出ー個(gè)關(guān)鍵字時(shí),它應(yīng)該向語法分析器返回該關(guān)鍵字的內(nèi)部編碼。LEX并不是ー個(gè)完整的語言,它只是某種高級(jí)語言（稱為LEX的宿主語言）的擴(kuò)充,因此,LEX沒有為描述動(dòng)作設(shè)計(jì)新的語言,而是借助其宿主語言來描述動(dòng)作。LEX自動(dòng)地把表示輸入串詞法結(jié)構(gòu)的正規(guī)式及相應(yīng)的動(dòng)作轉(zhuǎn)換成一個(gè)宿主語言的程序,即詞法分析程序,它有一個(gè)固定的名字yylex,在這里yylex是ー個(gè)C語言程序。2C語言簡介C語言是在70年代初問世的。ー九七八年由美國電話電報(bào)公司（AT&T）貝爾實(shí)驗(yàn)室正式發(fā)表了C語言。同時(shí)由8.用わ0!181^1I和ル此!（辻（±辻合著了著名的“THECPROGRAMMINGLANGUAGE"ー書。通常簡稱為《K&R》,蟠人稱之為《K&R》標(biāo)準(zhǔn)。但是,在《K&R》中并沒有定義ー個(gè)完整的標(biāo)準(zhǔn)C語言,后來由美國國家標(biāo)準(zhǔn)協(xié)會(huì)（AmericanNationalStandardsInstitute）在此基礎(chǔ)上制定了一個(gè)C語言標(biāo)準(zhǔn),于一九八三年發(fā)表。通常稱之為ANSICo早期的C語言主要是用于UNIX系統(tǒng)。由于C語言的強(qiáng)大功能和各方面的優(yōu)點(diǎn)逐漸為人們認(rèn)識(shí),到了ハ十年代，C開始進(jìn)入其它操作系統(tǒng),并很快在各類大、中、小和微型計(jì)算機(jī)上得到了廣泛的使用，成為當(dāng)代最真的不掉線嗎??、?？？？？？？？？？？？優(yōu)秀的程序設(shè)計(jì)語言之一。目前最流行的C語言有以下幾種:MicrosoftC或稱MSCBorlandTurboC或稱TurboCAT&TC這些C語言版本不僅實(shí)現(xiàn)了ANSIC標(biāo)準(zhǔn),而且在此基礎(chǔ)上各自作了一些擴(kuò)充,使之更加方便、完美。C語言的特點(diǎn):1語言簡潔、緊湊,使用方便、靈活。ANSIC-共只有32個(gè)關(guān)鍵字:

breakCasecharconstCOinuedoubleelseenumexternfltifintlongregisterrernstaticSizofstructswitchtydefVOidvolatilewhile9種控制語句,程序書寫自由,主要用小寫字母表示,壓縮了一切不必要的成分。TurboC擴(kuò)充了11個(gè)關(guān)鍵字:asm_cs _ds _es _sscdeclfarhugeinterruptnear pascal注意:在C語言中,關(guān)鍵字都是小寫的。?運(yùn)算符豐富。共有34種。C把括號(hào)、賦值、逗號(hào)等都作為運(yùn)算符處理。從而使C的運(yùn)算類型極為豐富,可以實(shí)現(xiàn)其他高級(jí)語言難以實(shí)現(xiàn)的運(yùn)算。?數(shù)據(jù)結(jié)構(gòu)類型豐富。?具有結(jié)構(gòu)化的控制語句。5?語法限制不太嚴(yán)格,程序設(shè)計(jì)自由度大。6?C語言允許直接訪問物理地址,能進(jìn)行位（biい操作,能實(shí)現(xiàn)匯編語言的大部分功能,可以直接對(duì)硬件進(jìn)行操作。因此有人把它稱為中級(jí)語言。7?生成目標(biāo)代碼質(zhì)量高,程序執(zhí)行效率高。8?與匯編語言相比,用C語言寫的程序可移植性好。但是,C語言對(duì)程序員要求也高,程序員用C寫程序會(huì)感到限制少、靈活性大,功能強(qiáng),但較其他高級(jí)語言在學(xué)習(xí)上要困難ー些。C語言的字符集:字符是組成語言的最基本的元素。C語言字符集由字母,數(shù)字,空格,標(biāo)點(diǎn)和特殊字符組成。在字符常量,字符串常量和注釋中還可以使用漢字或其它可表示的圖形符號(hào)。1.字母小寫字母a?z共26個(gè)大寫字母A?Z共26個(gè)2.數(shù)字〇?9共10個(gè).空白符空格符、制表符、換行符等統(tǒng)稱為空白符?？瞻追辉谧址Ａ亢妥址Ａ恐衅鹱饔谩Ｔ谄渌胤匠霈F(xiàn)時(shí),只起間隔作用,編譯程序?qū)λ鼈兒雎圆挥?jì)。因此在程序真的不掉線嗎??、?？？？？？？？？？？？中使用空白符與否,對(duì)程序的編譯不發(fā)生影響,但在程序中適當(dāng)?shù)牡胤绞褂每瞻追麑⒃黾映绦虻那逦院涂勺x性。.標(biāo)點(diǎn)和特殊字符C語言詞匯:在C語言中使用的詞匯分為六類:標(biāo)識(shí)符,關(guān)鍵字,運(yùn)算符,分隔符,常量,注釋符等。1.標(biāo)識(shí)符在程序中使用的變量名、函數(shù)名、標(biāo)號(hào)等統(tǒng)稱為標(biāo)識(shí)符。除庫函數(shù)的函數(shù)名由系統(tǒng)定義外,其余都由用戶自定義。C規(guī)定,標(biāo)識(shí)符只能是字母（A?Z,a?z）、數(shù)字（〇?9）、下劃線。組成的字符串,并且其第一個(gè)字符必須是字母或下劃線。以下標(biāo)識(shí)符是合法的:a,x,x3,BOOK_1,sum5以下標(biāo)識(shí)符是非法的:3s 以數(shù)字開頭s*T 出現(xiàn)非法字符?-3x 以減號(hào)開頭bowy-1出現(xiàn)非法字符-（減號(hào)）在使用標(biāo)識(shí)符時(shí)還必須注意以下幾點(diǎn):⑴標(biāo)準(zhǔn)C不限制標(biāo)識(shí)符的長度,但它受各種版本的C語言編譯系統(tǒng)限制,同時(shí)也受到具體機(jī)器的限制。例如在某版本C中規(guī)定標(biāo)識(shí)符前八位有效,當(dāng)兩個(gè)標(biāo)識(shí)符前ハ位相同時(shí),則被認(rèn)為是同一個(gè)標(biāo)識(shí)符。(2)在標(biāo)識(shí)符中,大小寫是有區(qū)別的。例如BOOK和book是兩個(gè)不同的標(biāo)識(shí)符。(3)標(biāo)識(shí)符雖然可由程序員隨意定義,但標(biāo)識(shí)符是用于標(biāo)識(shí)某個(gè)量的符號(hào)。因此,命名應(yīng)盡量有相應(yīng)的意義,以便于閱讀理解,作到“顧名思義”。2.關(guān)鍵字關(guān)鍵字是由C語言規(guī)定的具有特定意義的字符串,通常也稱為保留字。用戶定義的標(biāo)識(shí)符不應(yīng)與關(guān)鍵字相同。C語言的關(guān)鍵字分為以下幾類:⑴類型說明符用于定義、說明變量、函數(shù)或其它數(shù)據(jù)結(jié)構(gòu)的類型。如前面例題中用到的int,double等⑵語句定義符用于表示一個(gè)語句的功能。如例1.3中用到的ifelse就是條件語句的語句定義符。⑶預(yù)處理命令字用于表示一個(gè)預(yù)處理命令。如前面各例中用到的include..運(yùn)算符C語言中含有相當(dāng)豐富的運(yùn)算符。運(yùn)算符與變量,函數(shù)一起組成表達(dá)式,表示各種運(yùn)算功能。運(yùn)算符由ー個(gè)或多個(gè)字符組成。.分隔符在C語言中采用的分隔符有逗號(hào)和空格兩種。逗號(hào)主要用在類型說明和函數(shù)參數(shù)表中,分隔各個(gè)變量?？崭穸嘤糜谡Z句各單詞之間,作間隔符。在關(guān)鍵字,標(biāo)識(shí)符之間必須要有一個(gè)以上的空格符作間隔,否則將會(huì)出現(xiàn)語法錯(cuò)誤,例如把inta;寫成inta;C編譯器會(huì)把inta真的不掉線嗎ワ????????????當(dāng)成一個(gè)標(biāo)識(shí)符處理,其結(jié)果必然出錯(cuò)。.常量C語言中使用的常量可分為數(shù)字常量、字符常量、字符串常量、符號(hào)常量、轉(zhuǎn)義字符等多種。在后面章節(jié)中將專門給予介紹。.注釋符C語言的注釋符是以“/*”開頭并以“*/”結(jié)尾的串。在“/*”和“*/”之間的即為注釋。程序編譯時(shí),不對(duì)注釋作任何處理。注釋可出現(xiàn)在程序中的任何位置。注釋用來向用戶提示或解釋程序的意義。在調(diào)試程序中對(duì)暫不使用的語句也可用注釋符括起來,使翻譯跳過不作處理,待調(diào)試結(jié)束后再去掉注釋符。3.3軟件工程方法論的應(yīng)用軟件工程是指導(dǎo)計(jì)算機(jī)軟件開發(fā)和維護(hù)的工程學(xué),采用工程的概念、原理、技術(shù)、和方法開發(fā)與維護(hù)軟件,把經(jīng)過時(shí)間考驗(yàn)而證明正確的管理技術(shù)和當(dāng)前能夠得到的最好的技術(shù)方法結(jié)合起來。自從1968年在聯(lián)邦德國召開的國際會(huì)議上正式提出并使用了“軟件工程”這個(gè)術(shù)語以來,研究軟件工程的專家學(xué)者們陸續(xù)提出了100多條關(guān)于軟件工程的準(zhǔn)則或“信條”。著名的軟件工程專家B.W.Boehm綜合這些學(xué)者們的意見并總結(jié)了TRW公司多年開發(fā)軟件的經(jīng)驗(yàn),于!983年在ー篇論文中提出軟件工程的七條原理。他認(rèn)為這七條原理是確保軟件產(chǎn)品質(zhì)量和開發(fā)效率的原理的最小集合。這七條原理是互相獨(dú)立的,其中任意六條原理的組合都不能代替另一條原理,因此,它們是缺ー不可的最小集合,然而這七條原理又是相當(dāng)完備的,人們雖然不能用數(shù)學(xué)方法嚴(yán)格證明它們是一個(gè)完備的集合,但是,可以證明去此之前已經(jīng)提出的100多條軟件工程原理都可以由這七條原理的任意組合蘊(yùn)含或派生。?用分階段的生命周期計(jì)劃嚴(yán)格管理經(jīng)統(tǒng)計(jì)表明,不成功的軟件項(xiàng)目中有一半左右是由于計(jì)劃不周造成的。Boehm認(rèn)為,在軟件的整個(gè)生命周期中應(yīng)制定并嚴(yán)格執(zhí)行六類計(jì)劃:項(xiàng)目概要計(jì)劃、里程碑計(jì)劃、項(xiàng)目控制計(jì)劃、產(chǎn)品控制計(jì)劃、驗(yàn)證計(jì)劃、運(yùn)行維護(hù)計(jì)劃?堅(jiān)持進(jìn)行階段評(píng)審大部分錯(cuò)誤是在編碼之前造成的錯(cuò)誤發(fā)現(xiàn)與改正得越晚,所需付出的代價(jià)越高。因此,在每個(gè)階段都進(jìn)行嚴(yán)格的評(píng)審,以便盡早發(fā)現(xiàn)在軟件開發(fā)過程的錯(cuò)誤實(shí)行嚴(yán)格的產(chǎn)品控制在軟件開發(fā)過程中不要隨意改變需求,因?yàn)楦淖兡稠?xiàng)需求往往需要付出較高的代價(jià),但在實(shí)踐中用戶往往會(huì)提出需求變更,因此需要采取科學(xué)的產(chǎn)品控制技術(shù)。目前主要實(shí)行基準(zhǔn)配置管理:基準(zhǔn)配置是指經(jīng)過階段評(píng)審后的軟件配置成分,如各個(gè)階段產(chǎn)生的文檔或程序代碼。對(duì)涉及基準(zhǔn)配置的修改,必須經(jīng)過嚴(yán)格的評(píng)審,通過后才能實(shí)施修改。采用現(xiàn)代程序設(shè)計(jì)技術(shù)實(shí)踐表明:釆用先進(jìn)的技術(shù)既可提高軟件開發(fā)的效率,又可提高軟件維護(hù)的效率。80年代及之前：結(jié)構(gòu)化分析、設(shè)計(jì)技術(shù)90年代：面向?qū)ο蠓治?、設(shè)計(jì)技術(shù)結(jié)果應(yīng)能清楚地審查軟件產(chǎn)品是看不見、摸不著的邏輯產(chǎn)品,開發(fā)過程難以評(píng)價(jià)和管理。真的不掉線嗎つ、 ????????????根據(jù)軟件開發(fā)項(xiàng)目的總目標(biāo)及完成期限,規(guī)定開發(fā)組織的責(zé)任和產(chǎn)品標(biāo)準(zhǔn),使所得的結(jié)果能夠清楚地審查開發(fā)小組的人員應(yīng)該少而精開發(fā)小組人員的素質(zhì)和數(shù)量是影響軟件產(chǎn)品質(zhì)量和開發(fā)效率的重要因素。開發(fā)小組人員數(shù)目的增加,使相互交流復(fù)雜、費(fèi)用增加。承認(rèn)不斷改進(jìn)軟件工程實(shí)踐的必要性遵循前6條基本原理,就能夠按照當(dāng)代軟件工程基本原理實(shí)現(xiàn)軟件的工程化生產(chǎn),但不能保證趕上時(shí)代前進(jìn)的步伐。積極主動(dòng)采納新的軟件技術(shù),且不斷總結(jié)經(jīng)驗(yàn)軟件工程的傳統(tǒng)途徑是“生命周期法”,強(qiáng)調(diào)“結(jié)構(gòu)化分析、結(jié)構(gòu)化設(shè)計(jì)”。(1)“生命周期法”的起源人類解決復(fù)雜問題時(shí)普遍釆用的ー個(gè)策略是“各個(gè)擊破”,也就是對(duì)問題進(jìn)行分解,然后再分別解決各個(gè)子問題的策略。軟件工程采用的“生命周期法”,就是從時(shí)間角度對(duì)軟件開發(fā)和維護(hù)的復(fù)雜問題進(jìn)行分解,把軟件生存的漫長周期依次劃分為若干個(gè)階段,每個(gè)階段有相對(duì)獨(dú)立的任務(wù),然后再逐步完成每個(gè)階段的任務(wù)。(2)生命周期劃分的原則各階段的任務(wù)彼此間盡可能相對(duì)獨(dú)立,同一個(gè)階段各項(xiàng)任務(wù)的性質(zhì)盡可能相同,從而降低每個(gè)階段任務(wù)的復(fù)雜性,簡化不同階段之間的聯(lián)系,有利于軟件開發(fā)過程的組織管理。(3)生命周期的劃分軟件生命周期一般分為:軟件定義(問題定義、可行性研究、需求分析)、軟件開發(fā)(總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼和單元測試、綜合測試)、軟件維護(hù)等三個(gè)時(shí)期。軟件工程各階段的基本任務(wù)?問題定義:問題定義階段需要回答的關(guān)鍵問題是:“有解決的問題是什么?”通過問題定義階段的工作,系統(tǒng)分析員應(yīng)該提出關(guān)于問題性質(zhì)、工程目標(biāo)和規(guī)模的書面報(bào)告。通過對(duì)實(shí)際用戶和使用部門負(fù)責(zé)人的訪問調(diào)查,分析員扼要地寫出他對(duì)問題的理解,并在用戶和使用部門負(fù)責(zé)人的會(huì)議上認(rèn)真討論這份書面報(bào)告,澄清含糊不清的地方,改正理解不正確的地方,最后得到ー份雙方都滿意的文檔。?可行性研究這個(gè)階段要回答的關(guān)鍵問題是：“對(duì)于上一個(gè)階段所確定的問題有行的通的解決方法嗎?”在問題定義階段提出的對(duì)工程目標(biāo)和規(guī)模的報(bào)告通常比較模糊。可行性研究階段應(yīng)該導(dǎo)出系統(tǒng)的高層邏輯模型（通常用數(shù)據(jù)流圖表示）,并且在此基礎(chǔ)上更準(zhǔn)確、更具體地確定工程規(guī)模和目標(biāo)。然后分析員更準(zhǔn)確地估計(jì)系統(tǒng)的成本和效益,對(duì)建議的系統(tǒng)進(jìn)行仔細(xì)的成本/效益分析。?需求分析這個(gè)階段的任務(wù)是“為了解決這個(gè)問題,目標(biāo)系統(tǒng)必須做什么”,主要是確定目標(biāo)系統(tǒng)必須具備哪些功能。在需求分析階段確定的系統(tǒng)邏輯模型是以后設(shè)計(jì)和實(shí)現(xiàn)目標(biāo)系統(tǒng)的基礎(chǔ),因此必須準(zhǔn)確完整地體現(xiàn)用戶的要求。該階段有寫的文檔有規(guī)格說明書、初步的用戶使用手冊(cè)、系統(tǒng)功能框架圖等。?總體設(shè)計(jì)真的不掉線嗎??、?？？？？？？？？？？？這個(gè)階段要回答的關(guān)鍵問題是:“概括地說,應(yīng)該如何解決這個(gè)問題?”首先應(yīng)該考慮幾種可能的解決方案。例如,目標(biāo)系統(tǒng)的ー些主要功能是用計(jì)算機(jī)自動(dòng)完成還是用人工完成。通常至少考慮下述幾類可能的方案:低成本解決方案、中等成本的解決方案和高成本的“十全十美”的系統(tǒng)。系統(tǒng)分析員應(yīng)該使用系統(tǒng)流程圖或者其他工具描述每種可能的系統(tǒng)。?詳細(xì)設(shè)計(jì)總體設(shè)計(jì)階段以比較抽象概括的方式提出了解決問題的方法。詳細(xì)設(shè)計(jì)階段的任務(wù)就好似把解決方法具體化,也就是回答下面這個(gè)關(guān)鍵問題:“應(yīng)該怎樣具體地實(shí)現(xiàn)這個(gè)系統(tǒng)呢?”這個(gè)階段的任務(wù)還不是編寫程序,而是設(shè)計(jì)出程序的詳細(xì)規(guī)格說明。通常用HIPO圖（層次圖加輸入/處理/輸出圖）或PDL語言（過程設(shè)計(jì)語言）描述詳細(xì)的結(jié)果。該階段要產(chǎn)生的文檔有偽代碼、詳細(xì)的測試計(jì)劃、最終的用戶使用手冊(cè)等。?編碼和單元測試這個(gè)階段的關(guān)鍵任務(wù)是寫出正確的容易理解、容易維護(hù)的程序模決。程序員應(yīng)該根據(jù)目標(biāo)系統(tǒng)的性質(zhì)和實(shí)際環(huán)境,選取ー種適當(dāng)?shù)母呒?jí)程序設(shè)計(jì)語言,把詳細(xì)設(shè)計(jì)的結(jié)果翻譯成用選定的語言書寫的程序,并且仔細(xì)測試編寫出的每一個(gè)模塊。?綜合測試這個(gè)階段的主要任務(wù)是通過各種類型的測試（及相應(yīng)的調(diào)試）使軟件達(dá)到預(yù)定的要求。最基本的測試是集成測試和驗(yàn)收測試。所謂集成測試是根據(jù)設(shè)計(jì)的軟件結(jié)構(gòu),把經(jīng)過單元測試檢驗(yàn)的模塊按某種選定的策略裝備起來,在裝配過程中對(duì)程序進(jìn)行必要的測試。所謂驗(yàn)收測試是按照規(guī)格說明書的規(guī)定（通常在需求分析階段確定）,有用戶（或在用戶的積極參加下）對(duì)目標(biāo)系統(tǒng)進(jìn)行驗(yàn)收。?軟件維護(hù)軟件維護(hù)階段的關(guān)鍵任務(wù)是,通過各種必要的維護(hù)活動(dòng)是系統(tǒng)持久地滿足用戶的需要。通常有四類維護(hù)活動(dòng):改正性維護(hù),有就是診斷和改正在使用過程中發(fā)現(xiàn)的軟件錯(cuò)誤;適應(yīng)性維護(hù),即修改軟件以適應(yīng)環(huán)境的變化;完善性維護(hù),即根據(jù)用戶的要求改進(jìn)或擴(kuò)充軟件是它更完善;預(yù)防性維護(hù)，即修改軟件為將來的維護(hù)活動(dòng)預(yù)先做準(zhǔn)備。每ー項(xiàng)維護(hù)活動(dòng)都應(yīng)該準(zhǔn)確地記錄下來,作為正式的文檔加以保存。3.4詞法語法分析簡介

詞法分析的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序,對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解,從而識(shí)別出一個(gè)個(gè)的單詞（也稱單詞符號(hào)或符號(hào)）。這里所謂的單詞是指邏輯上緊密相連的一組字符,這些字符具有集體含義。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語,如“程序”，“語句”，“表達(dá)式”等等,即判斷單詞序列是否符合組成各類語法短語的組成規(guī)則,一般這種語法短語,也稱為語法單位,可表示成語法樹。3.5詞法需求分析簡介詞法分析階級(jí)是編譯過程的第一個(gè)階級(jí)。這個(gè)階級(jí)的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序,對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解,從而識(shí)別ー個(gè)個(gè)單詞（也稱為單詞符號(hào)或符號(hào)）.這里所謂的單詞是指邏輯上緊密相連的ー組字符,這些字符具有集體含義。比如標(biāo)識(shí)是由字母開頭,后跟字母、數(shù)字字符序列組成的ー種單詞,。保留字是ー種單詞,此外還有算符,界符等等。真的不掉線嗎??、?？？？？？？？？？？？詞法分析器的主要任務(wù)是讀入輸入字符，產(chǎn)生記號(hào)序列,提交給語法分析使用。詞法分析器與語法分析器之間的交互如下圖:

詞法分析器源程序 記號(hào)取下ー個(gè)字符1.剔除空白符和注釋1.剔除空白符和注釋詞法分析器讀入輸入串,將其轉(zhuǎn)換成將被語法分析器分析的記號(hào)流。許多語言允許“空白符”（空格,制表符或者換行符）出現(xiàn)在記號(hào)之間。原程序中的注釋一般都被語法分析器和翻譯器忽略,所以他們也可以看成空白符。常數(shù)在ー個(gè)表達(dá)式中,任何ー個(gè)允許單個(gè)數(shù)字出現(xiàn)的位置都應(yīng)該允許任何整型常數(shù)出現(xiàn)。由于翻譯期間把數(shù)作為ー個(gè)單元來處理,收集數(shù)字形成整數(shù)這一任務(wù)一般由詞法分析器完成。識(shí)別標(biāo)識(shí)符和關(guān)鍵字保留關(guān)鍵字的集合可以通過適當(dāng)?shù)爻跏蓟?hào)表而得到正確的處理。實(shí)現(xiàn)詞法分析器的接口在詞法分析中,使用術(shù)語“記號(hào)”，“模式”，“詞素”表示特定含義。記號(hào)包括:關(guān)鍵字、標(biāo)識(shí)符、操作符、常量、文字串、和標(biāo)點(diǎn)符號(hào)。詞法分析器把與記號(hào)有關(guān)的信息收集在記號(hào)的屬性中。記號(hào)影響語法分析,而屬性影響記號(hào)的翻譯。在實(shí)際實(shí)現(xiàn)時(shí),記號(hào)通常只有一個(gè)屬性,即指向符號(hào)表中一個(gè)表項(xiàng)的指針,與記號(hào)有關(guān)的信息保存在這個(gè)詞素第一次出現(xiàn)的行為。這些信息存儲(chǔ)在符號(hào)表中該標(biāo)識(shí)符對(duì)應(yīng)的表項(xiàng)內(nèi)。記號(hào)的命名規(guī)則:正規(guī)表達(dá)式建立正規(guī)表達(dá)式時(shí),可以先定義簡單的正規(guī)表達(dá)式,然后用它們構(gòu)造出更復(fù)雜的正規(guī)表達(dá)式。每個(gè)表達(dá)式r表示ー個(gè)語言L(R)。記號(hào)的識(shí)別:狀態(tài)轉(zhuǎn)換圖3.6語法需求分析簡介語法分析是編譯過程的第二個(gè)階級(jí)。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語,如“程序”，“語句”，“表達(dá)式”等等。一般這種語法短語,也稱為語法單位,可表示成語法樹。語法分析所依據(jù)的是語言的語法規(guī)則,即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序。詞法分析和語法分析本質(zhì)上都是對(duì)源程序的結(jié)構(gòu)進(jìn)行分析。但詞法分析的任務(wù)僅對(duì)源程序進(jìn)行線性掃描即可完成,比如識(shí)別標(biāo)識(shí)符,因?yàn)闃?biāo)識(shí)符的結(jié)構(gòu)是字母打頭的字母和數(shù)字序列,這只要順序掃描輸入流,遇到既不是字母又不是數(shù)字字符時(shí),將前面所真的不掉線嗎??ヽ?？？？？？？？？？？？

發(fā)現(xiàn)的所有字母和數(shù)字組合在ー起而構(gòu)成單詞標(biāo)識(shí)符。但這種線性掃描則不能用于識(shí)別遞歸定義的語法成分,比如就不能用此辦法去匹配表達(dá)式中的括號(hào)。語法分析的任務(wù)是語法分析器接收詞法分析研究器提供的記號(hào)串,檢查它們是否能由源程序的文法產(chǎn)生,語法分析器在編譯器中的位置如圖所示:源程序中間表示記號(hào)語法分析器語法樹取下ー個(gè)記號(hào)源程序中間表示記號(hào)語法分析器語法樹取下ー個(gè)記號(hào)典型的文法的語法分析器有三類:ー類是通用的語法分析方法,如Cocke-Younger-Kasami算法和Early算法,這些方法在生成編譯器時(shí)效率太低。編譯器常用的是自頂向下和自底向上的方法。采用自頂向下的遞歸子程序法,就是對(duì)應(yīng)每個(gè)非終結(jié)符語法單元,編ー個(gè)獨(dú)立的處理子程序。語法分析從讀入第一個(gè)單詞開始,由非終結(jié)符即開始符出發(fā),沿語法描述圖箭頭指出的方向進(jìn)行分析。當(dāng)遇到非終結(jié)符時(shí),則調(diào)用相應(yīng)的處理子程序,從語法描述圖看也就進(jìn)入了一個(gè)語法單元,再沿當(dāng)前所進(jìn)入的語法描述圖的箭頭方向進(jìn)行分析,當(dāng)遇到終結(jié)符時(shí),則判斷當(dāng)前讀入的單詞是否與圖中的終結(jié)符相匹配,若匹配,則執(zhí)行相應(yīng)的語義程序。再讀取下一個(gè)單詞繼續(xù)分析。遇到分支點(diǎn)時(shí)將當(dāng)前的單詞與分支點(diǎn)上的多個(gè)終結(jié)符逐個(gè)相比較,若都不匹配時(shí)可能是進(jìn)入下ー非終結(jié)符語法單位或是出錯(cuò)。

在編譯程序中符號(hào)表用來存放語言中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息,這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。在詞法分析及語法分析過程中不斷積累和更新表中的信息,并在詞法分析到代碼生成和各階段,按各自的需要從表中獲得不同的屬性信息。不論編譯策略是否分趟,符號(hào)表的作用和地位是完全一致的。符號(hào)表的功能主要有:?收集符號(hào)屬性:在分析語言程序中標(biāo)識(shí)符說明部分時(shí),編譯程序根據(jù)說明信息收集有關(guān)標(biāo)識(shí)符的屬性,并在符號(hào)表中建立符號(hào)的相應(yīng)屬性信息。?上下文語義的合法性檢查的依據(jù):同一個(gè)標(biāo)識(shí)符可能在程序和不同地方出現(xiàn),而有關(guān)該符號(hào)和屬性是在不同情況下收集的,特別是在多趟編譯及程序分段編譯的情況下,更需檢查標(biāo)識(shí)符屬性在上下文中的一致性和全法性。通過符號(hào)表中屬性記錄可進(jìn)行這些語義檢查。作為目標(biāo)代碼生成階段地址分配的依據(jù):除語言中規(guī)定的臨時(shí)分配存儲(chǔ)的變量外,每個(gè)符號(hào)變量在目標(biāo)代碼生成時(shí)需要確定其在存儲(chǔ)分配的位置。語言程序中的符號(hào)變量由它被定義的存儲(chǔ)類別或被定義的位置來確定。首先要確定其被分配的區(qū)域。真的不掉線嗎??ヽ?？？？？？？？？？？？其次是根據(jù)變量出現(xiàn)的次序。在編譯程序中符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息,這些信息集中反映了標(biāo)識(shí)符的語義特征屬性。在詞法分析及語法分析過程中不斷積累和更新表中的信息,并在詞法分析到代碼生成的各階段,按各自的需要從表中獲取不同的屬性信息。不論編譯策略是否分M,符號(hào)表的作用和地位是完全一致的。符號(hào)表的功能主要有:收集符號(hào)屬性:在分析語言程序中標(biāo)識(shí)符說明部分時(shí),編譯程序根據(jù)說明信息收集有關(guān)標(biāo)識(shí)符的屬性,并在符號(hào)表中建立符號(hào)的相應(yīng)屬性信息。下文語義的合法性檢查的依據(jù):同一個(gè)標(biāo)識(shí)符可能在程序和不同地方出現(xiàn),而有關(guān)該符號(hào)和屬性是在不同情況下收集的,特別是在多趟編譯及程序分段編譯的情況下,更需檢查標(biāo)識(shí)符屬性在上下文中的一致性和全法性。通過符號(hào)表中屬性記錄可進(jìn)行這些語義檢查。作為目標(biāo)代碼生成階段地址分配的依據(jù):除語言中規(guī)定的臨時(shí)分配存儲(chǔ)的變量外,每個(gè)符號(hào)變量在目標(biāo)代碼生成時(shí)需要確定其在存儲(chǔ)分配的位置。語言程序中的符號(hào)變量由它被定義的存儲(chǔ)類別或被定義的位置來確定。首先要確定其被分配的區(qū)域。其次是根據(jù)變量出現(xiàn)的次序。語言符號(hào)可分為關(guān)鍵字（保留字）符號(hào),操作符號(hào)幾標(biāo)識(shí)符號(hào)。他們之間的主要屬性有較大的差別。因此通常為他們建立不同的符號(hào)表。4系統(tǒng)設(shè)計(jì)編譯程序的功能圖如下:高級(jí)語言程序ズ嘛程序）低級(jí)語言（目標(biāo)語言）ー個(gè)編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算機(jī)用戶不必考慮與機(jī)器的煩瑣細(xì)節(jié),使程序員和程序設(shè)計(jì)獨(dú)立于機(jī)器,這對(duì)于當(dāng)今機(jī)器的數(shù)量和種類持續(xù)不斷地增長的年代真的不掉線嗎??、?？？？？？？？？？？？尤為重要。1系統(tǒng)設(shè)計(jì)總體流程圖調(diào)用Read_File（）把源程序調(diào)入到內(nèi)存4.2語法分析體流程圖真的不掉線嗎??、?？？？？？？？？？？？遞歸調(diào)用Programme()4.3語法分析概要設(shè)計(jì)語法分析是編譯過程的核心部分,語法分析的任務(wù)是:按照文法,從源程序符號(hào)串中識(shí)別出各類語法成分,同時(shí)進(jìn)行語法檢查,為語義分析和代碼生成做準(zhǔn)備。語法分析設(shè)計(jì)采用遞歸下降分析法,遞歸下降分析技術(shù)是ー種無回溯的自頂向下分析技術(shù),它的實(shí)現(xiàn)思想是:讓ー個(gè)識(shí)別符程序由一組子程序組成,其中每ー個(gè)子程序?qū)?yīng)于文法的ー個(gè)非終結(jié)符;根據(jù)文法的遞歸定義,這些子程序往往是遞歸子程序。這種技術(shù)稱為遞歸下降技術(shù),相應(yīng)的識(shí)別程序稱為遞歸下降識(shí)別程序〇在遞歸下降識(shí)別程序中的每ー個(gè)子程序都對(duì)應(yīng)于文法的一個(gè)非終結(jié)符,更確切地說為各個(gè)非終結(jié)符設(shè)計(jì)一個(gè)子程序,每ー個(gè)子程序分析相對(duì)于相應(yīng)非終結(jié)符短語。例如,當(dāng)進(jìn)入關(guān)于非終結(jié)符真的不號(hào)〈語句〉的遞歸子程序時(shí),便期待句子中出現(xiàn)相對(duì)于〈語句〉的短語,這時(shí)必要的是讓識(shí)別程序邏輯知道句子中正期待短語的位置。遞歸下降分析技術(shù)是面向目標(biāo)的,這個(gè)目標(biāo)是子程序所相應(yīng)的非終結(jié)符號(hào),也是預(yù)測的,預(yù)言能找到這個(gè)相對(duì)于該非終結(jié)符號(hào)的短語。C語言的語法分析EBNF如下:く程序) ［く宏定義)］［く頭文件》］く主函數(shù)(main)＞［く子函數(shù)〉］く主函數(shù)(main)》 ［〈變量說明部分〉］［く常量說明部分〉］［く子函數(shù)調(diào)用〉］く語句〉く常量說明部分〉 CONSTく常量定義〉しく常量定義〉｝;く常量定義〉 く標(biāo)識(shí)符〉=く整型常量〉く整型常量〉 ［+1Tく數(shù)字〉｛く數(shù)字〉｝く變量說明部分〉 く類型說明〉く標(biāo)識(shí)符〉しく標(biāo)識(shí)符〉｝;

く類型說明》intIflaotIdoublelcharく類型說明》intIflaotIdoublelcharく標(biāo)識(shí)符》 く字母》｛く字母〉Iく數(shù)字〉｝く語句〉 く賦值語句〉Iく條件語句〉Iく循環(huán)語句〉Iく子函數(shù)調(diào)用語句〉丨く輸入語句〉Iく輸出語句〉く賦值語句〉 く標(biāo)識(shí)符〉=く表達(dá)式〉く條件〉く表達(dá)式〉く關(guān)系運(yùn)算符〉く表達(dá)式〉I!く表達(dá)式〉く循環(huán)語句〉<F0R循環(huán)語句〉（<WHILE循環(huán)語句〉|くDO-WHILE循環(huán)語句〉くFOR循環(huán)語句〉 forぐ［賦值語句］"表達(dá)式］';，［條件語句］'）'<WHILE循環(huán)語句〉 whi1グぐく條件〉リ，く語句〉くdo-while^t環(huán)語句〉 def｛」く語句〉,｝,while，（，く條件〉，），く函數(shù)調(diào)用語句） く函數(shù)名〉ヤ［く變量說明〉］'）'く輸入語句〉 scanf，（，く輸入類型聲明〉?く標(biāo)識(shí)符〉'）"；’く輸出語句〉 prints（，く輸出類型聲明〉く標(biāo)識(shí)符〉，）'，；'く輸出類型聲明〉 %d|%c|%sく表達(dá)式〉 ［+ITく項(xiàng)〉く加減法運(yùn)算符X項(xiàng)〉く項(xiàng)〉 く因子X乘除法運(yùn)算符X因子〉く因子〉 く標(biāo)識(shí)符〉Iく無符號(hào)整數(shù)〉I'（'く表達(dá)式〉’）'く加減法運(yùn)算符〉 +|~く乘除法運(yùn)算符〉 ?1/く關(guān)系運(yùn)算符〉 ==|<|<=|>|>=|!=く條件語句〉 ifく條件X語句〉elseく語句）く字母) a|b|……|A|B|……IZく數(shù)字〉 0111……19用C語言實(shí)現(xiàn)遞歸下降分析程序如下:voidError0main()(Constant();Variable();Call-sentence0;Sentence();真的不掉線嗎??、?？？？？？？？？？？？Constant()/?常量說明部分?/if(const)Constant-define();Constant-define()/?常量定義?/Integer-content0;/?整型常量?/)Variable() /?變量說明部分?/(if(類型說明)定義標(biāo)識(shí)符;)Sentence() /?語句?/if(!Set.value.sentence())if(!Condition.sentence0)

if(ICircle.sentence())

if(ICall.sentence0)

if(Iprintf)

if(!scanf)returnError();Set-value.sentence0Identifer();/?標(biāo)識(shí)符?/Expression();/?表達(dá)式?/Condition0 /?條件?/|Expression();Relation-symbol(); /?關(guān)系運(yùn)算符?/Expression();)Circle-sentence() /?循環(huán)語句?/(for語句();真的不掉線嗎??、?？？？？？？？？？？？do-while語句();)Call.sentence() /?函數(shù)調(diào)用語句?/(Function.Identifer(); /?函數(shù)名?/)Expression() /?表達(dá)式*/(if(+l-)Math-symbol0; /?算數(shù)運(yùn)算符?/Item();)Item() /?項(xiàng)?/(Factor0;Math-symbol();Factor();)Factor0/?因子?/Integer;If00)Expression();If(グ)Get-next-word0;)Math-symbol()(if(Math-symbol())Relation-symbol0;if(Relation-symbol0)Get.next-word0;Condition-sentence()/?條件語句?/if(if){ifC(')真的不掉線嗎ツ? ????????????Expression();if0)りSentence();}if(else)Sentence();)4.4目標(biāo)代碼的分析代碼生成概要:?代碼生成的基礎(chǔ)是用目標(biāo)代碼段系統(tǒng)地替換AST的結(jié)點(diǎn)和子樹,用這種方法可以保持語義緊接著是ー個(gè)線性代階段,從重寫的AST產(chǎn)生一個(gè)線性指令序列。替換過程被稱為樹重寫。線性化由目標(biāo)代碼段和數(shù)據(jù)流和控制流需求控制。代碼生成中的三個(gè)主要問題是代碼選擇、寄存器分配和指令排序。一般情況下,發(fā)現(xiàn)最優(yōu)組合是NP完全的。有三個(gè)方法簡化代碼生成問:1每次只考慮AST的一小部分;2簡化目標(biāo)機(jī);3限制代碼段之間的接口。代碼生成分三個(gè)階段進(jìn)行:1預(yù)處理,通過程序轉(zhuǎn)換,有些AST結(jié)點(diǎn)模式被其他AST結(jié)點(diǎn)模式替換;2正確代碼生成,通過樹重寫,所有AST結(jié)點(diǎn)模式被目標(biāo)代碼序列替換;3后處理,通過窺孔優(yōu)化,有些目標(biāo)代碼序列被其他目標(biāo)代碼序列替換。?預(yù)處理和后處理可能反復(fù)執(zhí)行?得到代碼最簡單的方法是為AST的每個(gè)結(jié)點(diǎn)生成代碼段,由迭代解釋程序?yàn)槠鋱?zhí)行。如果目標(biāo)代碼為C或C++,所有優(yōu)化都可能留給C或C++編譯程序。這個(gè)過程用最小的投入使解釋程序變?yōu)榫幾g程序。?可以生成對(duì)庫中簡單拷貝的例程調(diào)用,而不是多次重復(fù)ー個(gè)代碼段,這可以相當(dāng)可觀地減小目標(biāo)代碼的長度。這個(gè)技術(shù)被稱為線程代碼。目標(biāo)代碼長度的減少對(duì)嵌入式系統(tǒng)可能是重要的。?通過將庫例程編號(hào)并且將程序存儲(chǔ)為這些編號(hào)數(shù)的ー個(gè)列表可以大大減小目標(biāo)代碼長度。所有目標(biāo)機(jī)依賴現(xiàn)在集中于庫例程中。?在其他方向,每ー個(gè)重復(fù)的代碼段可能在它們的上下文中被部分求值,從而導(dǎo)致更有效的代碼。?在簡單代碼生成中,為每個(gè)可能的結(jié)點(diǎn)類型選擇了到目標(biāo)代碼的固定翻譯。這些翻譯基于共同的接口規(guī)定。?簡單代碼生成只需局部判定,因此尤其適合窄編譯程序。?寄存器機(jī)的簡單代碼生成用機(jī)器指令重寫每個(gè)表達(dá)式結(jié)點(diǎn),這滿足了代碼選擇的需要。接口規(guī)定是:一條指令的輸出寄存器必要性須即用作父母指令的輸入寄存器。?寄存器機(jī)上的表達(dá)式的代碼可以通過深度優(yōu)先遞歸訪問生成,這滿足了指令排序的需要。遞歸例程攜帶兩個(gè)額外的參數(shù),結(jié)果必須傳入其中的寄存器和空閑寄存器集,這滿足了寄存器分配的需要。?因?yàn)槊總€(gè)沒有處理的操作數(shù)都占用了一個(gè)寄存器,為需要最多寄存器的操作數(shù)首先編譯代碼是有利的。這要求可以在深度優(yōu)先訪問中計(jì)算結(jié)點(diǎn)的權(quán)。當(dāng)ー個(gè)表達(dá)式需要的寄存器多于可用的寄存器時(shí),我們需要溢出ー個(gè)和多個(gè)寄存真的不掉線嗎??ヽ?？？？？？？？？？？？?器至存儲(chǔ)器。沒有最好的寄存器溢出技術(shù),除非進(jìn)行全面的研究。因此我們求助于啟發(fā)式算法。?在ー個(gè)啟發(fā)式算法中,我們分離出可以用可用寄存器編譯的最大子表達(dá)式,編譯它們,將結(jié)果存儲(chǔ)進(jìn)臨時(shí)變量。變減小了原始樹,我們對(duì)其重復(fù)這個(gè)過程。?機(jī)器寄存器被編譯程序設(shè)計(jì)者分為四組:為管理目的所需的、為參數(shù)傳遞保留的、為表達(dá)式求值保留的和用于存儲(chǔ)局部變量的。通常情況下,每個(gè)集合的大小是固定,并且有些集合可能是空的。?通常情況下,為局部變量保留的寄存器集比候選集要小。啟發(fā)式算法包括先來先服務(wù)、來自程序員的寄存器提示以及從靜態(tài)或動(dòng)態(tài)簡要表得的使用計(jì)數(shù)。更高級(jí)的啟發(fā)算法使用圖著色。?棧上的編譯用符號(hào)解釋的編譯有些類似于符號(hào)解釋。在后者中,我們保持符號(hào)表示法,但現(xiàn)在我們包括棧和寄存器,更重要的是,這一次,表示法中的信息必須精確。這種表示法被稱為寄變描述符。?如果結(jié)點(diǎn)的效果可以精確存儲(chǔ)于寄變描述符中,我們就這樣做。沒有為結(jié)點(diǎn)生成代碼,但其語義保留在寄變描述符中:舊寄變描述+結(jié)點(diǎn)?如呆結(jié)點(diǎn)的效果使我們不能精確地在寄變描述符中保留信息,我們生成代碼以獲得效果并且在寄變描述符中記錄結(jié)果。因此語義被保留于結(jié)點(diǎn)的重寫中。?如果從活躍分析中得到可用信息,當(dāng)離開其活躍范圍時(shí),我們可以從寄變描述符中刪除關(guān)于變量的所有信息。?基本塊為控制圖的最大部分,它不包含分裂和結(jié)合?；緣K是從標(biāo)號(hào)或從例程的開頭開始,正好在轉(zhuǎn)移或類轉(zhuǎn)移結(jié)點(diǎn)、標(biāo)號(hào)或例程的結(jié)尾結(jié)束。它只包含表達(dá)式和賦值。?基本塊的概念從對(duì)控制流的關(guān)注中分離出對(duì)表達(dá)式和賦值的整齊序列的代碼生成的關(guān)注。這種分離對(duì)窄編譯程序尤其有用,因?yàn)樗试S它們?yōu)楸磉_(dá)式序列做優(yōu)化代碼生成。?基本塊的代碼生成分兩步進(jìn)行。首先將控制流圖轉(zhuǎn)換成依賴圖,它是一“dag”,即有向非循環(huán)圖。然后我們重寫依賴圖至代碼。收益在于比起控制流圖,依賴圖對(duì)指令順序限制較少。?基本塊的依賴圖由兩種依賴組成:表達(dá)式中通過操作數(shù)的數(shù)據(jù)依賴以及通過變量的數(shù)據(jù)依賴,這些變量的賦值中得到它們的值并且它們的值在且中被繼續(xù)使用。最終的數(shù)據(jù)依賴是那些在基本塊后仍被需要的值,這些值稱為基本塊的根。?強(qiáng)調(diào)這些數(shù)據(jù)依賴并且移除其他的控制流依賴產(chǎn)生了一個(gè)粗糙的數(shù)據(jù)依賴圖,它可以通過旁路賦值并且只保留那些從根可達(dá)的結(jié)點(diǎn)而被簡化。這個(gè)圖是dag,即有向非循環(huán)圖。?基本塊的dag可以通過識(shí)別公共子表達(dá)式而進(jìn)ー步縮減。這個(gè)縮減可以通過不斷地合并具有相同操作數(shù)、運(yùn)算符和依賴的結(jié)點(diǎn)而得到。?傳統(tǒng)地,基本塊的dag作為三元式的數(shù)組而實(shí)現(xiàn)。?基本塊dag中的結(jié)點(diǎn)被重寫至相對(duì)應(yīng)的機(jī)器指令,然后基于操作數(shù)求值將dag線性化。?用于線性化dag的晚求值的特有形式可以識(shí)別梯形序列,該梯影序列匹配寄存器,ーー存儲(chǔ)器指令序列,這些指令都有公共寄存器。這種序列十分有效。真的不掉線嗎つ? ?????????????為發(fā)現(xiàn)先性化,重一個(gè)梯形開始,將第一個(gè)可用的梯形序列分離出來,以由后至前的順序生成代碼,然后從dag上離除這個(gè)梯形并且重復(fù)上述過程。?基本塊中表達(dá)式中的指針可以用兩個(gè)簡單的規(guī)則處理:1.對(duì)指針?biāo)缸兞康馁x值使隨后的表達(dá)式中使用的任何變量依賴該賦值;2.從指針檢索ー個(gè)值依賴于所有前面的賦值。擴(kuò)展分析可能允許取消某些依賴。?表達(dá)式樹的最優(yōu)重寫可以通過BURS代碼生成得到,BURS代表自底向上重寫系統(tǒng)。BURS技術(shù)允許將給定的任意復(fù)雜的輸入樹分解為許多子樹,其中的每個(gè)子樹是給定樹集的成員,既模式樹。模式樹可能同樣是任意復(fù)雜的。應(yīng)用BURS生成代碼,我們將輸入樹看作表達(dá)式AST,將模式樹看作帶機(jī)器指令的AST。BURS在輸入樹上的兩遍掃描中操作:一遍自底向上和一遍自頂向下。自底向上掃描參照模式樹的結(jié)點(diǎn)注釋輸入樹中的每個(gè)結(jié)點(diǎn)。在輸入樹中,結(jié)點(diǎn)I與結(jié)點(diǎn)N相關(guān)意味著頂部有I的樹可以用頂部有N子樹來重寫其頂部。這暗示在重寫頂部后,I以下的樹的所有其他部分也可以被重寫,然后自頂向下掃描可以重寫整個(gè)樹。自底向上掃描結(jié)合模式樹的片段集,特別象詞法分析器結(jié)合正則表達(dá)式的項(xiàng)目集。與詞法分析器ー樣,BURS模式匹配的速度可以通過將其作為FSA而試銷來提高（在這種情況下,它是ー個(gè)樹自動(dòng)機(jī)）,而不是采用解釋的方法）。?與詞法分析器不同,不同模式有不同代價(jià),而我們想要最小代價(jià)的重寫。在解釋實(shí)現(xiàn)中,基于代價(jià)的判定可以用動(dòng)態(tài)程序設(shè)計(jì)技術(shù)處理:在每個(gè)結(jié)點(diǎn),只有在給頂寄存器類型中得到結(jié)果的代價(jià)最地的方法被保留。在樹自動(dòng)機(jī)實(shí)現(xiàn)中,常量代價(jià)可以被合并進(jìn)自動(dòng)機(jī)。結(jié)果轉(zhuǎn)換表經(jīng)常是巨大但可以被可觀地壓縮。?BURS代碼生成可以相對(duì)容易地為額外的需要而改寫。例如,具有集中類型寄存器的機(jī)器的代碼生成和方法到控制流指令的擴(kuò)展。?兩個(gè)變量都存活于程序中的一個(gè)給定位置,當(dāng)涉及到寄存器分配時(shí)它們會(huì)相互干擾。如果我們知道所有變量的活躍范圍,可以創(chuàng)建變量的寄存器相干圖,其中每個(gè)結(jié)點(diǎn)代表一個(gè)變量并且兩結(jié)點(diǎn)N1與N2之間的每條弧表示結(jié)點(diǎn)N!與N2所代表的標(biāo)量的活躍范圍互相重疊。?通過對(duì)圖著色,沒有相同顏色的兩結(jié)點(diǎn)被弧連接,沒種顏色代表ー個(gè)寄存器,這樣我們可以發(fā)現(xiàn)ー個(gè)可能的寄存器至變量的分配》最優(yōu)寄存器分配與使用最低顏色數(shù)的圖著色對(duì)應(yīng)。?最優(yōu)圖著色問題是NP完全的,但存在好的啟發(fā)式算法,例如,從圖中暫時(shí)移除度最小的結(jié)點(diǎn),用相同的算法遞歸地對(duì)余下的圖著色,重新連接移去的結(jié)點(diǎn)并且對(duì)其著色。?在超級(jí)編譯中,ー個(gè)小但經(jīng)常使用的中間代碼片段被采用并且用慣犯的研究來為它生成可能的最好的代碼。結(jié)果代碼在編譯程序中被用做模板。用這種方法已經(jīng)發(fā)現(xiàn)了驚人的代碼序列。?在將中間代碼轉(zhuǎn)換成目標(biāo)代碼前,可能會(huì)進(jìn)行預(yù)處理以提高效率。簡單預(yù)處理的例子有恒定折?和算術(shù)簡化。如果原程序語義需要如此,必須注意算術(shù)溢出條件是否被預(yù)處理忠實(shí)地翻譯。?更廣泛的預(yù)處理可以在例程上進(jìn)行,它們可以被內(nèi)聯(lián)或克隆。在內(nèi)聯(lián)中對(duì)例程的調(diào)用被被調(diào)用的例程體替換。這節(jié)省了調(diào)用與返回序列,為進(jìn)ー步優(yōu)化開真的不掉線嗎??ヽ?？？？？？？？？？？？?辟了道路。必須注意保持參數(shù)轉(zhuǎn)移的語義。?在克隆中,制作例程R的拷貝C,其中參數(shù)P的值固定為值V;對(duì)R的所有調(diào)用（其中參數(shù)P有值V）被對(duì)拷貝C的調(diào)用替換。對(duì)拷貝C經(jīng)?？梢援a(chǎn)生一個(gè)比對(duì)原來的例程R更好的翻譯。?代碼生成過程產(chǎn)生的某些次最優(yōu)符號(hào)機(jī)器代碼序列可以同歸窺孔優(yōu)化移除,其中固定的參數(shù)化序列被其他更好的固定的參數(shù)化序列取代。大約1〇。種替換模式就足夠解決相對(duì)簡單代碼生成器留下的幾乎所有修正的低效問題?指令流中的可替換序列在窺孔優(yōu)化中用基于替換模式的FSA識(shí)別。FSA識(shí)別器識(shí)別最長的可能序列,正如其在詞法分析器中所做的。然后,序列被替換并且重新開始。?代碼生成產(chǎn)生了符號(hào)奇跡指令表,其離可執(zhí)行的二進(jìn)制程序還有幾步之遙。在大多數(shù)編譯程序中,這些步驟有局部匯編程序完成。?匯編程序?qū)樵创a模塊生成的符號(hào)指令翻譯成可重定位的二進(jìn)制目標(biāo)文件。連接程序?qū)⒁恍┛芍囟ㄎ坏亩M(jìn)制文件和可能的ー些庫目標(biāo)文件結(jié)合為可執(zhí)行的二進(jìn)制程序文件。載入程序?qū)⒖蓤?zhí)行二景致程序文件的內(nèi)容裝入存儲(chǔ)器并且開始執(zhí)行程序。?可重定位目標(biāo)文件的代碼段和數(shù)據(jù)段由直接從符號(hào)指令的來的二進(jìn)制代碼組成。因?yàn)椹`些機(jī)器指令需要特殊的對(duì)齊,必須在可重定位目標(biāo)代碼中插入空操作指令。?可重定位二進(jìn)制目標(biāo)文件包含代碼段、數(shù)據(jù)段、重定位信息以及外部連接信息。?計(jì)算可重定位二進(jìn)制文件中的存儲(chǔ)器地址就好象文件在位置。被裝入存儲(chǔ)器。重定位信息列出地址的位置,就象通常一樣,當(dāng)文件被裝入不同位置時(shí),它必須更新。?得到重定位信息從理論上說是ー個(gè)兩遍掃描過程。第二遍掃描可以通過回填重定位地址而避免。重定位信息通常作為位圖實(shí)現(xiàn)。?外部入口點(diǎn)在可重定位二進(jìn)制文件中標(biāo)記ー個(gè)給定單元使其可以被其他可重定位二進(jìn)制文件使用。ー個(gè)模塊中的外部入口點(diǎn)可以被不同甚至相同模塊中的外部訪問存取。?外部連接信息經(jīng)常作為記錄數(shù)組實(shí)現(xiàn)?連接程序結(jié)合其輸入文件的代碼段和數(shù)據(jù)段,用重定位與外部連接信息將相對(duì)地址轉(zhuǎn)換為絕對(duì)地址,在庫模塊中連接以滿足剩余的外部訪問。?連接產(chǎn)生一個(gè)可執(zhí)行代碼文件,它由一個(gè)代碼段和ー個(gè)數(shù)據(jù)段組成。重定位位圖與外部符號(hào)表已經(jīng)不存在了,完成了它們的使命。這就是完成了翻譯過程。從編譯程序構(gòu)造的極度高級(jí)的觀點(diǎn)看，可以認(rèn)為文本分析由模式匹配完成,上下文處理由數(shù)據(jù)流機(jī)完成,目標(biāo)代碼合成再教育次由模式匹配完成。4.580x86指令系統(tǒng)計(jì)算機(jī)是通過執(zhí)行指令序列來解決問題的,因而每種計(jì)算機(jī)都有一組指令集供給用戶使用,這組指令集就稱為計(jì)算機(jī)的指令系統(tǒng)。目前,一般小型或微型計(jì)算機(jī)的指令系統(tǒng)可以包括幾十種或百余種指令。這里簡單介紹一下80X86的指令系統(tǒng)以及在指令格式。計(jì)算機(jī)中的指令由操作碼字段和操作數(shù)字段兩部分組成。操作碼字段指示計(jì)算機(jī)所要執(zhí)行的操作,而操作數(shù)字段則指出在指令執(zhí)行操作的過程中所需要的操作數(shù)。例如,加法指令除需要指定加法操作外,還需要提供加數(shù)和被加數(shù)。操作數(shù)字段可以是操作數(shù)本身,也可以是操作數(shù)地址或是地址的一部分,還可以是指向操作數(shù)地址的指針或其他相關(guān)操作數(shù)的信息。指令的格式一般是:真的不掉線嗎??、?？？？？？？？？？？？操作數(shù)字段可以是ー個(gè)、兩個(gè)、或三個(gè),通常稱