編譯原理第一章

1、1編譯原理編譯原理 主講:陳小娟 E-mail: 西南大學(xué)榮昌校區(qū)信息管理系2本課程的考核：本課程的考核：l平時(shí)作業(yè)平時(shí)作業(yè):20%l平時(shí)考勤平時(shí)考勤:10%l實(shí)驗(yàn)考核實(shí)驗(yàn)考核:20%l期末考試期末考試(閉卷閉卷):50%第一章引論引論1.1 什么是編譯程序？什么是編譯程序？從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序,它把一種語(yǔ)言它把一種語(yǔ)言(稱(chēng)作源語(yǔ)言稱(chēng)作源語(yǔ)言)書(shū)寫(xiě)的程序翻譯成另一種書(shū)寫(xiě)的程序翻譯成另一種語(yǔ)言語(yǔ)言(稱(chēng)作目標(biāo)語(yǔ)言稱(chēng)作目標(biāo)語(yǔ)言)的等價(jià)的程序。的等價(jià)的程序。比如匯編程序是一個(gè)翻譯程序，它把匯編語(yǔ)言程序翻比如匯編程序是一個(gè)翻譯程序，它把

2、匯編語(yǔ)言程序翻譯成機(jī)器語(yǔ)言。如果把編譯程序看成是一個(gè)譯成機(jī)器語(yǔ)言。如果把編譯程序看成是一個(gè)“黑盒黑盒子子”，它執(zhí)行的轉(zhuǎn)化工作如下圖：，它執(zhí)行的轉(zhuǎn)化工作如下圖：編譯程序高 級(jí) 語(yǔ) 言 書(shū)寫(xiě) 的 程 序（源程序）低級(jí)語(yǔ)言程序（目標(biāo)程序）4 編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算編譯程序的重要性體現(xiàn)在它使得多數(shù)計(jì)算機(jī)用戶(hù)不必考慮與機(jī)器有關(guān)的煩瑣細(xì)節(jié)，機(jī)用戶(hù)不必考慮與機(jī)器有關(guān)的煩瑣細(xì)節(jié)，使程序員和程序設(shè)計(jì)專(zhuān)家獨(dú)立于機(jī)器。這使程序員和程序設(shè)計(jì)專(zhuān)家獨(dú)立于機(jī)器。這對(duì)于當(dāng)今機(jī)器的數(shù)量和種類(lèi)持續(xù)不斷地增對(duì)于當(dāng)今機(jī)器的數(shù)量和種類(lèi)持續(xù)不斷地增長(zhǎng)的年代尤為重要。長(zhǎng)的年代尤為重要。51.2編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯過(guò)程

3、和編譯程序的結(jié)構(gòu)o編譯程序完成從源程序到目標(biāo)程序的翻譯工作，編譯程序完成從源程序到目標(biāo)程序的翻譯工作，是一個(gè)復(fù)雜的整體的過(guò)程。從概念上來(lái)講，一個(gè)是一個(gè)復(fù)雜的整體的過(guò)程。從概念上來(lái)講，一個(gè)編譯程序的整個(gè)工作過(guò)程是劃分成階段進(jìn)行的，編譯程序的整個(gè)工作過(guò)程是劃分成階段進(jìn)行的，每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換成另一種每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個(gè)階段進(jìn)行的操作在邏輯上是緊密表示形式，各個(gè)階段進(jìn)行的操作在邏輯上是緊密連接在一起的。連接在一起的。o一般一個(gè)編譯過(guò)程劃分成一般一個(gè)編譯過(guò)程劃分成詞法分析、語(yǔ)法分析、詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成，代碼優(yōu)化和目標(biāo)代碼語(yǔ)義分

