《遼寧大學(xué)編譯原理課件part.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《遼寧大學(xué)編譯原理課件part.ppt（68頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2020/7/23,1,編譯原理(Principles of Compiling),主講：周翰遜 QQ：26054036,2020/7/23,2,編譯原理課程簡(jiǎn)介,地位 計(jì)算機(jī)專(zhuān)業(yè)的一門(mén)核心課程 編譯程序是計(jì)算機(jī)的重要系統(tǒng)軟件，是高級(jí)程序設(shè)計(jì)語(yǔ)言的支撐基礎(chǔ) 課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和方法,2020/7/23,3,用途與作用,這是本專(zhuān)業(yè)應(yīng)具備的基本知識(shí)，就像其他原理一樣，是基礎(chǔ)。 三大系統(tǒng)軟件： OS、DBMS、Compiling System 開(kāi)發(fā)大型系統(tǒng)軟件、工具軟件的需要。 看資料、寫(xiě)論文的需要,2020/7/23,4,編譯原理前導(dǎo)課程,前導(dǎo)課程及涉及內(nèi)容 組成原理計(jì)算機(jī)組

2、成及結(jié)構(gòu) 微機(jī)原理匯編語(yǔ)言與機(jī)器語(yǔ)言 離散數(shù)學(xué)推理知識(shí)及其完備性 數(shù)據(jù)結(jié)構(gòu)樹(shù)、表等的表示與實(shí)現(xiàn) 操作系統(tǒng)提供虛擬機(jī)和系統(tǒng)調(diào)用 高級(jí)程序設(shè)計(jì)語(yǔ)言語(yǔ)言定義和編程,2020/7/23,5,意義: 學(xué)習(xí)編譯程序構(gòu)造原理，技術(shù) 更好地理解高級(jí)語(yǔ)言 編譯的原理和方法有助于構(gòu)造一些實(shí)用的工具,2020/7/23,6,課程特點(diǎn): 理解性 技術(shù)性 考核： 筆試 80% 平時(shí)出勤+作業(yè) 20%,2020/7/23,7,學(xué)時(shí)與參考教材,學(xué)時(shí)：51學(xué)時(shí)(15周)，4學(xué)時(shí) 參考教材： 1、陳火旺等，程序設(shè)計(jì)語(yǔ)言編譯原理（第3版），國(guó)防工業(yè)出版社，2003.8.印刷 2、高仲儀、金茂忠，編譯原理及編譯程序構(gòu)造

3、，北航出版社。 3、 龍書(shū)：Alfred Aho ect.， 編譯原理，李建中等譯，機(jī)械工業(yè)出版社，2003.8.(原版-郵電出版社) 4、Kenneth C. Louden，編譯原理及實(shí)踐，馮博琴等譯，機(jī)械工業(yè)出版社，2001.2.印刷,2020/7/23,8,學(xué)時(shí)與參考教材,參考教材(續(xù))： 5、金成植，編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)，高等教育出版社，2000.7. 6、高仲儀等，編譯技術(shù)，西北工業(yè)大學(xué)出版社，1985.9 7、何炎祥等，編譯原理，華中理工大學(xué)出版社，2000.10. 8、P.M.劉易斯，編譯程序設(shè)計(jì)理論，科學(xué)出版社，1984.5. ,2020/7/23,9,陳火旺生平,陳火旺

4、（1936 02.05 - 2008 02.02）福建省安溪縣人。中國(guó)工程院院士，國(guó)防科學(xué)技 術(shù)大學(xué)計(jì)算機(jī)學(xué)院教授、博士生導(dǎo)師，于2008年2月2日因病醫(yī)治無(wú)效，在長(zhǎng)沙逝世，72歲。 1956年畢業(yè)于上海復(fù)旦大學(xué)數(shù)學(xué)系，同年加入中國(guó)共產(chǎn)黨，留校任助教。曾在北京大學(xué)數(shù)理邏輯專(zhuān)業(yè)、英國(guó)國(guó)家物理所進(jìn)修。1970年調(diào)長(zhǎng)沙工學(xué)院（后改名國(guó)防科技大學(xué)），歷任（電子）計(jì)算機(jī)系副教授、系副主任、教授、博士生導(dǎo)師、研究生院副院長(zhǎng)。1990年被授予少將軍銜。 1997年當(dāng)選為中國(guó)工程院信息與電子工程學(xué)部院士。是武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室學(xué)術(shù)委員會(huì)主任，國(guó)務(wù)院學(xué)位委員會(huì)計(jì)算機(jī)學(xué)科評(píng)議組成員，全國(guó)工科院校計(jì)算機(jī)

