軟件構(gòu)造第一章

1、 軟件構(gòu)造主講教師： 張靜 第一章 緒論 1.1課程介紹 1.2什么是編譯程序 1.3編譯程序的生成 1.4處理源程序的軟件工具1.1課程介紹 課程性質(zhì) 原理性課程，是計(jì)算機(jī)類(lèi)專(zhuān)業(yè)的基礎(chǔ)課程。 原理：基礎(chǔ)性 科學(xué)性 普適性 課程的重要性 軟件工程主干課 程 編譯程序（系統(tǒng)）是計(jì)算機(jī)系統(tǒng)的核心支撐軟件 貫穿程序語(yǔ)言、運(yùn)行時(shí)系統(tǒng)、體系結(jié)構(gòu) 聯(lián)系計(jì)算機(jī)科學(xué)和計(jì)算機(jī)系統(tǒng)的典范 編譯技術(shù)的廣泛的應(yīng)用 人工智能、多媒體技術(shù)等 翻譯軟件 嵌入式系統(tǒng) ERP二次開(kāi)發(fā) 冗余代碼分析 文本編輯器、信息檢索系統(tǒng)、模式識(shí)別器 排版繪圖系統(tǒng) 教學(xué)目的與要求 深入對(duì)程序設(shè)計(jì)語(yǔ)言的理解；（加深對(duì)程序編譯過(guò)程的理解，培養(yǎng)計(jì)算

2、思維能力） 提高軟件開(kāi)發(fā)能力；（提高編程效率） 提高元級(jí)程序設(shè)計(jì)能力；（編譯器的設(shè)計(jì)實(shí)現(xiàn)） 增強(qiáng)形式化、抽象化能力。（問(wèn)題形式化） 相關(guān)課程先修課程 高級(jí)語(yǔ)言程序設(shè)計(jì)（Java, C/C+） 數(shù)據(jù)結(jié)構(gòu) 離散數(shù)學(xué)其他相關(guān)課程計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)，操作系統(tǒng)，程序設(shè)計(jì)語(yǔ)言理論，形式語(yǔ)言與自動(dòng)機(jī) 教材及主要參考書(shū)教材 編譯原理（第3版），張素琴、呂映芝、 清華大學(xué)出版社 參考書(shū)程序設(shè)計(jì)語(yǔ)言 編譯原理（第3版），陳火旺、劉春林等，國(guó)防工業(yè)出版社 2000 教學(xué)內(nèi)容教學(xué)內(nèi)容介紹編譯器構(gòu)造的基本原理、基本方法和基本技術(shù)介紹理論知識(shí)：形式語(yǔ)言和自動(dòng)機(jī)理論等強(qiáng)調(diào)形式化描述技術(shù)（抽象思想）強(qiáng)調(diào)對(duì)編譯原理和技術(shù)的宏觀理解

3、，不把注意力分散到枝節(jié)算法（理解、會(huì)用） 課程課程架構(gòu)架構(gòu)理論和實(shí)踐并重的課程 理論部分的題目出現(xiàn)于書(shū)面練習(xí)，課堂小測(cè)和期末考試實(shí)踐題目（Project）各部分權(quán)重 平時(shí)成績(jī)30%（簽到、平時(shí)測(cè)驗(yàn)、作業(yè)、上機(jī)） 期末考試 70%準(zhǔn)時(shí)到、認(rèn)真聽(tīng)、掌握方法、善于思考1.2什么是編譯程序1.2.1語(yǔ)言的概念和分類(lèi)n概念 語(yǔ)言是人類(lèi)所特有的用來(lái)表達(dá)意思、交流思想的工具，是一種特殊的社會(huì)現(xiàn)象，由語(yǔ)音、詞匯、語(yǔ)法、語(yǔ)義構(gòu)成一個(gè)系統(tǒng)。語(yǔ)言包括口語(yǔ)和書(shū)面形式。 語(yǔ)言的分類(lèi) (1)自然語(yǔ)言 人與人之間交流信息的一種語(yǔ)言. 動(dòng)物之間通過(guò)動(dòng)物語(yǔ)言交流信息. （2）數(shù)理語(yǔ)言 以數(shù)理邏輯、集合論和統(tǒng)計(jì)數(shù)學(xué)來(lái)描述的一種語(yǔ)