4、析、中間代碼生成，代碼優(yōu)化和目標(biāo)代碼生成生成六個(gè)階段六個(gè)階段,這是一種典型的劃分方法。這是一種典型的劃分方法。 編譯程序的結(jié)構(gòu)詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生器語(yǔ)義分析與中間代碼產(chǎn)生器優(yōu)化器目標(biāo)代碼生成器出錯(cuò)處理表格管理源程序單詞符號(hào)語(yǔ)法單位中間代碼中間代碼目標(biāo)代碼71.詞法分析詞法分析o功能功能:從左到右讀入源程序的每個(gè)字符，對(duì)構(gòu)成從左到右讀入源程序的每個(gè)字符，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞（也叫單詞符號(hào)或符號(hào)）。一個(gè)個(gè)單詞（也叫單詞符號(hào)或符號(hào)）。o單詞：邏輯上緊密相連的一組字符，這些字符單詞：邏輯上緊密相連的一組字

5、符，這些字符具有集體含義。如：標(biāo)識(shí)符、保留字（關(guān)鍵字具有集體含義。如：標(biāo)識(shí)符、保留字（關(guān)鍵字或基本字）、算符、界符等。或基本字）、算符、界符等。例. 某源程序片斷如下：begin var sum , first , count : real ; sum := first + count * 10end.詞法分析階段將他們組成如右圖的單詞序列.（注意:程序代碼中的空格在編譯時(shí)被過(guò)濾.）如果使用id1,id2,id3分別表示sum ，first ，count經(jīng)過(guò)分析后：sum := first + count * 10則表示為id1:=id2+id3*10又如一個(gè)C源程序片斷： int a; a

6、= a + 2;詞法分析后可能返回:單詞類(lèi)型單詞類(lèi)型 單詞值單詞值 保留字 int標(biāo)識(shí)符(變量名) a界符 ;標(biāo)識(shí)符(變量名) a算符(賦值) =標(biāo)識(shí)符(變量名) a算符(加) +整數(shù) 2界符 ；102.語(yǔ)法分析（語(yǔ)法分析（Syntax analysis或或Parsing）語(yǔ)法分析是編譯過(guò)程的一個(gè)邏輯階段。語(yǔ)法分析是編譯過(guò)程的一個(gè)邏輯階段。語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類(lèi)語(yǔ)法短語(yǔ)，如列組合成各類(lèi)語(yǔ)法短語(yǔ)，如“程序程序”，“語(yǔ)句語(yǔ)句”，“表達(dá)式表達(dá)式”等等。語(yǔ)法分析程序判斷源程序在結(jié)等等。語(yǔ)法分析程序判斷源程序在結(jié)構(gòu)上是否正確。構(gòu)上

7、是否正確。源程序的結(jié)構(gòu)由上下文無(wú)關(guān)文法描述。語(yǔ)法分析源程序的結(jié)構(gòu)由上下文無(wú)關(guān)文法描述。語(yǔ)法分析程序可以用程序可以用YACC等工具自動(dòng)生成。等工具自動(dòng)生成。11語(yǔ)法分析器的兩個(gè)重要作用：語(yǔ)法分析器的兩個(gè)重要作用：根據(jù)詞法分析器提供的記號(hào)流，為語(yǔ)法正根據(jù)詞法分析器提供的記號(hào)流，為語(yǔ)法正確的輸入構(gòu)造分析樹(shù)（或語(yǔ)法樹(shù)）。確的輸入構(gòu)造分析樹(shù)（或語(yǔ)法樹(shù)）。檢查輸入中的語(yǔ)法（可能包括詞法）錯(cuò)誤，檢查輸入中的語(yǔ)法（可能包括詞法）錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理。并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理。下圖是語(yǔ)法分析器在編譯器模型中的位置：下圖是語(yǔ)法分析器在編譯器模型中的位置： 12語(yǔ)法分析器在編譯器模型中的位置語(yǔ)法分

