【正文】 分解成各類語法短語。如“程序”，“語句”，“表達(dá)式”等等。一般這種語法短語也稱為語法單位，可表示成語法樹。語法分析所依據(jù)的是語言的語法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。 典型的文法的語法分析器有三類：一類是通用的語法分析方法，如CockeYoungerKasami 算法和 Early 算法，這些方法在生成編譯器時效率太低。編譯器常用的是自頂向下和自底向上的方法。 采用自頂向下的遞歸子程序法，就是對應(yīng)每個非終結(jié)符 語法單元，編一個獨立的處理子程序。語法分析從讀入第一個單詞開始，由非終結(jié)符即開始符出發(fā)，沿語法描述圖箭頭指出的方向進行分析。當(dāng)遇到非終結(jié)符時，則調(diào)用相應(yīng)的處理子程序，從語法描述圖看也就進入了一個語法單元，再沿當(dāng)前所進入的語法描述圖的箭頭方向進行分析，當(dāng)遇到終結(jié)符時，則判斷當(dāng)前讀入的單詞是否與圖中的終結(jié)符相匹配，若匹配，則執(zhí)行相應(yīng)的語義程序。再讀取下一個單詞繼續(xù)分析。遇到分支點時將當(dāng)前的單詞與 第 3 頁 共 41 頁 分支點上的多個終結(jié)符逐個相比較，若都不匹配時可能是進入下一非終結(jié)符語法單位或是出錯。 自頂向下的分析算法通過在最左推導(dǎo) 中描述出各個步驟來分析記號串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號是一個前序編，而且其順序是由根到葉子。自頂向下的分析程序有兩類：回溯分析程序和預(yù)測分析程序。預(yù)測分析程序試圖利用一個或多個先行記號來預(yù)測出輸入串中的下一個構(gòu)造，而回溯分析程序則試著分析其他可能的輸入，當(dāng)一種可能失敗時就要求輸入中備份任意數(shù)量的字符。雖然回溯分析程序比預(yù)測強大許多，但它們都非常慢，一般都在指數(shù)的數(shù)量級上，所以對于實際的編譯器并不適合。遞歸下降程序分析和 LL（ 1）分析一般地都要求計算先行集合，它們分別稱作 First 集合和 Follow 集合。由于無需顯示地構(gòu)造出這些集合就可以構(gòu)造出簡單的自頂向下的分析程序，所以在基本算法的介紹之后我們再討論它們。之后我償還要談到一個由遞歸下降分析構(gòu)造的分析程序。 由于代碼生成較復(fù)雜，所以編譯器一般將這一階段分成幾個涉及不同中間數(shù)據(jù)結(jié)構(gòu)的步驟，其中包括了某種稱作中間代碼的抽象代碼。編譯器也可能沒有生成真正的可執(zhí)行代碼，而是生成了某種形式的匯編代碼，這必須由匯編器、鏈接器和裝入器進行進一步處理。匯編器、鏈接器和裝入器可由操心系統(tǒng)提供或由編譯器自帶。在翻譯期間，中間表示或 IR 代表了源程序和數(shù) 據(jù)結(jié)構(gòu)。雖然抽象語法樹是源代碼完美充分的表達(dá)，即使對于代碼生成也不過這樣，但是它與目標(biāo)代碼極不相像，在控制流構(gòu)造上尤為如此。在控制流構(gòu)造上，目標(biāo)代碼使用轉(zhuǎn)移語句而不是 if 和 while 語句。因此，編譯器編寫者可能希望從語法樹生成一個更接近目標(biāo)代碼的中間表示形式，或者用這樣一個中間表示代替語法樹，然后再從這個新的中間表示生成目標(biāo)代碼。這種類似目標(biāo)代碼的中間表示稱為中間代碼。 編譯器研發(fā)的可行性分析 編寫編譯器的原理和技術(shù)具有十分普遍的意義，以致于在每一個計算機科學(xué)家的研究生涯中，許多原理和技術(shù)都會反復(fù)用到 。編譯器的編寫涉及到程序設(shè)計語言、計算機體系結(jié)構(gòu)、語言理論、算法和軟件工程等學(xué)科。幸運的是，有幾種基本編譯器編寫技術(shù)已經(jīng)被用于構(gòu)建許多計算機的多種語言翻譯器。簡單的說，編譯器是一個程序，它讀入用某種語言（源語言）編寫的程序并將其翻譯成一個與之等價的以另一種語言（目標(biāo)語言）編寫的程序。作為這個翻譯過程匠一個重要組成部分，編譯器能夠向用戶報告被編譯的源程序中出現(xiàn)的錯誤。 編譯器由兩部分組成：分析與綜合。分析部分將源程序切分成一些基本塊并形成源程序的中間表示，綜合部分把源程序的中間表示轉(zhuǎn)為所需的目標(biāo)程序。在分析期 間，源程序所蘊含的操作將被確定下來并被表示成為一個稱為語法樹的分層結(jié)構(gòu)。語法樹的每個節(jié)點表示一個操作，該節(jié)點的子節(jié)點表示這個操作的參數(shù)。 許多操縱源程序的軟件工具都首先完成某種類型的分析。下邊是這類工具的示例： 1． 結(jié)構(gòu)編輯器，結(jié)構(gòu)編輯器將一個命令序列作為輸入一構(gòu)造程序。 2． 智能打印機，智能打印機能夠?qū)Τ绦蜻M行分析，打印出結(jié)構(gòu)清晰的程序。 3． 靜態(tài)檢查器，靜態(tài)檢查器讀入一個程序，分析這個程序，并在不運行這個程序的條件試圖發(fā)現(xiàn)程序的潛在錯誤。 4． 解釋器，解釋器不是通過翻譯來產(chǎn)生目標(biāo)程序，而是直接執(zhí)行源程序中蘊含的操作。 第 4 頁 共 41 頁 目前，世界上存在著數(shù)千種源語言，既有 Fortran 和 Pascal 這樣的傳統(tǒng)程序設(shè)計語言，也有各計算機應(yīng)用領(lǐng)域中出現(xiàn)的專用語言。目標(biāo)語言也同樣廣泛，目標(biāo)語言可以是另一種程序設(shè)計語言或者是從微處理機到計算機的任何計算機的機器語言。不同語言需要不同的編譯器。根據(jù)編譯器的構(gòu)造方法或者它們要實現(xiàn)的功能，編譯器被分為一遍編譯器、多遍編譯器、裝入并執(zhí)行編譯器、調(diào)試編譯器、優(yōu)化編譯器等多種類別。從表面上看，編譯器的種類似乎千變?nèi)f化，多種多樣，實質(zhì)上任何編譯器所要完成的基本任務(wù)都是相同的。通過理解這些任務(wù)，我們可以利用同樣的 基本技術(shù)為各種各樣的源語言和目標(biāo)機器構(gòu)建編譯器。 從 20 世紀(jì) 50年代早期第一個編譯器出現(xiàn)到今，我們所掌握的有關(guān)編譯器的知識已經(jīng)得到了長足的發(fā)展。整個 20世紀(jì) 50年代，編譯器的編寫一直被認(rèn)為是一個極難的問題。目前我們已經(jīng)系統(tǒng)地掌握了處理編譯期間發(fā)生的許多重要任務(wù)的技術(shù)。良好的實現(xiàn)語言、程序設(shè)計環(huán)境和軟件工具也已經(jīng)被開發(fā)出來。 20 世紀(jì) 50 年代末有人開始研究編譯程序的自動生成技術(shù)，提出并研制編譯程序的編譯程序。它的功能是以任一語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā)，自動產(chǎn)生該語言的編譯程序。目前，很多自動生成的 工具已廣泛使用，如詞法分析的生成系統(tǒng) LEX，語法分析程序的生成系統(tǒng) YACC 等。 20世紀(jì) 60 年代起，不斷有人使用自展技術(shù)來構(gòu)造編譯程序。自展的主要特征是用被編譯的語言來書寫該語言自身的編譯程序。自從 1971 年， PASCAL 的編譯程序用自展技術(shù)生成后，起影響就越來越大。 研究編譯程序是有意義在于： 1） 編譯程序構(gòu)造是計算機科學(xué)中的一個非常成功的分支，也是最早獲的成功的分支之一； 2） 它與文件轉(zhuǎn)換程序關(guān)系密集，且不僅僅適用于編譯程序； 3） 它包含許多在實際應(yīng)用中有用的算法。 由于近幾年并行機及多處理機的發(fā)展，對軟件的并行處理 技術(shù)提出了新的要求。特別是并行編譯技術(shù)發(fā)展很快，目前處理并行編譯技術(shù)有兩種方法： 第一種方法，運用重構(gòu)技術(shù)把已有的串行語言編寫的程序經(jīng)過相關(guān)分析，分解成可并行的成分，分配到多 CPU 或多處理機上運行，這種技術(shù)國內(nèi)已有 FORTRAN 和 C語言的并行重構(gòu)處理系統(tǒng)，相當(dāng)成功。 第二種方法，即在程序設(shè)計語言機制上允許用戶自己編寫并行程序，這當(dāng)然比編寫串行語言對編程人員提出的要求更多。即用戶自己必須知道程序各模塊之間邏輯結(jié)構(gòu)關(guān)系及調(diào)用關(guān)系乃至運算量，以確定哪些模塊可以并行執(zhí)行。若編程者能按程序設(shè)計情況編出并行程序，無疑并 行程序效率將比第一種方法要好。 隨著并行技術(shù)和并行語言的發(fā)展，處理并行語言的并行編譯技術(shù)正在深入研究之中，將串行程序轉(zhuǎn)換成并行程序的自動并行編譯技術(shù)也正在深入研究之中。 代碼生成較復(fù)雜，所以編譯器一般將這一階段分成幾個涉及不同中間數(shù)據(jù)結(jié)構(gòu)的步驟，其中包括了某種稱作中間代碼的抽象代碼。編譯器也可能沒有生成真正的可執(zhí)行代碼，而是生成了某種形式的匯編代碼，這必須由匯編器、鏈接器和裝入器進行進一步處理。匯編器、鏈接器和裝入器可由操心系統(tǒng)提供或由編譯器自帶。在翻譯期間，中間表示或 IR 代表了源程序和數(shù)據(jù)結(jié)構(gòu)。雖然抽象語 法樹是源代碼完美充分的表達(dá)，即使對于代碼生成也不過這樣，但是它與目標(biāo)代碼極不相像，在控制流構(gòu)造上尤為如此。在控制流構(gòu)造上，目標(biāo)代碼使用轉(zhuǎn)移語句而不是 if和 while 語句。因此，編譯器編寫者可能希望從語法樹生成一個更接近目標(biāo)代碼的中間表示形式，或者用這樣一個中間表示代替語法樹，然后再從這個新的中間表示生成目標(biāo)代碼。這種類似目標(biāo)代碼的中間表示稱為中間代碼。然后編譯程序再調(diào)用相應(yīng)的處理程序，將中間代碼轉(zhuǎn)換 第 5 頁 共 41 頁 為計算機能處理的機器指令，最終得到目標(biāo)代碼。 2． 3 編譯過程概述 編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一， 而且多數(shù)計算機系統(tǒng)都含有不止一個高級語言的編譯程序，對有些高級語言甚至配置了幾個不同性能的編譯程序。從功能上看，一個編譯程序就是一個語言翻譯程序。它把一種語（稱作源語言）書寫的程序翻譯成另一種語言（稱作目標(biāo)語言）的等價的程序。比如匯編程序是一個翻譯程序，它把匯編語言程序翻譯成機器語言程序。如果源語言是像 FORTRAN， PASCAL，或 C 那樣的高級語言，目標(biāo)語言是像匯編語言或機器語言那樣的低級玉器言，則這種翻譯程序稱作編譯程序。 一個編譯程序的重要性體現(xiàn)在它使得多數(shù)計算機用戶不必考慮與機器有關(guān)的繁索細(xì)節(jié)，使程 序員和程序設(shè)計專家獨立于機器，這對于當(dāng)今機器的數(shù)量和種類持續(xù)不斷地增長的年代憂為重要。除了編譯程序外，還需要一些其它的程序才能生成一個可在計算機執(zhí)行的目標(biāo)程序。 高級語言程序的處理過程如圖： 需處理的源程序 源程序 目標(biāo)匯編程序 可再裝配的機器代碼 可在裝配的目標(biāo)文件 絕對機器代碼 一個源程序有時可能分成幾個模塊存放在不同的文件里，將這些源程序匯集在一起的任務(wù)，由一個叫做預(yù)處理程序的程序完成，有些預(yù)處理程序也負(fù)責(zé)宏展開，像 C語言和預(yù)處理程序要完成文件合并、宏展開等任務(wù)。也就是說，一個編譯程序的輸入可能要一個或多個預(yù)處理程序來產(chǎn)生，另外，為得到能運行的機器代碼，編譯程序的輸出可能仍需要進一步地處理。 編譯程序完成從源程序到目標(biāo)程序的翻 譯工作，是一個復(fù)雜的整體的過程。從概念上來講，一個編譯程序和整體工作過程是劃分成階級進行的，每個階級將源程序的一種表示形式換成另一種表示形式，各個階級進行的操場作在邏輯上是緊密連接在一起的，如圖 1 所示，給出了一個編譯過的和各個階級，這是一種比較典型的劃分方法。 預(yù)處理程序 編譯程序 匯編程序 裝配 /連接 —編輯程序 第 6 頁 共 41 頁 源程序 圖 1 圖 1 將編譯過程劃分了詞法分析、語法分析、語義分析、中 間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、六個階級。另外兩個重要的工作：表格處理和出錯處理與上述六個階級都有聯(lián)系。編譯過程是源程序和各種信息被子保留在種種不同的表格里，編譯各階級的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格處理的工作；如果編譯過程中發(fā)現(xiàn)源程序有錯誤，編譯程序應(yīng)報告錯誤的性質(zhì)和錯誤發(fā)生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。 詞法分析階級是編譯過程的第一個階級。這個階級的任務(wù)是從左到 右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，從而識別一個個單詞（也稱為單詞符號或符號）。這里所謂的單詞是指邏輯上緊密相連的一組字符，這些字符具有集體含義。比如標(biāo)識是由字母開頭，后跟字母、數(shù)字字符序列組成的一種單詞。保留字是一種單詞，此外還有算符，界符等等。 語法分析是編譯過程的第二個階級。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等。一般這種語法短語，也稱為語法單位，可表示成語法樹。語法分析所依據(jù)的是語言的語法規(guī)則，即描述程序 結(jié)構(gòu)的規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。詞法分析和語法分析本質(zhì)上都是對源程序的結(jié)構(gòu)進行分析。但詞法分析的任務(wù)僅對源程序進行線性掃描即可完成，比如識別標(biāo)識符，因為標(biāo)識符的結(jié)構(gòu)是字母打頭的字母和數(shù)字序列，這只要順序掃描輸入流，遇到既不是字母又不是數(shù)字字符時，將前面所發(fā)現(xiàn)的所有字母和數(shù)字組合在一起而構(gòu)成單詞標(biāo)識符。但這種線性掃描則不能用于識別遞歸定義的語法成分，比如就不能用此辦法去匹配表達(dá)式中的括號。 語義分析階級是審查源程序有無語義錯誤，為代碼生成階級收集類型信息。比如語分析的一個工 作是進行類型審查，審查每個算符是否具有語言規(guī)范允許的運算