4、言。 例如，用計(jì)算機(jī)進(jìn)行幾何定理的證明就得以數(shù)理語(yǔ)言形式進(jìn)行描述。 （3）程序設(shè)計(jì)語(yǔ)言 人和計(jì)算機(jī)進(jìn)行信息交流的一種語(yǔ)言，它遵循一定的語(yǔ)法和語(yǔ)義的規(guī)則，而編譯程序的功能正是： 1）討論語(yǔ)法，檢查程序正確性 2）討論語(yǔ)義，生成目標(biāo)代碼1.2.2程序設(shè)計(jì)語(yǔ)言簡(jiǎn)述 機(jī)器語(yǔ)言機(jī)器語(yǔ)言(第一代第一代) 低級(jí)語(yǔ)言低級(jí)語(yǔ)言 匯編語(yǔ)言匯編語(yǔ)言(第二代第二代) 初期初期 ：FORTRAN、ALGOL、COBOL 發(fā)展期發(fā)展期 ：LISP、APL、SNOBOL、PL/1、 (第三代第三代) SIMULA、BASIC程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言 高級(jí)語(yǔ)言高級(jí)語(yǔ)言 結(jié)構(gòu)化時(shí)期結(jié)構(gòu)化時(shí)期 ：PASCAL、Ada、C 函數(shù)式

5、：函數(shù)式：ML、LISP、APL 多范型時(shí)期多范型時(shí)期 邏輯式：邏輯式：PROLOG 面向?qū)ο螅好嫦驅(qū)ο螅篠malltalk、C+、Java (第四代第四代) SQL 網(wǎng)絡(luò)網(wǎng)絡(luò) ：Java、Perl、C# 超高級(jí)語(yǔ)言超高級(jí)語(yǔ)言 報(bào)表語(yǔ)言報(bào)表語(yǔ)言 MAPPER 機(jī)器語(yǔ)言：能夠被計(jì)算機(jī)的硬件系統(tǒng)直接執(zhí)行的指令程序，如“0001000101”。 匯編語(yǔ)言：將硬件指令用一些助記符表示，即符號(hào)化的機(jī)器語(yǔ)言，如“ADD，MOV”。 高級(jí)語(yǔ)言：從程序員的角度出發(fā)，對(duì)匯編語(yǔ)言進(jìn)一步抽象，使用便于理解的“自然語(yǔ)言”表述。1.2.3 翻譯程序 翻譯程序 將一種語(yǔ)言程序（稱(chēng)為源程序）改造成另一種等價(jià)的語(yǔ)言程序（稱(chēng)為

6、目標(biāo)程序）的程序。源語(yǔ)言 書(shū)寫(xiě)源程序的語(yǔ)言稱(chēng)為源語(yǔ)言.目標(biāo)語(yǔ)言 書(shū)寫(xiě)目標(biāo)程序的語(yǔ)言稱(chēng)為目標(biāo)語(yǔ)言. 翻譯程序匯編程序解釋程序編譯程序n匯編程序 匯編程序：把匯編語(yǔ)言寫(xiě)的源程序翻譯成機(jī)器語(yǔ)言的目標(biāo)程序， 這個(gè)翻譯過(guò)程稱(chēng)為匯編。如下圖： 匯編程序執(zhí)行過(guò)程 匯編程序一般對(duì)源程序進(jìn)行兩遍掃描來(lái)完成。 第一遍：進(jìn)行存貯分配，造出第二遍掃描時(shí)用的各種表格； 第二遍：用機(jī)器語(yǔ)言操作碼來(lái)代替匯編符號(hào)操作碼。 17匯編源程序目標(biāo)程序匯編程序初始數(shù)據(jù) 結(jié)果數(shù)據(jù) 解釋程序解釋程序：將高級(jí)語(yǔ)言寫(xiě)的源程序作為輸入數(shù)據(jù)，但并不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身的一種程序。如下圖： 解釋程序執(zhí)行過(guò)程 解釋程序適合于會(huì)話(huà)