8、析器在編譯器模型中的位置詞 法分析器記 號(hào)取下一個(gè)記號(hào)源程序圖1.3 語(yǔ)法分析器在編譯器模型中的位置分析樹(shù)前端其余部分語(yǔ)法分析器分析樹(shù)符號(hào)表o語(yǔ)法分析得到的語(yǔ)法短語(yǔ)也稱(chēng)為語(yǔ)法單位?？梢哉Z(yǔ)法分析得到的語(yǔ)法短語(yǔ)也稱(chēng)為語(yǔ)法單位?？梢员硎境梢豢脴?shù)。表示成一棵樹(shù)。o如：表達(dá)式如：表達(dá)式id1:=id2+id3*10 的語(yǔ)法樹(shù)如下的語(yǔ)法樹(shù)如下表達(dá)式表達(dá)式id1:=id2+id3*10 的語(yǔ)法樹(shù)的另一種表達(dá)形式：的語(yǔ)法樹(shù)的另一種表達(dá)形式：15o語(yǔ)法分析的依據(jù)：語(yǔ)言的語(yǔ)法規(guī)則。語(yǔ)法分析的依據(jù)：語(yǔ)言的語(yǔ)法規(guī)則。o每種程序設(shè)計(jì)語(yǔ)言都有描述程序語(yǔ)法結(jié)構(gòu)的規(guī)每種程序設(shè)計(jì)語(yǔ)言都有描述程序語(yǔ)法結(jié)構(gòu)的規(guī)則。例如，則。例如，

9、Pascal程序由程序塊（又叫分程序）程序由程序塊（又叫分程序）構(gòu)成，程序塊由語(yǔ)句組成，語(yǔ)句由表達(dá)式組成，構(gòu)成，程序塊由語(yǔ)句組成，語(yǔ)句由表達(dá)式組成，表達(dá)式由記號(hào)組成等等。這些規(guī)則可以用上下表達(dá)式由記號(hào)組成等等。這些規(guī)則可以用上下文無(wú)關(guān)文法或文無(wú)關(guān)文法或BNF范式（范式（Backus-Naur Form）描述。描述。16o程序的結(jié)構(gòu)通常是用遞歸規(guī)則表示的，例如：程序的結(jié)構(gòu)通常是用遞歸規(guī)則表示的，例如：o表達(dá)式的表示：表達(dá)式的表示：o任何標(biāo)識(shí)符是表達(dá)式。任何標(biāo)識(shí)符是表達(dá)式。o任何常數(shù)（整常數(shù)、實(shí)常數(shù)）是表達(dá)式。任何常數(shù)（整常數(shù)、實(shí)常數(shù)）是表達(dá)式。o若表達(dá)式若表達(dá)式1和表達(dá)式和表達(dá)式2都是表達(dá)式，那

10、么都是表達(dá)式，那么o表達(dá)式表達(dá)式1+表達(dá)式表達(dá)式2o表達(dá)式表達(dá)式1*表達(dá)式表達(dá)式2o（表達(dá)式（表達(dá)式1）o都是表達(dá)式。都是表達(dá)式。o類(lèi)似地語(yǔ)句的表示：類(lèi)似地語(yǔ)句的表示：o標(biāo)識(shí)符標(biāo)識(shí)符:=表達(dá)式表達(dá)式 是語(yǔ)句。是語(yǔ)句。owhile (表達(dá)式表達(dá)式) do 語(yǔ)句語(yǔ)句 和和if (表達(dá)式表達(dá)式) then 語(yǔ)句語(yǔ)句 else 語(yǔ)句語(yǔ)句都是語(yǔ)句。都是語(yǔ)句。173.語(yǔ)義分析語(yǔ)義分析o語(yǔ)義分析階段的任務(wù)是審查源程序有無(wú)語(yǔ)義錯(cuò)誤，為代碼生成階段收集類(lèi)型信息。比如，語(yǔ)義分析的一個(gè)工作是進(jìn)行進(jìn)行類(lèi)型審查。源程序中有些語(yǔ)法成分，按照語(yǔ)法規(guī)則去判斷，它是正確的，但它不符合語(yǔ)義規(guī)則。比如使用了沒(méi)有聲明的變量；或者給一

