第1章編譯原理答案(主編張晶)

《編譯原理》

教師：王文晶為什么要學(xué)習(xí)編譯原理必修主干課程：操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計者與計算機之間的基本界面。通過學(xué)習(xí)該課程，掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機理。能運用所學(xué)技術(shù)解決實際問題，能獨立編寫一個小型編譯系統(tǒng)。此外，通過學(xué)習(xí)編譯原理可以更好地理解程序語言的內(nèi)部機制,從而更好地理解和運用程序設(shè)計語言。能運用編譯程序構(gòu)造的原理和技術(shù)完成相關(guān)軟件工具的設(shè)計和開發(fā)工作。學(xué)習(xí)方法平時（40%）一本教材，認(rèn)真聽課：以講義為主，板書為輔---做適當(dāng)?shù)墓P記上機（編程+練習(xí)20分）+考勤（10分）+作業(yè)（實驗報告、隨堂作業(yè)10分）課程特點：理論性強，算法復(fù)雜補充：公共郵箱wwjjsj@163.com密碼20122012

期末（60%）:閉卷筆試編譯理論自動機和形式語言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)素材基礎(chǔ)控制對象編譯原理與其它課程關(guān)系要求先學(xué)習(xí)以下課程1.程序設(shè)計語言2.算法與數(shù)據(jù)結(jié)構(gòu)：棧分配、堆分配、靜態(tài)分配等各種存儲分配方式。線性表、二叉查找樹、哈希表等多種數(shù)據(jù)結(jié)構(gòu)。

3.離散數(shù)學(xué)：集合論與數(shù)理邏輯是進(jìn)一步學(xué)習(xí)形式語言與自動機理論的數(shù)學(xué)基礎(chǔ)。

最好學(xué)習(xí)過或同時學(xué)習(xí)以下課程1.軟件工程：掌握大型程序設(shè)計以及工程化的軟件生產(chǎn)方法。2.形式語言與自動機：相當(dāng)于本課程中詞法分析與語法分析的理論基礎(chǔ)。

第一章引言第二章文法和語言第三章詞法分析第四章語法分析—自頂向下分析方法第五章語法分析—自底向上分析方法第六章語法分析—LR方法目錄第一章引言學(xué)習(xí)目標(biāo)了解和掌握高級程序設(shè)計語言與編譯程序的關(guān)系了解和掌握編譯程序的功能

了解和掌握編譯程序的體系結(jié)構(gòu)了解和掌握編譯程序的工作過程

1.1編譯程序、匯編程序、解釋程序1.2編譯過程及結(jié)構(gòu)1.3編譯程序的組織及開發(fā)目錄低級語言（LowlevelLanguage)字位碼、機器語言、匯編語言特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、繁 瑣、費時、易出錯高級語言

--Fortran、Pascal、C語言等特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護(hù)等。1.1翻譯程序、編譯程序、解釋程序源程序

用匯編語言或高級語言編寫的程序稱為源程序目標(biāo)程序（翻譯后的程序）用目標(biāo)語言所表示的程序目標(biāo)語言：可以是介于源語言和機器語言之間的“中間語言”，可以是某種機器的機器語言,也可以是某機器的匯編語言。翻譯程序

將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。概念：源程序、翻譯程序、目標(biāo)程序三者關(guān)系：源程序翻譯程序目標(biāo)程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM輸入輸出翻譯程序（Translator）是一種程序，其輸入是某種語言的一系列語句，而其輸出則是另一種語言的一系列語句。1.1.1翻譯程序源語言程序目標(biāo)語言程序Translator輸入輸出如匯編程序：匯編語言翻譯為機器語言。編譯程序（Compiler）是一種程序。它把用高級語言寫的源程序作為數(shù)據(jù)接收，經(jīng)過翻譯轉(zhuǎn)換，產(chǎn)生面向機器的代碼作為輸出。這當(dāng)中代碼還可能要由匯編程序或裝配程序作進(jìn)一步加工，得出目標(biāo)程序，交給計算機執(zhí)行。1.1.2編譯程序高級語言源程序面向機器代碼Compiler目標(biāo)程序代碼匯編裝配源程序的編譯和運行編譯或匯編階段運行階段源程序目標(biāo)程序編譯程序或匯編程序輸出數(shù)據(jù)目標(biāo)程序+運行子程序輸入數(shù)據(jù)工作過程解釋程序（Interpreter）（類似于口譯，不生成目標(biāo)代碼）