5、專(zhuān)業(yè)教學(xué)指導(dǎo)委員會(huì)主任，國(guó)家“863計(jì)劃”信息領(lǐng)域第一屆專(zhuān)家委員會(huì)委員，中國(guó)軟件行業(yè)協(xié)會(huì)副主任委員。 成就及榮譽(yù) 1991年被授予國(guó)家有突出貢獻(xiàn)中青年專(zhuān)家稱(chēng)號(hào)，同年獲光華科學(xué)基金一等獎(jiǎng)。長(zhǎng)期從事計(jì)算機(jī)軟件和人工智能等方面的教學(xué)和研究。建立了有限函數(shù)空間上的能行運(yùn)算和能行連續(xù)泛函理論；主持國(guó)內(nèi)第一個(gè)符號(hào)匯編語(yǔ)言和宏指令產(chǎn)生器的設(shè)計(jì)與實(shí)現(xiàn)；主持中國(guó)第一個(gè)FORTRAN編譯程序的設(shè)計(jì)，獲1978年全國(guó)科學(xué)大會(huì)獎(jiǎng)；參與領(lǐng)導(dǎo)中國(guó)第一臺(tái)巨型計(jì)算機(jī)銀河I的研制，負(fù)責(zé)軟件系統(tǒng)總體設(shè)計(jì)，獲特等國(guó)防科技成果獎(jiǎng)；主持國(guó)內(nèi)最早的一個(gè)面向?qū)ο蠹苫浖_(kāi)發(fā)環(huán)境GWOSE的研制，獲國(guó)防科工委科技進(jìn)步一等獎(jiǎng)；領(lǐng)導(dǎo)自然語(yǔ)言

6、處理的研究，研制成功英漢機(jī)器編譯系統(tǒng)MATRIX，獲全國(guó)優(yōu)秀軟件二等獎(jiǎng)；在人工智能方面主持研制的非單調(diào)推理系統(tǒng)1993年獲國(guó)防科工委科技進(jìn)步一等獎(jiǎng)。撰有能行連續(xù)泛函、串行運(yùn)算向量化等論文、研究報(bào)告60余篇；主編有數(shù)理邏輯與控制論、程序設(shè)計(jì)語(yǔ)言編譯原理、程序設(shè)計(jì)方法學(xué)基礎(chǔ)等。 陳火旺院士為我國(guó)計(jì)算機(jī)軟件與理論學(xué)科的建立和發(fā)展作出了貢獻(xiàn)，為國(guó)家、軍隊(duì)和學(xué)校人才培養(yǎng)、科學(xué)研究作出了貢獻(xiàn)。,2020/7/23,10,主要內(nèi)容,編譯系統(tǒng)及其設(shè)計(jì)概述(總體結(jié)構(gòu)、設(shè)計(jì)方法；3) 語(yǔ)言與文法(文法、推導(dǎo)、歸約、分類(lèi)、分析樹(shù)；5) 詞法分析(詞法分析、正規(guī)式與正規(guī)文法、DFA狀態(tài)轉(zhuǎn)移圖；8) 語(yǔ)法分析(自頂向下

7、：LL(1)、遞歸子程序；自底向上：算符優(yōu)先、LR；15) 語(yǔ)義分析(屬性文法、各種語(yǔ)句的語(yǔ)法制導(dǎo)翻譯；12) 運(yùn)行環(huán)境(存儲(chǔ)分配、過(guò)程調(diào)用、符號(hào)表管理；3) 無(wú)：代碼優(yōu)化與代碼生成(基本塊與流圖、局部?jī)?yōu)化、馴化優(yōu)化、代碼生成；2) 總結(jié)(2),2020/7/23,11,教學(xué)目的計(jì)算學(xué)科是一個(gè)寬泛的學(xué)科,用戶(hù),,多層虛擬系統(tǒng) ,開(kāi)發(fā)利用,工程實(shí)現(xiàn),計(jì)算機(jī)理,呈現(xiàn)抽象、理論、設(shè)計(jì)三種學(xué)科形態(tài),性能越來(lái)越好 使用越來(lái)越方便,,2020/7/23,12,教學(xué)目的計(jì)算學(xué)科的定義,關(guān)鍵：由計(jì)算機(jī)自動(dòng)完成/實(shí)現(xiàn)自動(dòng)計(jì)算 對(duì)信息描述和變換算法的系統(tǒng)研究，主要包括它們的理論、分析、效率、實(shí)現(xiàn)和應(yīng)用 計(jì)算學(xué)科的