11、個(gè)過(guò)程名賦值；或者調(diào)用函數(shù)時(shí)參數(shù)類(lèi)型不合適或者參加運(yùn)算的兩個(gè)變量類(lèi)型不匹配等等。比如下邊的程序片段： o int arr2,c; c = arr1 * 10 ;其中的賦值語(yǔ)句是符合語(yǔ)法規(guī)則的，但是因?yàn)闆](méi)有聲明變量arr1，而存在語(yǔ)義錯(cuò)。 o又比如某些語(yǔ)言規(guī)定運(yùn)算對(duì)象可以被強(qiáng)制又比如某些語(yǔ)言規(guī)定運(yùn)算對(duì)象可以被強(qiáng)制,那么當(dāng)二目運(yùn)算那么當(dāng)二目運(yùn)算施于一整型和一實(shí)型對(duì)象時(shí)施于一整型和一實(shí)型對(duì)象時(shí),編譯程序?qū)⒄娃D(zhuǎn)化為實(shí)型而編譯程序?qū)⒄娃D(zhuǎn)化為實(shí)型而不認(rèn)為是源程序的錯(cuò)誤，假如語(yǔ)句不認(rèn)為是源程序的錯(cuò)誤，假如語(yǔ)句sum := first + count * 10中中* 的兩個(gè)運(yùn)算對(duì)象：的兩個(gè)運(yùn)算對(duì)象： co

12、unt是實(shí)型，是實(shí)型，10是整型，則在是整型，則在語(yǔ)義分析階段進(jìn)行類(lèi)型審查之后，在語(yǔ)法分析得到的分析語(yǔ)義分析階段進(jìn)行類(lèi)型審查之后，在語(yǔ)法分析得到的分析樹(shù)上增加一語(yǔ)義處理結(jié)點(diǎn)，表示整型轉(zhuǎn)化實(shí)型的一目運(yùn)算樹(shù)上增加一語(yǔ)義處理結(jié)點(diǎn)，表示整型轉(zhuǎn)化實(shí)型的一目運(yùn)算符符inttoreal,其樹(shù)如下：其樹(shù)如下：194.中間代碼生成中間代碼生成o在進(jìn)行了上述的詞法分析，語(yǔ)法分析和語(yǔ)義分析階在進(jìn)行了上述的詞法分析，語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語(yǔ)言或中部表示形式，這種內(nèi)部表示形式叫做中間語(yǔ)言或中間代碼。

13、間代碼。o所謂所謂“中間代碼中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，重要的設(shè)計(jì)原則為兩點(diǎn)：一是容易生成；二是容易重要的設(shè)計(jì)原則為兩點(diǎn)：一是容易生成；二是容易將它翻譯成目標(biāo)代碼。很多編譯程序采用了一種近將它翻譯成目標(biāo)代碼。很多編譯程序采用了一種近似似“三地址指令三地址指令”的的“四元式四元式”中間代碼，這種四中間代碼，這種四元式的形式為：元式的形式為：o(運(yùn)算符，運(yùn)算對(duì)象運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象，運(yùn)算對(duì)象2，結(jié)果，結(jié)果)。20215.代碼優(yōu)化代碼優(yōu)化o代碼優(yōu)化階段的任務(wù)是對(duì)前

14、階段產(chǎn)生的中代碼優(yōu)化階段的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行變換或進(jìn)行改造，目的是使生間代碼進(jìn)行變換或進(jìn)行改造，目的是使生成的目標(biāo)代碼更為高效，即省時(shí)間和省空成的目標(biāo)代碼更為高效，即省時(shí)間和省空間，或兩者都有。間，或兩者都有。 22依據(jù)優(yōu)化所涉及的程序范圍，又可分為局部?jī)?yōu)化、依據(jù)優(yōu)化所涉及的程序范圍，又可分為局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。循環(huán)優(yōu)化和全局優(yōu)化三個(gè)不同的級(jí)別。236.目標(biāo)代碼生成目標(biāo)代碼生成o目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。

15、這是編譯的最后階段，代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類(lèi)型變件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類(lèi)型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。調(diào)度等。2425o上述編譯過(guò)程的六個(gè)階段的任務(wù)，再加上用表格管理程序建立變量、常量和過(guò)程標(biāo)識(shí)符的說(shuō)明與引用之間的信息聯(lián)系等，用出錯(cuò)處理程序?qū)υ~法和語(yǔ)法分析遇到的錯(cuò)誤給出在源程序中出錯(cuò)的錯(cuò)誤性質(zhì)、位置等，可分別由幾

