《哈工大編譯原理》課件

《哈工大編譯原理》ppt課件目錄CONTENTS編譯原理概述詞法分析語法分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成01編譯原理概述編譯原理簡介編譯原理是計(jì)算機(jī)科學(xué)中的一個(gè)重要分支，主要研究如何將高級(jí)語言程序翻譯成低級(jí)語言程序，并優(yōu)化生成的目標(biāo)程序。編譯原理涉及多個(gè)領(lǐng)域，如語言學(xué)、計(jì)算機(jī)體系結(jié)構(gòu)、算法等，是一門綜合性很強(qiáng)的學(xué)科。編譯原理的應(yīng)用非常廣泛，如編譯器設(shè)計(jì)、程序分析、軟件工程等。編譯過程的基本概念源程序用高級(jí)語言編寫的程序，也稱為源代碼。目標(biāo)程序編譯后的程序，也稱為目標(biāo)代碼或機(jī)器代碼。編譯程序?qū)⒃闯绦蚍g成目標(biāo)程序的軟件。編譯過程將源程序通過詞法分析、語法分析、語義分析、中間代碼生成、優(yōu)化、目標(biāo)代碼生成等階段，最終生成目標(biāo)程序的過程。詞法分析器將源程序分解成一個(gè)個(gè)的單詞或符號(hào)，便于語法分析器處理。語法分析器根據(jù)語法規(guī)則將詞法分析器輸出的單詞或符號(hào)組裝成語句或表達(dá)式。語義分析器對(duì)語法分析器輸出的語句或表達(dá)式進(jìn)行語義檢查，確保其符合語義規(guī)則。中間代碼生成器將語義分析器輸出的結(jié)果轉(zhuǎn)換成中間代碼。優(yōu)化器對(duì)中間代碼進(jìn)行優(yōu)化，提高生成的目標(biāo)程序的性能。目標(biāo)代碼生成器將優(yōu)化后的中間代碼轉(zhuǎn)換成目標(biāo)程序。編譯程序的組成02詞法分析詞法分析是編譯過程中的第一個(gè)階段，主要負(fù)責(zé)將源程序的字符流分割成一個(gè)個(gè)單獨(dú)的單詞或符號(hào)。詞法分析器通常被稱為掃描器或詞法器，它不關(guān)心單詞的語法屬性，只負(fù)責(zé)識(shí)別和提取單詞。詞法分析的結(jié)果是源程序的一個(gè)標(biāo)記流，這些標(biāo)記對(duì)應(yīng)于源程序中的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)和運(yùn)算符等。010203詞法分析概述01輸入源程序的字符流。02輸出源程序的標(biāo)記流。031.初始化設(shè)置初始狀態(tài)和緩沖區(qū)。042.循環(huán)從緩沖區(qū)中取出一個(gè)字符，根據(jù)當(dāng)前狀態(tài)和該字符確定下一個(gè)狀態(tài)和標(biāo)記。053.輸出輸出當(dāng)前標(biāo)記，并更新狀態(tài)和緩沖區(qū)。064.結(jié)束條件當(dāng)緩沖區(qū)為空且所有字符都被處理時(shí)，結(jié)束詞法分析。詞法分析過程詞法分析的實(shí)現(xiàn)工具詞法分析器的實(shí)現(xiàn)可以使用工具如Lex或Flex，這些工具可以根據(jù)正則表達(dá)式自動(dòng)生成詞法分析器的代碼。狀態(tài)機(jī)詞法分析器實(shí)際上是一個(gè)狀態(tài)機(jī)，根據(jù)當(dāng)前狀態(tài)和輸入字符確定下一個(gè)狀態(tài)和輸出的標(biāo)記。正則表達(dá)式在定義詞法分析器的規(guī)則時(shí)，通常使用正則表達(dá)式來描述單詞的模式。例如，`[a-zA-Z_][a-zA-Z0-9_]*`可以匹配C語言中的標(biāo)識(shí)符。代碼生成使用工具生成的代碼通常是C語言代碼，需要將其集成到編譯器的其他部分中。03語法分析語法分析是編譯過程中的重要階段，其任務(wù)是將源程序分解成一系列的語法結(jié)構(gòu)，以便后續(xù)的語義分析和代碼生成。語法分析的結(jié)果是抽象語法樹（AbstractSyntaxTree,AST），它是源代碼的抽象語法結(jié)構(gòu)的樹狀表現(xiàn)形式。語法分析方法主要分為自頂向下和自底向上兩種。語法分析概述01自頂向下的語法分析是從源程序的頂級(jí)結(jié)構(gòu)開始，逐步向下分析。02常用的自頂向下分析算法有預(yù)測分析算法和遞歸下降分析算法。03自頂向下的語法分析方法適合于上下文無關(guān)文法的語言，如C、Java等。04該方法的優(yōu)點(diǎn)是結(jié)構(gòu)清晰，易于理解和實(shí)現(xiàn)，但可能存在無法找到最左推導(dǎo)的問題。自頂向下的語法分析01常用的自底向上分析算法有LR(0)、SLR(1)、LALR(2)等。自底向上的語法分析方法適合于處理左遞歸文法的語言，如Pascal、Fortran等。該方法的優(yōu)點(diǎn)是能夠處理更廣泛的文法結(jié)構(gòu)，但實(shí)現(xiàn)相對(duì)復(fù)雜，且可能存在無法找到最右推導(dǎo)的問題。自底向上的語法分析是從源程序的底層結(jié)構(gòu)開始，逐步向上分析。020304自底向上的語法分析04中間代碼生成中間代碼定義中間代碼是源代碼和目標(biāo)代碼之間的代碼，用于表示源程序的結(jié)構(gòu)和語義。中間代碼的作用中間代碼作為源代碼和目標(biāo)代碼之間的橋梁，有助于提高編譯器的可移植性和可維護(hù)性。中間代碼的形式常見的中間代碼形式包括三地址代碼、抽象語法樹（AST）和靜態(tài)單賦值形式（SSA）。中間代碼生成概述030201三地址代碼的特點(diǎn)三地址代碼具有簡單、直觀和易于優(yōu)化的特點(diǎn)，能夠清晰地表示程序中的控制流程和數(shù)據(jù)流。三地址代碼的生成算法常見的三地址代碼生成算法包括遞歸下降分析法和語法制導(dǎo)翻譯法。三地址代碼定義三地址代碼是一種中間代碼形式，由一系列的三元式組成，每個(gè)三元式包含三個(gè)操作數(shù)和兩個(gè)操作符。三地址代碼的生成在編譯過程中，需要識(shí)別出源程序中的循環(huán)結(jié)構(gòu)，以便進(jìn)行正確的中間代碼生成。循環(huán)結(jié)構(gòu)的識(shí)別在循環(huán)結(jié)構(gòu)中，有些變量在循環(huán)體內(nèi)被重復(fù)計(jì)算，可以將這些計(jì)算移出循環(huán)體外，以提高程序的執(zhí)行效率。循環(huán)不變量的外提循環(huán)展開是將循環(huán)體中的語句復(fù)制多份并依次執(zhí)行，以減少循環(huán)次數(shù)，提高程序的執(zhí)行效率。但是循環(huán)展開可能會(huì)增加程序的體積和降低程序的局部性。循環(huán)展開循環(huán)結(jié)構(gòu)的處理05代碼優(yōu)化代碼優(yōu)化概述030201代碼優(yōu)化是指在編譯器中，通過一系列的優(yōu)化技術(shù)，對(duì)源代碼進(jìn)行優(yōu)化，以提高生成的目標(biāo)代碼的執(zhí)行效率。代碼優(yōu)化是編譯過程中的一個(gè)重要環(huán)節(jié)，它能夠顯著提高程序的運(yùn)行效率，減少程序運(yùn)行時(shí)間，提高用戶體驗(yàn)。代碼優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類。局部優(yōu)化01局部優(yōu)化是指對(duì)程序中的某一部分進(jìn)行優(yōu)化，以提高該部分的執(zhí)行效率。02常見的局部優(yōu)化包括常量折疊、常量傳播、死代碼消除等。局部優(yōu)化的目的是減少程序中的冗余計(jì)算和不必要的操作，提高程序執(zhí)行效率。03123全局優(yōu)化是指對(duì)整個(gè)程序進(jìn)行優(yōu)化，以提高程序的總體執(zhí)行效率。全局優(yōu)化的目的是通過重新安排程序中的計(jì)算順序、減少數(shù)據(jù)訪問次數(shù)、消除無用計(jì)算等手段，提高程序的總體執(zhí)行效率。常見的全局優(yōu)化包括循環(huán)展開、循環(huán)不變量代碼外提、公共子表達(dá)式消除等。全局優(yōu)化06目標(biāo)代碼生成目標(biāo)代碼生成概述01目標(biāo)代碼生成是編譯過程的重要環(huán)節(jié)，其任務(wù)是將中間代碼轉(zhuǎn)換成目標(biāo)機(jī)器代碼或匯編語言程序。02目標(biāo)代碼生成需要考慮代碼優(yōu)化、指令選擇、內(nèi)存分配等問題，以提高生成代碼的執(zhí)行效率。03目標(biāo)代碼生成器通常采用靜態(tài)單賦值形式（SSA）表示中間代碼，以便進(jìn)行有效的優(yōu)化和轉(zhuǎn)換。代碼生成器通常由指令選擇、控制流優(yōu)化、循環(huán)優(yōu)化等模塊組成。控制流優(yōu)化模塊負(fù)責(zé)對(duì)控制流進(jìn)行分析和優(yōu)化，如消除冗余計(jì)算、消除無用代碼等。指令選擇模塊負(fù)責(zé)從中間代碼中選擇合適的機(jī)器指令，并進(jìn)行指令調(diào)度和并行化。循環(huán)優(yōu)化模塊負(fù)責(zé)對(duì)循環(huán)結(jié)構(gòu)進(jìn)行優(yōu)化，如循環(huán)展開、循環(huán)合并等。代碼生成器的構(gòu)造全局分配策略考慮整個(gè)程序的生命周期進(jìn)行寄存器分配，適用于多線程或多進(jìn)程環(huán)境下的程序。動(dòng)態(tài)分配策略在運(yùn)行時(shí)確定寄存器分配方案，適用于程序執(zhí)行路徑不確定