對源程序進(jìn)行解釋執(zhí)行的程序。輸出數(shù)據(jù)解釋程序輸入數(shù)據(jù)源程序1.1.3解釋程序優(yōu)點：提供一種直接的交互調(diào)試能力，在執(zhí)行用戶程序時可以修改用戶程序。對新的類型可動態(tài)地修改，如符號的意義。提高良好的診斷信息不依賴于目標(biāo)機，移植性較好。

事實上，純粹的解釋程序并不多見，通常做某種程序的結(jié)合。編譯過程是指將高級語言程序翻譯為等價的目標(biāo)程序的過程。翻譯外文資料：1、能識別出句子中的一個單詞；2、分析句子的語法結(jié)構(gòu)；3、根據(jù)句子的含義進(jìn)行初步翻譯；4、對譯文進(jìn)行修飾；5、寫出最后的譯文。1.2編譯程序的基本結(jié)構(gòu)翻譯和編譯工作的比較翻譯外文編譯程序分析識別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成符號表管理源程序目標(biāo)代碼生成目標(biāo)程序出錯處理詞法分析優(yōu)化語義分析語法分析編譯過程1.2.1詞法分析任務(wù)所做轉(zhuǎn)換依據(jù)構(gòu)詞規(guī)則主要理論基礎(chǔ)自動機理論源程序字符串單詞符號輸入源程序；掃描、分解字符串，識別出一個個單詞（定義符、標(biāo)識符、運算符、界符、常數(shù)）概念單詞token：是語言的基本語法單位保留字reservedword(有時也叫關(guān)鍵字)

（如:if、else、while）標(biāo)識符identifier（如:max、min、str）常數(shù)（如:12、6.8）分界符(有時也叫運算符)（如:+、-、*、/、;、（、））示例FORK:=1TO100M:=I+10*KN:=J+10*KNEXTKTONEXTFORKNMIJKKK:=100:=:=11010+**+關(guān)鍵字標(biāo)識符分界符運算符常數(shù)詞法分析程序的結(jié)果-----二元式(如：FORK:=1TO100)單詞值單詞類別FOR關(guān)鍵字K標(biāo)識符:=分界符1常數(shù)TO關(guān)鍵字100常數(shù)…..……1.2.2語法分析任務(wù)所做轉(zhuǎn)換依據(jù)語法規(guī)則主要理論基礎(chǔ)上下文無關(guān)文法單詞符號語法單位（語法范疇）在詞法分析基礎(chǔ)上，將單詞符號串轉(zhuǎn)化為語法單位（語法范疇）（短語、子句、句子、程序段、程序），并確定整個輸入串是否構(gòu)成語法上正確的程序。如：Thislineisalongersentence語法分析又例：position:=initial+rate*60;（Pascal）規(guī)則<賦值語句>::=<標(biāo)識符>“:=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”<表達(dá)式>::=<標(biāo)識符><表達(dá)式>::=<整數(shù)><表達(dá)式>::=<實數(shù)>

賦值語句標(biāo)識符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符:=表達(dá)式*id1:=id2+id3*N :=+N60*id1Positionid2initialid3rate進(jìn)一步分析語法結(jié)構(gòu)正確的程序是否符合源程序的上下文約束、運算相容性等規(guī)定。審查靜態(tài)語義使用的變量聲明了嗎？允許操作的運算對象嗎？類型正確嗎？…1.2.3語義分析

語義分析句子的結(jié)構(gòu)理解了，撲捉它的“含義”如：杰克說杰瑞把他的作業(yè)落在了家里?！八摹笔钦l的？又：杰克說杰克把他的作業(yè)落在了家里。幾個杰克？語義分析杰克把她的作業(yè)落在了家里。（杰克是男生）“杰克”和“她的”不一致?！敖芸恕焙汀八摹辈牌ヅ湔Z義分析（語言的規(guī)定和實現(xiàn)）intarr[2],c;c=arr*10;