16、個(gè)模塊或程序完成，它們分別稱(chēng)作詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和出錯(cuò)處理程序。從而可給出一個(gè)典型的編譯程序結(jié)構(gòu)框圖，如圖1-3-1所示 261.2.3編譯階段的組合編譯階段的組合o在前面所討論的編譯過(guò)程中階段的劃分是編譯程序的邏輯在前面所討論的編譯過(guò)程中階段的劃分是編譯程序的邏輯組織。有時(shí)，常常把編譯的過(guò)程分為前端組織。有時(shí)，常常把編譯的過(guò)程分為前端(front end)和后和后端端(back end)，前端的工作主要依賴(lài)于源語(yǔ)言而與目標(biāo)機(jī)，前端的工作主要依賴(lài)于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)無(wú)關(guān), 后端工作依賴(lài)于目標(biāo)機(jī)而一般不依賴(lài)源

17、語(yǔ)言后端工作依賴(lài)于目標(biāo)機(jī)而一般不依賴(lài)源語(yǔ)言.通常前通常前端包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成這端包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成這些階段，某些優(yōu)化工作些階段，某些優(yōu)化工作, 即中間代碼優(yōu)化也可在前端做，也即中間代碼優(yōu)化也可在前端做，也包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符號(hào)表管理等包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符號(hào)表管理等工作。后端工作包括目標(biāo)代碼生成和目標(biāo)代碼優(yōu)化，以及工作。后端工作包括目標(biāo)代碼生成和目標(biāo)代碼優(yōu)化，以及相關(guān)出錯(cuò)處理和符號(hào)表操作。相關(guān)出錯(cuò)處理和符號(hào)表操作。 27遍遍o一個(gè)編譯過(guò)程可由一遍、兩遍或多遍完成。一個(gè)編譯過(guò)程可由一遍、兩遍或多遍完成。

18、所謂所謂“遍遍”，也稱(chēng)作，也稱(chēng)作“趟趟”，是對(duì)源程序或其等價(jià)的中間，是對(duì)源程序或其等價(jià)的中間語(yǔ)言程序從頭到尾掃視并完成規(guī)定任務(wù)的過(guò)程。語(yǔ)言程序從頭到尾掃視并完成規(guī)定任務(wù)的過(guò)程。每一每一遍掃視可完成上述一個(gè)階段或多個(gè)階段的工作。例如遍掃視可完成上述一個(gè)階段或多個(gè)階段的工作。例如一遍可以只完成詞法分析工作；一遍完成詞法分析和一遍可以只完成詞法分析工作；一遍完成詞法分析和語(yǔ)法分析工作；甚至一遍完成整個(gè)編譯工作。對(duì)于多語(yǔ)法分析工作；甚至一遍完成整個(gè)編譯工作。對(duì)于多遍的編譯程序，第一遍的輸入是用戶(hù)書(shū)寫(xiě)的源程序，遍的編譯程序，第一遍的輸入是用戶(hù)書(shū)寫(xiě)的源程序，最后一遍的輸出是目標(biāo)語(yǔ)言程序，其余是上一遍的輸最

19、后一遍的輸出是目標(biāo)語(yǔ)言程序，其余是上一遍的輸出為下一遍的輸入。出為下一遍的輸入。 o在實(shí)際的編譯系統(tǒng)的設(shè)計(jì)中，編譯的幾個(gè)階段的工作究竟應(yīng)該怎樣組合，即編譯程序究竟分成幾遍，參考的因素主要是源語(yǔ)言和機(jī)器（目標(biāo)機(jī)）的特征。o比如源語(yǔ)言的結(jié)構(gòu)直接影響編譯的遍的劃分； 像PL/1或ALGOL68那樣的語(yǔ)言，允許名字的說(shuō)明出現(xiàn)在名字的使用之后，那么在看到名字之前是不便為包含該名字的表達(dá)式生成代碼的，這種語(yǔ)言的編譯程序至少分成兩遍才容易生成代碼。另外機(jī)器的情況，即編譯程序工作的環(huán)境也影響編譯程序的遍數(shù)的劃分。一個(gè)多遍的編譯程序可以較之一遍的編譯程序少占內(nèi)存，遍數(shù)多一點(diǎn)，整個(gè)編譯程序的邏輯結(jié)構(gòu)可能清晰些，但