7、型語(yǔ)言，如BASIC語(yǔ)言。主要優(yōu)點(diǎn)：1，易于為用戶(hù)提供調(diào)試功能，對(duì)源程序的語(yǔ)法分析及出錯(cuò)處理都很及時(shí)2，修改調(diào)試也很方便，但是解釋程序執(zhí)行速度較慢，運(yùn)行效率低。18n編譯程序 從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序，它把一種語(yǔ)言(稱(chēng)作源語(yǔ)言)書(shū)寫(xiě)的程序翻譯成另一種語(yǔ)言(稱(chēng)作目標(biāo)語(yǔ)言)的等價(jià)的程序. 編譯系統(tǒng) 目標(biāo)程序，再加上運(yùn)行系統(tǒng)（如服務(wù)子程序、動(dòng)態(tài)分配程序、裝配程序等）就可獲得計(jì)算結(jié)果，整個(gè)系統(tǒng)稱(chēng)為編譯系統(tǒng)。編譯程序執(zhí)行過(guò)程20源程序源程序編譯程序編譯程序目標(biāo)程序目標(biāo)程序（機(jī)器語(yǔ)言）（機(jī)器語(yǔ)言）源程序源程序編譯程序編譯程序目標(biāo)程序目標(biāo)程序（匯編語(yǔ)言）（匯編語(yǔ)言）匯編程序匯編程序目標(biāo)程

8、序目標(biāo)程序（機(jī)器語(yǔ)言）（機(jī)器語(yǔ)言）編譯階段編譯階段編譯階段編譯階段匯編階段匯編階段目標(biāo)程序目標(biāo)程序（機(jī)器語(yǔ)言）（機(jī)器語(yǔ)言）運(yùn)行系統(tǒng)運(yùn)行系統(tǒng)可執(zhí)行程序可執(zhí)行程序結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)運(yùn)行階段運(yùn)行階段解釋程序與編譯程序的主要區(qū)別是： 編譯程序是將源程序翻譯成目標(biāo)程序后再執(zhí)行該目標(biāo)程序，而解釋程序則是逐條讀出源程序中的語(yǔ)句并解釋執(zhí)行，即在解釋程序的執(zhí)行過(guò)程中并不產(chǎn)生目標(biāo)程序。 上述三種翻譯程序中，匯編程序最容易實(shí)現(xiàn)，其次是解釋程序，編譯程序最難。所以只要掌握了編譯程序?qū)崿F(xiàn)方法，匯編程序和解釋程序就迎刃而解了。1.2.4編譯邏輯過(guò)程n詞法分析n語(yǔ)法分析n語(yǔ)義分析n中間代碼生成n代碼優(yōu)化n目標(biāo)代碼生成 英文語(yǔ)

9、句的翻譯過(guò)程 This line is a longer sentence. 識(shí)別單詞（詞法分析） 句子開(kāi)頭的單詞第一個(gè)字母要大寫(xiě) 空格是單詞分隔符 句點(diǎn)是句子結(jié)尾 n分析句子（語(yǔ)法分析） 形式上是否符合規(guī)則。n草譯（中間代碼生成）n修飾詞匯（優(yōu)化）n交差（生成目標(biāo)代碼）從左至右掃描字符流的源程序、分解構(gòu)成源程序的字符串，識(shí)別出(拼)一個(gè)個(gè)的單詞（符號(hào)）完成以下任務(wù)：1.拼出每個(gè)單詞2.刪除無(wú)用符號(hào)3.刪除注釋4.檢查詞法錯(cuò)誤（1）詞法分析識(shí)別單詞，斷詞例1 C語(yǔ)言中的一條語(yǔ)句sum=average+score*10; 詞法分析結(jié)果：（2）語(yǔ)法分析 語(yǔ)法分析是編譯程序的核心部分。它的功能是在詞