8、根本問(wèn)題是什么能且如何被有效地自動(dòng)計(jì)算 討論問(wèn)題求解的“能行性”,2020/7/23,13,教學(xué)目的計(jì)算學(xué)科各有分工,科學(xué),工程,技術(shù),：發(fā)現(xiàn)規(guī)律,：構(gòu)建系統(tǒng),：實(shí)現(xiàn)服務(wù),計(jì)算學(xué)科,涉及,2020/7/23,14,教學(xué)目的學(xué)科基本特征,形式化、抽象、邏輯,符號(hào)、符號(hào)變換,特點(diǎn),表現(xiàn)形式,2020/7/23,15,教學(xué)目的計(jì)算學(xué)科本科生專(zhuān)業(yè)能力構(gòu)成,編譯原理的授課涉及上述四種能力的培養(yǎng),,計(jì)算思維 算法設(shè)計(jì) 程序?qū)崿F(xiàn) 系統(tǒng)開(kāi)發(fā),,,公共基礎(chǔ)系列 基礎(chǔ)理論系列 程序與算法系列 軟件系統(tǒng)系列 (系統(tǒng)級(jí)的再認(rèn)識(shí)與再提高) 硬件技術(shù)系列,學(xué)科基礎(chǔ)能力,工程型 應(yīng)用型,科學(xué)型,,,,,2020/7/23,

9、16,教學(xué)目的編譯原理是一門(mén)非常好的課程,Alfred V.Aho：編寫(xiě)編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個(gè)計(jì)算機(jī)科學(xué)家的研究生涯中，本書(shū)中的原理和技術(shù)都會(huì)反復(fù)用到 涉及的是一個(gè)比較適當(dāng)?shù)某橄髮用嫔系臄?shù)據(jù)變換（既抽象，又實(shí)際） 既有一些具體的表示和變換算法；又是針對(duì)一類(lèi)問(wèn)題的求解（自動(dòng)計(jì)算的具體體現(xiàn)）,2020/7/23,17,教學(xué)目的編譯原理是一門(mén)非常好的課程,一個(gè)相當(dāng)規(guī)模的、邏輯結(jié)構(gòu)清晰系統(tǒng)的設(shè)計(jì)（含總體結(jié)構(gòu)） “自頂向下”和“自底向上”的系統(tǒng)設(shè)計(jì)方法（思想、方法、實(shí)現(xiàn)） 結(jié)論：計(jì)算機(jī)專(zhuān)業(yè)最恰當(dāng)、有效的知識(shí)載體之一 編譯：掌握“編譯原理”中的基本概念、基本理論、基本方法，在系

10、統(tǒng)級(jí)上再認(rèn)識(shí)程序和算法，提升計(jì)算機(jī)問(wèn)題求解的水平，增強(qiáng)系統(tǒng)能力，體驗(yàn)實(shí)現(xiàn)自動(dòng)計(jì)算的樂(lè)趣,2020/7/23,18,教學(xué)要求,知識(shí)層面 掌握編譯程序總體結(jié)構(gòu)系統(tǒng)能力基礎(chǔ) 掌握程序變換基本概念、問(wèn)題描述和處理方法，學(xué)習(xí)有關(guān)的原理、實(shí)現(xiàn)方法和技術(shù)，掌握典型方法 （自頂向下、自底向上、逐步求精、遞歸求解，目標(biāo)驅(qū)動(dòng)，問(wèn)題分析、問(wèn)題的抽象與形式化描述，算法設(shè)計(jì)與實(shí)現(xiàn)，系統(tǒng)構(gòu)建、模塊化 ） 增強(qiáng)理論結(jié)合實(shí)際能力，獲得更多的“頂峰體驗(yàn)” 程序?qū)崿F(xiàn)實(shí)現(xiàn)能力基礎(chǔ),2020/7/23,19,教學(xué)要求,能力層面 理論與實(shí)踐的結(jié)合能力：理論指導(dǎo)系統(tǒng)實(shí)現(xiàn) 系統(tǒng)能力：在系統(tǒng)級(jí)上認(rèn)識(shí)算法、系統(tǒng)的設(shè)計(jì)，從宏觀(guān)到微觀(guān)、從微觀(guān)