“中間代碼”是一種含義明確、便于處理的記號系統(tǒng)。如：三元式、四元式、逆波蘭式。例：四元式（運算符，第一運算量，第二運算量，結(jié)果）

x:=a*b+c（*，a，b，T1）（+，T1,c,T2）(:=,T2,-，x)1.2.4中間代碼 id1:=id2+id3*60(1) (inttoreal, 60 - t1 )(2) (* , id3 t1 t2 )(3) (+ , id2 t2 t3 )(4) (:= , t3 - id1 )1.2.5代碼優(yōu)化任務(wù)所做轉(zhuǎn)換依據(jù)程序等價變換規(guī)則主要理論基礎(chǔ)數(shù)據(jù)流方程中間代碼中間代碼（優(yōu)化后）對于代碼（主要是中間代碼）進(jìn)行加工變換，以期能夠產(chǎn)生更為高效（省時間和空間）的目標(biāo)代碼。代碼優(yōu)化 id1:=id2+id3*60(1) (inttoreal 60 - t1 )(2) (* id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1 )變換（1）(* id3 60.0 t1 )(2）（+ id2 t1 id1 )1.2.6目標(biāo)代碼生成任務(wù)所做轉(zhuǎn)換依據(jù)硬件體系結(jié)構(gòu)、指令系統(tǒng)中間代碼目標(biāo)代碼將中間代碼變換成特定機器上的低級語言代碼目標(biāo)代碼形式絕對指令、可重定位指令、匯編指令(* , id3 60.0 t1 )(+ , id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addf R2,R1movf R1,id16.目標(biāo)代碼生成按邏輯功能不同，可將編譯過程劃分為五個基本階段，與此相對應(yīng)，我們將實現(xiàn)整個編譯過程的編譯程序劃分為五個邏輯階段（即五個邏輯子過程）。每個階段中都要有，符號表管理和錯誤處理診察錯誤，并能報告用戶錯誤性質(zhì)和位置出錯處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個重要指標(biāo)。填表：把源程序中的信息和編譯過程中所產(chǎn)生的信息登記在表格中查表：在隨后的編譯過程中同時又要不斷的查找這些表格中的信息1.2.7符號表管理1.2.8錯誤處理目標(biāo)代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序編譯過程小結(jié)S.PO.P1.3編譯程序的組織及開發(fā)編譯程序是一個非常復(fù)雜的軟件系統(tǒng)，雖然編譯理論和技術(shù)不斷發(fā)展，開發(fā)周期縮短，但研制仍需大量時間。追求目標(biāo)過程自動化。

根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端前端：通常將與源程序有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成 ---分析部分特點：與源語言有關(guān)后端：與目標(biāo)機有關(guān)的部分稱為后端。代碼優(yōu)化、代碼生成---綜合部分特點：與目標(biāo)機有關(guān)編譯程序的前端和后端.java

java源程序文件.class二進(jìn)制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯同一前端+不同后端不同機器構(gòu)成同一語言的編譯程序例如Java語言

同一前端+不同后端不同機器構(gòu)成同一語言的編譯程序例如.NET框架

不同前端+同一后端同一機器生成幾個語言的編譯程序例如GCC

第一遍 第二遍 ……

S.P中間形式1S.P中間形式2C2C1S.PO.P對源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍。遍上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。一遍掃描即可完成整個編譯工作的稱為一遍掃描編譯程序遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡、目標(biāo)程序質(zhì)量的高低）

優(yōu)點：1、減少對內(nèi)存容量的要求2、編譯程序結(jié)構(gòu)清晰、各遍功能獨立、相互聯(lián)系簡單缺點：增加讀寫中間文件的次數(shù)，降低效率應(yīng)用：大部分軟件工具的開發(fā)，都要使用編譯技術(shù)和方法語法制導(dǎo)的結(jié)構(gòu)化編輯器程序格式化工具軟件測試工具靜態(tài)分析器：不可能執(zhí)行的