10、法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則把單詞序列分解成各類(lèi)語(yǔ)法單位，如“短語(yǔ)”、“子句”、“句子”、“程序段”和“程序”。并在分析過(guò)程中進(jìn)行語(yǔ)法正確性檢查，產(chǎn)生內(nèi)部形式的中間代碼。通過(guò)語(yǔ)法分析可以確定整個(gè)輸入串是否構(gòu)成一個(gè)語(yǔ)法上正確的“程序”。將例1的詞法分析結(jié)果表示成自上而下的語(yǔ)法樹(shù)（3）中間代碼生成 一個(gè)源程序經(jīng)過(guò)詞法分析和語(yǔ)法分析后，表明源程序在書(shū)寫(xiě)上是正確的，并且符合程序語(yǔ)言的語(yǔ)法規(guī)則。語(yǔ)義分析是按照語(yǔ)法分析器識(shí)別的語(yǔ)法范疇分析程序內(nèi)部的邏輯含義，產(chǎn)生相應(yīng)的中間代碼或目標(biāo)代碼。 例：四元式的四個(gè)部分（op,arg1, arg 2，result)分別表示算符、第一運(yùn)算量、第二運(yùn)算量、運(yùn)算結(jié)果

11、。表達(dá)式及各種語(yǔ)句均可表示成一組四元式。則例1中語(yǔ)句的四元式可表示為：(1) （uminus,10,/,T1）(2) （*,id3, T1,T2）(3) (+,id2, T2, T3)(4) (=,T3,/, id1) （4）代碼優(yōu)化 代碼優(yōu)化指為了提高目標(biāo)程序的質(zhì)量，而對(duì)源程序或前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得執(zhí)行速度快、占用空間少的目標(biāo)代碼。 等價(jià)的含義是使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同。節(jié)省的時(shí)間是通過(guò)減少指令條數(shù)和降低運(yùn)算強(qiáng)度等措施來(lái)實(shí)現(xiàn)。例： 將例1的中間代碼進(jìn)一步優(yōu)化：（1）(*,id3,10,T1 )（2）(+,id2,T1,id1)（5）目標(biāo)代碼

12、生成 目標(biāo)代碼生成是編譯程序的最后一個(gè)工作階段，其任務(wù)是把經(jīng)優(yōu)化處理之后的中間代碼變換成特定機(jī)器上的機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序，實(shí)現(xiàn)最終的翻譯工作。 由于目標(biāo)語(yǔ)言依賴(lài)于硬件系統(tǒng)，因而如何充分利用現(xiàn)有的寄存器以節(jié)省訪(fǎng)問(wèn)內(nèi)存的時(shí)間，合理地選擇執(zhí)行速度快的指令，生成盡可能短且有效的目標(biāo)代碼是這個(gè)階段考慮的主要問(wèn)題。例：將例1中優(yōu)化后的中間代碼生成匯編語(yǔ)言的目標(biāo)代碼：MOV id3,AXMUL #10,AXMOV id2,BXADD AX,BXMOV BX,id1 上述編譯過(guò)程的五個(gè)階段是編譯程序工作時(shí)的動(dòng)態(tài)特征，編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。編譯程序的結(jié)構(gòu)示意如下圖所示。出錯(cuò)