11、到宏觀(guān)，提高把握系統(tǒng)的能力 較大規(guī)模程序的設(shè)計(jì)與實(shí)現(xiàn) 形式化描述能力：修養(yǎng)“問(wèn)題、形式化描述、計(jì)算機(jī)化”問(wèn)題求解典型過(guò)程，推進(jìn)從“實(shí)例計(jì)算”到“類(lèi)計(jì)算”和“模型計(jì)算”的跨越 程序語(yǔ)言：兼顧語(yǔ)言描述方法、設(shè)計(jì)、應(yīng)用,2020/7/23,20,學(xué)習(xí)方法,學(xué)習(xí)是一個(gè)過(guò)程 上課、讀書(shū)、復(fù)習(xí)、做作業(yè)、討論、做實(shí)驗(yàn)、自己編程序、上機(jī)調(diào)試排錯(cuò)是絕對(duì)必要的，不可缺的 上課 課堂是本科教育的主要渠道：不要放棄自己經(jīng)過(guò)多年努力爭(zhēng)取到的權(quán)利 美國(guó)心理學(xué)家阿貝爾.梅拉別思： 信息總效果=文字27%+音調(diào)38%+面部表情35%,2020/7/23,21,學(xué)習(xí)方法,復(fù)習(xí)、做作業(yè)、討論：勤于思考 博覽、多思（學(xué)而不思則罔、

12、思而不學(xué)則??；書(shū)由厚到薄、由薄到厚）、常實(shí)踐 思考由懷疑和答案組成。懷疑是智慧的大門(mén)，知道得越多，就越會(huì)發(fā)問(wèn)，而問(wèn)題就越多。發(fā)問(wèn)使人進(jìn)步學(xué)問(wèn),2020/7/23,22,學(xué)習(xí)方法,理論：使自己“站到巨人的肩膀上”，并擁有一個(gè)“智慧的腦” 增加問(wèn)題求解和探索的主動(dòng)性 實(shí)踐：用智慧的腦，練就一雙靈巧的手，開(kāi)創(chuàng)一個(gè)新世界希望創(chuàng)新性實(shí)踐 在理論指導(dǎo)下實(shí)踐，強(qiáng)化理論與實(shí)踐相結(jié)合能力的培養(yǎng) 讀書(shū)：強(qiáng)化基礎(chǔ) 在獨(dú)立思考之前，必須先有基礎(chǔ)知識(shí)。所謂“獲得基礎(chǔ)知識(shí)”并不是形式上讀過(guò)某門(mén)課程，而是將學(xué)過(guò)的東西真正弄懂,2020/7/23,23,學(xué)習(xí)方法,加強(qiáng)實(shí)踐 “聽(tīng)過(guò)的會(huì)忘記， 看過(guò)的能記得， 做過(guò)的才理解”,教

13、了什么,學(xué)到什么,會(huì)做什么,,,2020/7/23,24,學(xué)習(xí)方法,輔導(dǎo)答疑 教師是最寶貴的資源 自己要思考，以追求最大收獲：習(xí)題、問(wèn)題 應(yīng)對(duì)困難 不畏懼困難 從教訓(xùn)到經(jīng)驗(yàn)親身體驗(yàn) 要實(shí)踐（作業(yè)、實(shí)驗(yàn)），加深理解，探討開(kāi)拓,2020/7/23,25,學(xué)生的體會(huì),向我們展示了一個(gè)原先未曾接觸過(guò)的世界。我越來(lái)越堅(jiān)信在編譯這個(gè)領(lǐng)域里，包含了太多前人的智慧 課中不時(shí)的小問(wèn)題，讓我們?nèi)プ杂伤伎?問(wèn)題不斷被解決的同時(shí)，又有一個(gè)個(gè)新的問(wèn)題提了出來(lái)，問(wèn)題的出現(xiàn)恰恰是上一個(gè)方案的不足，這個(gè)逐漸遞進(jìn)，逐漸解決問(wèn)題的過(guò)程好像踏著前人研究編譯理論的路線(xiàn)，不斷感覺(jué)大師們遇到的問(wèn)題、解決問(wèn)題的思路,2020/7/23,2

