編譯原理C1-緒論.ppt

1、編譯原理，計(jì)算機(jī)與軟件學(xué)院盧克忠副教授手機(jī)辦公電話：26732030 QQ 33608256546郵箱3360，課程安排，B507星期二3和4；周四，5天和6天，單周：辦公樓，235實(shí)驗(yàn)室，雙周：A208，周二，14:3016:30辦公時(shí)間：701，科技大廈7樓以北，績效評估，10%出勤率和課堂表現(xiàn)，15%作業(yè)，15%實(shí)驗(yàn)，60%考試，問題和建議。手機(jī)公電話：26732030 QQ群：3216543 QQ號：8256546 Email:辦公地點(diǎn)：科技大廈7樓北側(cè)701室，建議學(xué)好這門課，注意實(shí)驗(yàn)，訓(xùn)練編程技巧，上課認(rèn)真聽講，課后不知道如何及時(shí)

2、解決問題，耐心一致，課前預(yù)習(xí)，課后復(fù)習(xí)。編譯原理課程教授如何使用計(jì)算機(jī)實(shí)現(xiàn)從編程語言到匯編語言和機(jī)器語言的自動(dòng)轉(zhuǎn)換。課程內(nèi)容包括：語法介紹和詞匯分析；單詞識別語法分析；句子識別語法指導(dǎo)翻譯；目標(biāo)代碼生成的中間代碼和符號表的代碼優(yōu)化、存儲(chǔ)組織和分發(fā)、錯(cuò)誤檢查和糾正，以及編譯原則和技術(shù)的重要性。編譯程序的構(gòu)建綜合了計(jì)算機(jī)科學(xué)的各個(gè)方面：計(jì)算機(jī)理論、程序設(shè)計(jì)和軟件工程。本課程教授的編譯程序的原理和技術(shù)具有普遍意義，是計(jì)算機(jī)工作所必需的。這些原則和技術(shù)將在計(jì)算機(jī)從業(yè)者的職業(yè)生涯中反復(fù)使用。至于編譯原理在計(jì)算機(jī)科學(xué)中的地位，國內(nèi)外許多計(jì)算機(jī)專家認(rèn)為“如果你沒有研究過編譯原理，就不能說你認(rèn)真研究過計(jì)算機(jī)科

3、學(xué)。”，張素琴等，編譯原理(第二版)，清華大學(xué)出版社，何延秀等2005，編譯原理，高等教育出版社，陳火旺等2004，程序設(shè)計(jì)語言編譯原理(第三版)，國防工業(yè)出版社，阿爾弗雷德等。2006年，編譯者3360原理、技術(shù)與工具，第二版，人民郵電出版社，編譯原理(第二版)，2008年，趙建華等譯，機(jī)械工業(yè)出版社，安德魯?shù)取?009年，現(xiàn)代編譯器在c語言中的實(shí)現(xiàn)，人民郵電出版社，現(xiàn)代編譯原理(c語言描述), 2005年，趙克佳等譯，人民郵電出版社，2006年，參考文獻(xiàn)，介紹什么是編譯器？你為什么需要編譯程序？編程語言的發(fā)展，低級語言機(jī)器語言：0，1代碼匯編語言：0，1代碼和助記符，工作高級語言，它更接近