13、處理程序語(yǔ)法分析程序語(yǔ)義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理程序 編譯過(guò)程（6）表格管理 在編譯程序工作的過(guò)程中，需要不斷收集、記錄、查證和使用源程序中的一些語(yǔ)法符號(hào)的類(lèi)型和特征等相關(guān)信息以及編譯各階段的進(jìn)展?fàn)顩r。常用做法是讓編譯程序在其工作過(guò)程中建立并保存一批表格，如常數(shù)表、變量名表、數(shù)組內(nèi)情向量表、過(guò)程或子程序名表及標(biāo)號(hào)表等，將它們統(tǒng)稱(chēng)為符號(hào)表或名字表。 例如，一個(gè)名字是常量名、變量名，還是過(guò)程名等等；如果是變量名，它的類(lèi)型是什么、所占內(nèi)存是多大、地址是什么等等。合理地設(shè)計(jì)和使用表格是編譯程序構(gòu)造的一個(gè)重要問(wèn)題。編譯的各階段的工作都涉及到構(gòu)造、查找或更新

14、有關(guān)的表格，因此，表格管理程序也是編譯工作的重要內(nèi)容。（7）出錯(cuò)處理 編譯程序不僅應(yīng)能對(duì)正確的程序進(jìn)行翻譯，還應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶(hù)。這部分工作是由專(zhuān)門(mén)的一組程序完成，這組程序稱(chēng)為出錯(cuò)處理程序。最大限度發(fā)現(xiàn)錯(cuò)誤準(zhǔn)確之處錯(cuò)誤的性質(zhì)和發(fā)生地點(diǎn)將錯(cuò)誤影響限制在盡可能的范圍之內(nèi)1.2.5 遍 在確定編譯程序具體實(shí)現(xiàn)時(shí)，常常將編譯程序按其掃描遍數(shù)分為一遍掃描或多遍掃描 。 從頭到尾掃描一遍源程序或等價(jià)源程序，并做有關(guān)加工處理，稱(chēng)遍或者趟程。每經(jīng)過(guò)一遍源程序都要進(jìn)行等價(jià)變換并更接近目標(biāo)程序。 如果通過(guò)對(duì)源程序一遍掃描直接生成目