20、遍數(shù)多即意味著增加讀寫(xiě)中間文件的次數(shù)，勢(shì)必消耗較多時(shí)間，顯然會(huì)比一遍的編譯要慢。291.3 解釋程序和一些軟件工具解釋程序和一些軟件工具o1.3.1解釋程序解釋程序o為了實(shí)現(xiàn)在一個(gè)計(jì)算機(jī)上運(yùn)行高級(jí)語(yǔ)言的程序?yàn)榱藢?shí)現(xiàn)在一個(gè)計(jì)算機(jī)上運(yùn)行高級(jí)語(yǔ)言的程序,主要有兩個(gè)途徑：主要有兩個(gè)途徑：o第一個(gè)途徑是把該程序翻譯為這個(gè)計(jì)算機(jī)的指令代碼序列，這就是我第一個(gè)途徑是把該程序翻譯為這個(gè)計(jì)算機(jī)的指令代碼序列，這就是我們已經(jīng)描述的編譯過(guò)程。們已經(jīng)描述的編譯過(guò)程。o第二個(gè)途徑是編寫(xiě)一個(gè)程序，它解釋所遇到的高級(jí)語(yǔ)言程序中的語(yǔ)句第二個(gè)途徑是編寫(xiě)一個(gè)程序，它解釋所遇到的高級(jí)語(yǔ)言程序中的語(yǔ)句并且完成這些語(yǔ)句的動(dòng)作，這樣的程

21、序就叫并且完成這些語(yǔ)句的動(dòng)作，這樣的程序就叫解釋程序解釋程序。從功能上說(shuō)，。從功能上說(shuō)，一個(gè)解釋程序能讓計(jì)算機(jī)執(zhí)行高級(jí)語(yǔ)言。它與編譯程序的主要不同是一個(gè)解釋程序能讓計(jì)算機(jī)執(zhí)行高級(jí)語(yǔ)言。它與編譯程序的主要不同是它不生成目標(biāo)代碼，它每遇到一個(gè)語(yǔ)句，就要對(duì)這個(gè)語(yǔ)句進(jìn)行分析以它不生成目標(biāo)代碼，它每遇到一個(gè)語(yǔ)句，就要對(duì)這個(gè)語(yǔ)句進(jìn)行分析以決定語(yǔ)句的含義，執(zhí)行相應(yīng)的動(dòng)作。決定語(yǔ)句的含義，執(zhí)行相應(yīng)的動(dòng)作。30o用一圖來(lái)表示如下用一圖來(lái)表示如下:31o編譯系統(tǒng)生成的目標(biāo)代碼由計(jì)算機(jī)執(zhí)行才能生成結(jié)果。使用編譯系統(tǒng)時(shí)會(huì)區(qū)分編譯階段和運(yùn)行階段，編譯階段對(duì)源程序進(jìn)行編譯，運(yùn)行階段是指目標(biāo)程序的運(yùn)行。o而解釋系統(tǒng)則是邊解