4、計(jì)算機(jī)硬件指令系統(tǒng)，定義數(shù)據(jù)和描述算法(程序)，如C，JAVA，C，F(xiàn)ORTRAN，PASCAL，SQL，gap:機(jī)器不能理解高級語言，翻譯或解釋，解釋，解釋和翻譯(單句提交和整體提交)，源程序，輸入數(shù)據(jù)，計(jì)算結(jié)果，解釋器， 翻譯器將一種語言描述的程序(源程序)翻譯成另一種語言描述的等效程序(目標(biāo)程序)的程序。，翻譯程序，源程序，目標(biāo)程序，(*)。CPP/*。C/*。PAS/*。(*)。obj/*。exe/*。*)、編譯特殊翻譯、編譯高級語言程序(低級)匯編/機(jī)器語言程序、高級語言編程源程序編譯目標(biāo)程序輸入運(yùn)行系統(tǒng)輸出、編譯系統(tǒng))=、編譯運(yùn)行系統(tǒng)、編譯系統(tǒng)、用高級語言編寫的源代碼、符合人類閱讀

5、習(xí)慣、符合人類語法定義、使用命名結(jié)構(gòu)(如變量和過程)、便于人類使用、難于機(jī)器執(zhí)行、匯編語言或機(jī)器代碼、硬件要求包括機(jī)器指令、 寄存器和未命名的內(nèi)存地址對于人類來說難以理解，對于人類來說難以使用，對于機(jī)器來說易于執(zhí)行，匯編代碼的優(yōu)化，非優(yōu)化代碼，優(yōu)化代碼，以及編譯器的基本原理。 編譯器的設(shè)計(jì)必須遵循兩個(gè)原則：等價(jià)原則：編譯器必須保持編譯程序的意義不變，而不違背原來的意義。這個(gè)原則是編譯器設(shè)計(jì)者和編譯器用戶之間契約的核心。實(shí)用原則：優(yōu)化執(zhí)行的編譯器必須以明確的方式優(yōu)化和改進(jìn)輸入程序，如代碼優(yōu)化，如何翻譯，分析綜合，分析，中間表達(dá)，綜合，編譯程序的邏輯結(jié)構(gòu)，詞法分析器，語法分析器，語義分析器，中間代

6、碼生成，代碼優(yōu)化程序，目標(biāo)代碼生成，信息表管理程序，錯(cuò)誤檢查和處理程序，源代碼序列，目標(biāo)代碼替換，模塊分類，分析：詞法分析，語法分析， 語義分析綜合：中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成輔助：符號表管理、錯(cuò)誤檢查和處理八個(gè)功能對應(yīng)八個(gè)模塊詞法分析器，也叫掃描器，完成詞法分析功能：詞法分析器從左到右掃描源程序(字符串)并將其轉(zhuǎn)換成單詞(令牌)串； 同時(shí)，查找詞法錯(cuò)誤并管理標(biāo)識符注冊符號表。輸入：字符串輸出：(物種代碼，屬性值)在內(nèi)部表示屬性值標(biāo)記。輸入字符串：“位置=初始速率* 60”，即P，O，S，I，T，I，O，N，=，I，N，I，I，T，I，A，L、*，6，0，經(jīng)過詞法分析后，獲得以下To

7、ken):標(biāo)識符：位置，初始，速率賦值運(yùn)算符：=加法運(yùn)算符：乘法運(yùn)算符：*:number:60，詞法分析，語法分析，語法分析器，Parser完成語法分析功能：Parser實(shí)現(xiàn)“將單詞分組為句子”，構(gòu)建分析樹，指出語法錯(cuò)誤，并指導(dǎo)翻譯輸入：Token序列輸出：語法成分，賦值語句，標(biāo)識符，=，表達(dá)式，標(biāo)識符，*表達(dá)式，表達(dá)式，位置速率，數(shù)字， 60，位置=初始速率* 60，標(biāo)識符|=速率，語法分析，程序的語法結(jié)構(gòu)通常由遞歸規(guī)則定義：規(guī)則1:任意規(guī)則2:任意給定的和，那么下面也是表達(dá)式規(guī)則3:規(guī)則4: *:規(guī)則5:()，語法分析， 功能：分析語法分析器給出的語法單元的語義，以獲得標(biāo)識符的屬性：語義檢

8、查，如類型和范圍；子程序的靜態(tài)綁定，如操作合法性和數(shù)值范圍；代碼相對地址變量的靜態(tài)綁定；數(shù)據(jù)的相對地址；檢查是否有語義錯(cuò)誤并獲取類型信息。類型檢查、語義分析、位置、=、速率、*、初始、60、位置、=、速率、*、初始、60、int 2實(shí)數(shù)、中間代碼可視為抽象機(jī)器上的程序，如GCC生成的中間代碼、Java Byte。重要特性：簡單標(biāo)準(zhǔn)，機(jī)器無關(guān)，易于從語義分析階段生成，易于翻譯成目標(biāo)代碼。中間代碼有許多表示形式。反向波蘭(后綴表達(dá)式)四重三重地址碼，最大三個(gè)操作數(shù)三重兩個(gè)地址碼，最大兩個(gè)操作數(shù)流控制和過程調(diào)用，中間代碼生成，中間代碼生成，示例：id1 id2*id3，后綴表示(反向波蘭符號)id1

9、id2id3 *前綴表示(波蘭符號)id1*id2id3，四重表示(三個(gè)地址碼)1 (*，id1，id2，T1) 2(，id3，T1，T2)，三重表示1 (*，id2，id3) 2(，Id3) 其他類型的語句，例如printf(“hello”)x :=s(賦值)param x(參數(shù))調(diào)用F(函數(shù)調(diào)用)，其中s是hello的地址，F(xiàn)是printf的地址，中間代碼優(yōu)化過程：對代碼執(zhí)行等效轉(zhuǎn)換，以提高執(zhí)行效率，即，提高運(yùn)行速度，節(jié)省存儲(chǔ)空間，機(jī)器無關(guān)優(yōu)化，機(jī)器相關(guān)優(yōu)化，代碼優(yōu)化，機(jī)器無關(guān)優(yōu)化，根據(jù)優(yōu)化范圍分類，局部優(yōu)化，循環(huán)優(yōu)化， 全局優(yōu)化，優(yōu)化技術(shù)，常量合并：常量操作在編譯過程中完成，例如，8個(gè)9

10、*4公共子表達(dá)式提取，33，360基本塊內(nèi)強(qiáng)度縮減代碼提取，機(jī)器相關(guān)優(yōu)化，寄存器利用，將公共量放入寄存器，為了減少對內(nèi)存的訪問次數(shù)，根據(jù)算法對內(nèi)存訪問的要求，安排了MIMD，SIMD，SPMD，向量機(jī)和流水線機(jī)的存儲(chǔ)策略：緩存，并行存儲(chǔ)架構(gòu)，減少訪問沖突， 根據(jù)運(yùn)行算法劃分子任務(wù)(MPMD)，即體系結(jié)構(gòu)，生成目標(biāo)代碼，將中間代碼轉(zhuǎn)換為目標(biāo)機(jī)器上的機(jī)器指令代碼或匯編代碼，符號表，記錄符號及其相關(guān)屬性，如類型和范圍，對于進(jìn)程名，符號在詞法分析階段進(jìn)入符號表，其相關(guān)屬性應(yīng)在后續(xù)階段進(jìn)行補(bǔ)充。 浮動(dòng)位置，初始，速率；符號表管理，當(dāng)遇到錯(cuò)誤時(shí)，應(yīng)盡可能繼續(xù)相應(yīng)的階段。詞法分析：剩余的非單詞字符串，如3i

11、nt語義分析：語法結(jié)構(gòu)良好，但語義錯(cuò)誤，如添加兩個(gè)標(biāo)識符，但它們的類型是數(shù)組和過程。錯(cuò)誤處理、句子翻譯、編譯器組織、解析器、語義分析和代碼生成程序、詞法分析程序、目標(biāo)程序的排序、源程序、目標(biāo)程序、停止、啟動(dòng)、編譯通過、根據(jù)系統(tǒng)資源狀態(tài)、運(yùn)行目標(biāo)的要求等。編譯器可以被設(shè)計(jì)成許多每次通過可以對應(yīng)于該階段，或者它可以獨(dú)立于單次通過代碼。編譯的前端和后端，前端：與目標(biāo)機(jī)器無關(guān)的部分：與目標(biāo)機(jī)器、編譯器設(shè)計(jì)、設(shè)計(jì)目標(biāo)、目標(biāo)程序相關(guān)的部分，執(zhí)行速度快，編譯速度快，診斷能力強(qiáng)，可靠性高，可移植性和可擴(kuò)展性強(qiáng)。如何實(shí)現(xiàn)編譯器？用可運(yùn)行的代碼直接編譯太費(fèi)力了！圖，代表語言翻譯的圖，源語言，表示語言，目標(biāo)語言，交

12、叉編譯/移植，問題1:在一臺(tái)機(jī)器上有一個(gè)C語言編譯器，這個(gè)編譯器能用來在B機(jī)器上實(shí)現(xiàn)C語言編譯器嗎？條件：機(jī)器語言編譯器(P1)目的：實(shí)現(xiàn)機(jī)器語言編譯器(P3)，并使用本機(jī)編譯器。問題2:在A機(jī)上有一個(gè)C語言編譯器，現(xiàn)在有必要實(shí)現(xiàn)一個(gè)新的語言編譯器嗎？你能使用交叉編譯技術(shù)嗎？問題3:有沒有其他技術(shù)可以直接在一臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)C語言編譯器？解決方案：編譯器的一個(gè)子集(P0人)使用匯編程序來處理這個(gè)程序，并得到P2(P2:可以直接運(yùn)行)。編譯器(P3人)用P2編譯P3，得到P4。編譯器的自主開發(fā)技術(shù)采用編譯器自動(dòng)生成器、詞法分析器自動(dòng)生成器、詞法規(guī)則描述、詞法分析器(C程序)。輸入：詞法(正則表達(dá)式)識別動(dòng)作(程序段)輸出：yylex()函數(shù)，lex，自動(dòng)解析器生成器，語法規(guī)則描述，解析器，(c程序)，輸入：語法規(guī)則(生成)語義動(dòng)作(程序段)輸出：yyparse()函數(shù)，本章摘要，中間代碼生成，代碼優(yōu)化程序，目標(biāo)代碼生成，信息表管理程序，錯(cuò)誤檢查和處理程序，源序列，目標(biāo)代碼生成，第1章摘要問題。什么是翻譯、編譯和解釋程序？他們之間有什么相似之處和不同之處？編譯器通常由哪些部分組成？它和編譯系統(tǒng)有什么區(qū)別？詞匯分析的輸入、輸出和主要功能是什么？解析的輸入、輸