15、標(biāo)代碼程序，則說(shuō)編譯程序是單遍的。 把源程序分為幾遍來(lái)編譯，每遍只完成編譯程序中的一部分或幾個(gè)部分工作，稱(chēng)為多遍的。 比如第一遍進(jìn)行詞法、語(yǔ)法分析，檢查語(yǔ)法錯(cuò)誤；第二遍生成中間語(yǔ)言進(jìn)行存儲(chǔ)分配；第三遍生成可運(yùn)行的目標(biāo)程序。 決定遍的因素：（1）計(jì)算機(jī)存貯容量大??；（2）編譯程序功能強(qiáng)弱；（3）源語(yǔ)言繁簡(jiǎn)；（4）目標(biāo)程序優(yōu)化程度；（5）設(shè)計(jì)和實(shí)現(xiàn)編譯程序時(shí)使用工具的先進(jìn)程度；（6）編譯時(shí)間要求； (7）參加人員多少和素質(zhì)等等。 分多遍完成編譯過(guò)程可以使整個(gè)編譯程序的邏輯結(jié)構(gòu)更清晰一點(diǎn)，但遍數(shù)多勢(shì)必增加讀寫(xiě)中間文件的次數(shù)，從而消耗過(guò)多的時(shí)間。1.3編譯程序的生成1.3.1編寫(xiě)編譯程序的一般方法1.

16、3.2編譯程序開(kāi)發(fā)技術(shù)1.3.3編譯程序的自動(dòng)生成 1.3.1編寫(xiě)編譯程序的一般方法編寫(xiě)編譯程序的一般方法(1)直接用機(jī)器語(yǔ)言編寫(xiě)編譯程序(2)用匯編語(yǔ)言編寫(xiě)編譯程序(3)用系統(tǒng)程序設(shè)計(jì)語(yǔ)言編寫(xiě) (1)直接用機(jī)器語(yǔ)言編寫(xiě)編譯程序 機(jī)器語(yǔ)言是早期編寫(xiě)編譯程序的唯一工具, 但由于機(jī)器語(yǔ)言難讀難寫(xiě) , 現(xiàn)在幾乎沒(méi)有人再用它。(2)用匯編語(yǔ)言編寫(xiě)編譯程序 由于匯編語(yǔ)言太依賴(lài)于硬件環(huán)境,且程序過(guò)于冗長(zhǎng), 現(xiàn)在也不常用, 不過(guò)由于它通過(guò)匯編程序產(chǎn)生的目標(biāo)代碼效率比較高, 所以在編譯程序核心部分常用它編寫(xiě)。(3)用系統(tǒng)程序設(shè)計(jì)語(yǔ)言編寫(xiě) 由于用機(jī)器語(yǔ)言和匯編語(yǔ)言編寫(xiě)編譯程序其主要缺點(diǎn)是效率低,因此越來(lái)越多的人

17、傾向于使用高級(jí)語(yǔ)言作為工具來(lái)編寫(xiě)編譯程序。80年代開(kāi)始, 幾乎所有的編譯程序都是用高級(jí)語(yǔ)言編寫(xiě), 從而避開(kāi)了與機(jī)器有關(guān)許多煩瑣細(xì)節(jié),大大減輕編寫(xiě)編譯程序工作量。并非所有高級(jí)語(yǔ)言都適合于編寫(xiě)編譯程序。1.3.2編譯程序開(kāi)發(fā)技術(shù)(1)自編譯(2)交叉編譯(3)自展技術(shù)(4)移植(1)自編譯1）如果一種高級(jí)語(yǔ)言與之相應(yīng)的編譯程序也能直接用該語(yǔ)言本身寫(xiě)出來(lái) , 具有這種性質(zhì)語(yǔ)言稱(chēng)自編譯語(yǔ)言 , 即自編譯。能夠編譯自身的編譯程序稱(chēng)自編譯程序。2）自編譯語(yǔ)言除了書(shū)寫(xiě)自身編譯程序外 , 一般還可以編寫(xiě)其它語(yǔ)言編譯程序 。3）系統(tǒng)程序設(shè)計(jì)語(yǔ)言就是這樣語(yǔ)言，通常把能夠編寫(xiě)編譯程序或其它系統(tǒng)軟件(如操作系統(tǒng))的高

18、級(jí)語(yǔ)言稱(chēng)系設(shè)計(jì)語(yǔ)言,到目前為止,作為系統(tǒng)程序設(shè)計(jì)語(yǔ)言有PASCAL, MODULA, C, C+和ADA等。(2)交叉編譯 交叉編譯的概念 如果一個(gè) A 機(jī)器上編譯程序能產(chǎn)生 B 機(jī)器的目標(biāo)代碼 , 則稱(chēng)這種程序?yàn)榻徊婢幾g程序。(3)自展技術(shù) 自展技術(shù)的定義 自展技術(shù)可以由一個(gè)功能較小的編譯程序 , 一級(jí)一級(jí)擴(kuò)充而變成一個(gè)功能較強(qiáng)的編譯程序。(4)移植n移植就是把一臺(tái) 計(jì)算機(jī)上的軟件移植到另一臺(tái)計(jì)算機(jī)上去。n移植方法： 一種方法是綜合幾種型號(hào)計(jì)算機(jī)抽象出一個(gè)通用的匯編 語(yǔ)言,而每種型號(hào) 計(jì)算機(jī)上只要配有一個(gè)簡(jiǎn)單匯編程序 , 用它來(lái)把通用匯編語(yǔ)言書(shū)寫(xiě)的程序翻 譯成機(jī)器語(yǔ)言程序。 另一種方法就是利用交叉編譯方法可以把一臺(tái)計(jì)算機(jī)上自編譯語(yǔ)言的編譯程序移植到另 一臺(tái)計(jì)算機(jī)上。 1.3.3編譯程序的自動(dòng)生成 把源語(yǔ)言的定義以及機(jī)器語(yǔ)言的描述輸入到這種軟件中去 , 自動(dòng)生成該語(yǔ)言編譯程序, 這就是編譯