22、釋邊執(zhí)行。從存儲(chǔ)組織來(lái)看，在編譯階段，存儲(chǔ)區(qū)一般要有源程序緩沖區(qū)，目標(biāo)代碼緩沖區(qū)，名字表以及編譯程序使用的源程序中間表示和各種表格等等。在運(yùn)行階段，存儲(chǔ)區(qū)只有目標(biāo)代碼和數(shù)據(jù)區(qū)了。對(duì)解釋系統(tǒng)來(lái)說(shuō)，在它工作的自始至終，存儲(chǔ)區(qū)中要有源程序，名字表，標(biāo)號(hào)表等表格，輸入輸出緩沖區(qū)以及數(shù)據(jù)區(qū)等等 o解釋執(zhí)行解釋執(zhí)行 不生成目標(biāo)代碼 能支持交互環(huán)境（同增量式編譯系統(tǒng)） 優(yōu)點(diǎn)：交互方便，節(jié)省空間。缺點(diǎn)：效率低。因?qū)υ闯绦虻难h(huán)語(yǔ)句部分要反復(fù)解釋執(zhí)行。共同點(diǎn)：都需進(jìn)行詞法、語(yǔ)法、語(yǔ)義分析?？杀扔鳛椋壕幾g是筆譯（產(chǎn)生目標(biāo)程序）解釋是口譯（不產(chǎn)生目標(biāo)程序） 很多語(yǔ)言如BASIC,LISP和PROLOG等等最初都是解

23、釋執(zhí)行的，后來(lái)也都有了編譯系統(tǒng)。號(hào)稱(chēng)最具生命力的JAVA環(huán)境同時(shí)需要解釋和編譯系統(tǒng)的支持 1.4 編譯器中的主要數(shù)據(jù)結(jié)構(gòu)編譯器中的主要數(shù)據(jù)結(jié)構(gòu)o(1) 記號(hào)（t o k e n）o當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)；這也就是說(shuō)，作為一個(gè)枚舉數(shù)據(jù)類(lèi)型的值來(lái)表示源程序的記號(hào)集。有時(shí)還必須保留字符串本身或由此派生出的其他信息（例如：與標(biāo)識(shí)符記號(hào)相關(guān)的名字或數(shù)字記號(hào)值）。在大多數(shù)語(yǔ)言中，掃描程序一次只需要生成一個(gè)記號(hào)（這稱(chēng)為單符號(hào)先行（ single symbol lookahead）。在這種情況下，可以用全程變量放置記號(hào)信息；而在別的情況（最為明顯的是FORT RAN）下

24、，則可能會(huì)需要一個(gè)記號(hào)數(shù)組。o(2) 語(yǔ)法樹(shù)（syntax tree）o如果分析程序確實(shí)生成了語(yǔ)法樹(shù)，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動(dòng)態(tài)分配該結(jié)構(gòu)，則整棵樹(shù)可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的語(yǔ)義分析程序收集的信息。例如，一個(gè)表達(dá)式的數(shù)據(jù)類(lèi)型可作為表達(dá)式的語(yǔ)法樹(shù)節(jié)點(diǎn)中的域。有時(shí)為了節(jié)省空間，這些域也是動(dòng)態(tài)分配或存放在諸如符號(hào)表的其他數(shù)據(jù)結(jié)構(gòu)中，這樣就可以有選擇地進(jìn)行分配和釋放。實(shí)際上，根據(jù)它所表示的語(yǔ)言結(jié)構(gòu)的類(lèi)型（例如：表達(dá)式節(jié)點(diǎn)對(duì)于語(yǔ)句節(jié)點(diǎn)或聲明節(jié)點(diǎn)都有不同的要求），每一個(gè)語(yǔ)法樹(shù)節(jié)點(diǎn)本身都可能要求存儲(chǔ)不同的屬性。在這

25、種情況下，可由不同的記錄表示語(yǔ)法樹(shù)中的每個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)類(lèi)型只包含與本身相關(guān)的信息。o(3) 符號(hào)表（symbol table）o這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識(shí)符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類(lèi)型。符號(hào)表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)義分析程序?qū)⒃黾訑?shù)據(jù)類(lèi)型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號(hào)表提供的信息選出恰當(dāng)?shù)拇a。因?yàn)閷?duì)符號(hào)表的訪問(wèn)如此頻繁，所以插入、刪除和訪問(wèn)操作都必須比常規(guī)操作更有效。盡管可以使用各種樹(shù)的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時(shí)在一個(gè)列表或棧中可使用若干個(gè)表格。o(4) 常數(shù)表（literal table）o常數(shù)表的功能是存放在程序中用到的