14、6,學(xué)生的體會(huì),開(kāi)闊思路，建立嚴(yán)謹(jǐn)?shù)乃伎挤椒?潛移默化地培養(yǎng)形式化描述能力和抽象思維能力, 建立和完善系統(tǒng)觀(guān)和全局觀(guān) 帶給我的不只是理論知識(shí)，更重要的是自動(dòng)計(jì)算的思路,感到了一種“自動(dòng)計(jì)算”的快樂(lè) 這門(mén)課不僅讓我對(duì)編譯器有了一個(gè)比較理性的認(rèn)識(shí)與了解，讓我提高了自己的編程能力，還讓我再次體會(huì)到了計(jì)算機(jī)學(xué)科的一些基本思想，再次感受到了人類(lèi)的偉大在于抽象的公理系統(tǒng)以及算法的巧妙,2020/7/23,27,第1章 引論,1.1 計(jì)算機(jī)語(yǔ)言的發(fā)展 1.2 翻譯系統(tǒng) 1.3 編譯系統(tǒng)的功能分析 1.4 編譯程序總體結(jié)構(gòu) 1.5 編譯程序的生成 1.6 編譯技術(shù)的應(yīng)用,2020/7/23,28,1.1 計(jì)算

15、機(jī)語(yǔ)言的發(fā)展,機(jī)器語(yǔ)言(Machine Language) 0、1代碼 匯編語(yǔ)言(Assemble Language) 0、1代碼與助記符：接近計(jì)算機(jī)硬件指令系統(tǒng) 高級(jí)語(yǔ)言(High Level Language) 語(yǔ)句定義數(shù)據(jù)、描述算法（程序） 如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作) 命令語(yǔ)言(Command) 以功能封裝為特征,2020/7/23,29,高級(jí)語(yǔ)言的分類(lèi),命令式語(yǔ)言(Imperative Language) FORTRAN(段結(jié)構(gòu))、BASIC、Pascal(嵌套結(jié)構(gòu))、C、COBOL、ALGOL 函數(shù)(應(yīng)用)式語(yǔ)言(Functi

16、onal Language) LISP、ML 邏輯式(基于規(guī)則)語(yǔ)言(Logical Language) Prolog 面向?qū)ο笳Z(yǔ)言(Object-Oriented Language) Smalltalk、 Ada(程序包)、 C++ 、Java,2020/7/23,30,1.2 翻譯系統(tǒng),翻譯程序(Translator) 將某一種語(yǔ)言描述的程序(源程序Source Program)翻譯成等價(jià)的另一種語(yǔ)言描述的程序(目標(biāo)程序Object Program)的程序,翻譯程序,,,源程序,目標(biāo)程序,(*.C / *.PAS/*.AS),(*.OBJ / *.EXE/*.*),2020/7/23,31

17、,1.2 翻譯系統(tǒng),解釋程序(Interpreter) 口譯與筆譯（單句提交與整篇提交）,源程序,輸入數(shù)據(jù),計(jì)算結(jié)果,解釋程序,2020/7/23,32,1.2 翻譯系統(tǒng),編譯程序(Compiler) 高級(jí)語(yǔ)言程序匯編/機(jī)器語(yǔ)言程序,高級(jí)語(yǔ)言源程序,匯編/機(jī)器語(yǔ)言目標(biāo)程序,編譯程序,2020/7/23,33,1.2 翻譯系統(tǒng),支撐環(huán)境、運(yùn)行庫(kù)等,,,,,,編譯系統(tǒng)(Compiling System) 編譯系統(tǒng)=編譯程序+運(yùn)行系統(tǒng),SourceProgram,Compiler,ObjectProgram,Input,RunSystem,Output,2020/7/23,34,1.2 翻譯系統(tǒng),其

18、它翻譯系統(tǒng) 診斷編譯程序（Diagnostic Compiler) 優(yōu)化編譯程序（Optimizing Compiler) 交叉編譯程序（Cross Compiler) 可變目標(biāo)編譯程序（Retargetable Compiler) 并行編譯程序（Parallelizing Compiler） 匯編程序(Assembler)、交叉匯編程序(Cross Assembler)、反匯編程序（Disassembler),2020/7/23,35,1.2 翻譯系統(tǒng)匯總,MLMLP AssemblerDisassembler AL ALP Compiler Data HLHLPInterpreterR

19、esult,,,,,,,,,,,,,M-Machine L-Languge P-Program A-Assemble H-High Level,,2020/7/23,36,1.3 編譯系統(tǒng)的功能分析,分析 詞法、語(yǔ)法、語(yǔ)義 翻譯 語(yǔ)句的翻譯、代碼生成 例如：標(biāo)識(shí)符左值與右值的綁定(binding) 變量：存儲(chǔ)單元；名字：值 函數(shù)：目標(biāo)代碼序列；名字；入口地址,2020/7/23,37,上次課主要內(nèi)容,基本概念 翻譯程序、編譯程序、解釋程序、匯編程序、其他 編譯系統(tǒng)：編譯程序+運(yùn)行系統(tǒng),1.4 編譯程序總體結(jié)構(gòu),目標(biāo)代碼生成器,代碼優(yōu)化器,語(yǔ)義分析與中間代碼生成器,語(yǔ)法分析器,2020/7/23

20、,39,1. 詞法分析,例： res=fact *(term1+term2);,結(jié)果 IDNres = IDN fact * ( IDNterm1 + IDN term2 ) ;,在機(jī)器的眼里，這只是一個(gè)字符串！,走向目標(biāo)1：變成一個(gè)單詞序列！,在機(jī)器的眼里，變成一個(gè)符號(hào)序列！,2020/7/23,40,1、詞法分析,詞法分析器 (Lexical Analyzer)又叫做掃描器(Scanner)，完成詞法分析 功能：詞法分析器從左到右掃描源程序（字符串），并將其轉(zhuǎn)換成單詞(記號(hào)Token)串；同時(shí)查詞法錯(cuò)誤，進(jìn)行標(biāo)識(shí)符登記符號(hào)表管理 輸入：字符串 輸出：(種別碼，屬性值)序?qū)?屬性值t

21、oken的機(jī)內(nèi)表示 數(shù)據(jù)結(jié)構(gòu)？,2020/7/23,41,2. 語(yǔ)法分析,res=fact*(term1+term2);,關(guān)鍵：讓系統(tǒng)知道“組成規(guī)則”并按照規(guī)則分析！,走向目標(biāo)2：得到越來(lái)越接近要表達(dá)內(nèi)容的成分！,2020/7/23,42,2、語(yǔ)法分析,語(yǔ)法分析器(Syntax Analyzer，又叫Parser ) 完成語(yǔ)法分析 功能：實(shí)現(xiàn)“組詞成句”，構(gòu)造分析樹(shù)，指出語(yǔ)法錯(cuò)誤，指導(dǎo)翻譯 輸入：Token序列 輸出：語(yǔ)法成分 數(shù)據(jù)結(jié)構(gòu)？,2020/7/23,43,3. 語(yǔ)義分析,功能：分析由語(yǔ)法分析器給出的語(yǔ)法單位的語(yǔ)義 獲取標(biāo)識(shí)符的屬性：類(lèi)型、作用域等 語(yǔ)義檢查：運(yùn)算的合法性、取值范圍等

22、子程序的靜態(tài)綁定：代碼的相對(duì)地址 變量的靜態(tài)綁定：數(shù)據(jù)的相對(duì)地址,2020/7/23,44,4. 中間代碼生成,中間代碼(intermediate Code) 例:id1+id2*id3,后綴表示(逆波蘭Reverse Polish Notation) id1id2id3 * + 前綴表示(波蘭Polish Notation) + id1*id2id3,四元組表示 (三地址碼) (*,id2,id3,T1) (+,id1 ,T1 ,T2),三地址碼的另一種表示形式 T1=id2*id3 T2=id1*T1,三元組表示 1 (* ,id2,id3) 2 (+,id1,(1)),走向目標(biāo)3：接近機(jī)

23、器的表達(dá)！,2020/7/23,45,中綴表示(Infix notation): 波蘭表示（Polish / Prefix / Parenthesis-free / Lukasiewicz notation）也就是前綴表示 逆波蘭表示(Reverse Polish / Suffix / Postfix notation) 也就是后綴表示,波蘭表示Lukasiewicz發(fā)明,2020/7/23,46,4. 中間代碼生成,其它類(lèi)型的語(yǔ)句舉例 printf(“hello”) x := s（賦值） param x（參數(shù)） call f（函數(shù)調(diào)用） s 是 hello 的地址 f 是函數(shù) printf

24、的地址,2020/7/23,47,4. 中間代碼生成,中間代碼的特點(diǎn) 簡(jiǎn)單規(guī)范 機(jī)器無(wú)關(guān) 易于優(yōu)化與轉(zhuǎn)換 輸入？ 輸出？ 數(shù)據(jù)結(jié)構(gòu)？,2020/7/23,48,對(duì)中間代碼的優(yōu)化處理:對(duì)代碼進(jìn)行等價(jià)變換以求提高執(zhí)行效率提高運(yùn)行速度和節(jié)省存儲(chǔ)空間 與機(jī)器無(wú)關(guān)的優(yōu)化 與機(jī)器有關(guān)的優(yōu)化,5. 代碼優(yōu)化,2020/7/23,49,與機(jī)器無(wú)關(guān)的優(yōu)化,局部?jī)?yōu)化 常量合并：常數(shù)運(yùn)算在編譯期間完成，如8+9*4 公共子表達(dá)式的提取:基本塊內(nèi) 循環(huán)優(yōu)化 強(qiáng)度削減 代碼外提,2020/7/23,50,與機(jī)器有關(guān)的優(yōu)化,寄存器的利用 將常用量放入寄存器，以減少訪(fǎng)問(wèn)內(nèi)存的次數(shù) 體系結(jié)構(gòu) MIMD、SIMD、SPMD、向

25、量機(jī)、流水機(jī) 存儲(chǔ)策略 根據(jù)算法訪(fǎng)存的要求安排：Cache、并行存儲(chǔ)體系減少訪(fǎng)問(wèn)沖突 任務(wù)劃分 按運(yùn)行的算法即體系結(jié)構(gòu)，劃分子任務(wù)(MPMD),走向目標(biāo)4：更高效地執(zhí)行！,2020/7/23,51,6. 目標(biāo)代碼生成,將中間代碼轉(zhuǎn)換成目標(biāo)機(jī)上的機(jī)器指令代碼或匯編代碼,走向目標(biāo)5：實(shí)現(xiàn)目標(biāo)！,2020/7/23,52,7、表格管理,管理各種符號(hào)表（常數(shù)、標(biāo)號(hào)、變量、過(guò)程、結(jié)構(gòu)） 查、填（登記、查找）源程序中出現(xiàn)的符號(hào)和編譯程序生成的符號(hào)，為編譯的各個(gè)階段提供信息 輔助語(yǔ)法檢查、語(yǔ)義檢查 完成靜態(tài)綁定、管理編譯過(guò)程 Hash表、鏈表等各種查、填表技術(shù),2020/7/23,53,8、錯(cuò)誤處理,進(jìn)行各

26、種錯(cuò)誤的檢查、報(bào)告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯(cuò)誤的定位與局部化） 詞法：拼寫(xiě)、定義、 語(yǔ)法：語(yǔ)句結(jié)構(gòu)、表達(dá)式結(jié)構(gòu)、 語(yǔ)義：類(lèi)型不匹配、,2020/7/23,54,模塊分類(lèi),編譯程序8項(xiàng)功能對(duì)應(yīng)8個(gè)模塊,翻譯,輔助,符號(hào)表管理 出錯(cuò)處理,中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成,詞法分析 語(yǔ)法分析 語(yǔ)義分析,分析,,,,,例: 一個(gè)語(yǔ)句的翻譯,position:= initial + rate * 60,詞法分析器,2020/7/23,56,9 編譯的遍（Pass）,根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求等，可以將一個(gè)編譯程序設(shè)計(jì)成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù) 遍可以和階段相對(duì)

27、應(yīng)，也可無(wú)關(guān) 單遍代碼不太優(yōu),2020/7/23,57,10、編譯的前端與后端,前端 與源語(yǔ)言有關(guān)、與目標(biāo)機(jī)無(wú)關(guān)的部分 詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、與機(jī)器無(wú)關(guān)的代碼優(yōu)化 后端 與目標(biāo)機(jī)有關(guān)的部分 與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成,2020/7/23,58,1.5 編譯程序的生成,設(shè)計(jì)目標(biāo) OP 目標(biāo)程序小，執(zhí)行速度快 Compiler 編譯程序小，執(zhí)行速度快 診斷能力強(qiáng)，可靠性高 可移植性好，可擴(kuò)充性好 如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行的代碼編制太費(fèi)力！,,2020/7/23,59, 形圖,表示語(yǔ)言翻譯的 形圖,源語(yǔ)言,表示語(yǔ)言,目標(biāo)語(yǔ)言,2020/7/23,60,1.6 編譯技

28、術(shù)的應(yīng)用,把復(fù)雜數(shù)據(jù)看作一條語(yǔ)句 數(shù)據(jù)格式的分析 利用詞法分析、語(yǔ)法分析方法 數(shù)據(jù)處理的框架 基于語(yǔ)法制導(dǎo)的語(yǔ)義處理框架 編譯技術(shù)可以用于各種復(fù)雜數(shù)據(jù)的分析處理,2020/7/23,61,4) 利用編譯程序自動(dòng)生成器,詞法分析器的自動(dòng)生成程序,,,詞法規(guī)則說(shuō)明,詞法分析程序,(C程序),輸入： 詞法（正規(guī)表達(dá)式） 識(shí)別動(dòng)作（程序段） 輸出： yylex( ) 函數(shù),LEX,2020/7/23,62,語(yǔ)法分析器的自動(dòng)生成程序,,,語(yǔ)法規(guī)則說(shuō)明,語(yǔ)法分析程序,(C程序),輸入： 語(yǔ)法規(guī)則（產(chǎn)生式） 語(yǔ)義動(dòng)作（程序段） 輸出： yyparse( ) 函數(shù),,4) 利用編譯程序自動(dòng)生成器,2020/7

29、/23,63,例1-1 DOS 命令 date輸出格式處理,例：9-2-1993、09-03-1993、9-03-93 詞法 month DIGIT DIGIT | DIGIT day DIGIT DIGIT | DIGIT year DIGIT DIGIT | DIGII DIGIT DIGIT DIGIT 語(yǔ)法 date month - day - year,2020/7/23,64,語(yǔ)義 year(年)、month(月)、day(日) 語(yǔ)義約束條件 0 < month.value < 13 0 < day.value < 32，31，30 0 < year.value < 10000,

30、例1-1 DOS 命令 date輸出格式處理,2020/7/23,65,習(xí)題,1. 什么叫編譯程序？什么叫編譯系統(tǒng)？設(shè)想當(dāng)你是C語(yǔ)言的編譯程序的設(shè)計(jì)師時(shí)，你希望給出什么樣的系統(tǒng)結(jié)構(gòu)。 2.試分析一個(gè)簡(jiǎn)短的 C 程序，找出幾個(gè)屬于語(yǔ)法、詞法、語(yǔ)義的語(yǔ)言現(xiàn)象。 3.理解交叉編譯/移植和自展技術(shù),上次課主要內(nèi)容,變成一個(gè)單詞序列,走向目標(biāo)1,一個(gè)平滑的字符流,走向目標(biāo)2,走向目標(biāo)3,走向目標(biāo)4,走向目標(biāo)5,得到語(yǔ)法成分！,更接近機(jī)器語(yǔ)言,更高的效率,達(dá)到目標(biāo),2020/7/23,67,編譯程序,上次課主要內(nèi)容,編譯程序的組織 編譯的掃描遍數(shù) 前端、后端,前端,后端,,,,中間代碼,中間代碼,優(yōu)化,中間代碼,,,2020/7/23,68,上次課主要內(nèi)容,T形圖,編譯程序?qū)崿F(xiàn)技術(shù) 移植：用“C”語(yǔ)言寫(xiě)一個(gè)“C”語(yǔ)言編譯器 現(xiàn)有編譯器的利用：用“C”語(yǔ)言寫(xiě)一個(gè)“NEW”語(yǔ)言編譯器 自展：找一個(gè)子集，開(kāi)始滾雪球 自動(dòng)生成：lex、Yacc,