高級程序語言和編譯第1頁，共28頁，2023年，2月20日，星期二第一章高級程序語言和編譯本課程解決的主要問題:–如何將源程序翻譯成功能等價的目標程序?

問題：1.高級語言源程序及語法描述。(被譯者)。

2.編譯程序的結(jié)構(gòu)及構(gòu)造。(譯者)第2頁，共28頁，2023年，2月20日，星期二一、高級程序語言及語法規(guī)則高級語言程序處理：高級語言程序－>編譯程序－>低級語言程序

(源程序) （目標程序）第3頁，共28頁，2023年，2月20日，星期二1.高級語言程序(1)程序語言：是一個記號系統(tǒng)，由語法和語義來定義。語言三大要素：語法，語義和語用：語法：由基本符號組成語法成分一組規(guī)則語義：按語法規(guī)則構(gòu)成的語法成分的意義－>靜態(tài)語義，動態(tài)語義。語用：使用者與語言符號的關(guān)系，涉及符號來源，使用和影響。高級語言程序：都可看成一給定字符集（稱為字母表）上的一個字符串。合乎語法的字符串才算一個合適的程序。（字符流）第4頁，共28頁，2023年，2月20日，星期二程序的構(gòu)成：基本字符集，單詞，句子?；咀址篈SCII表中的字符。單詞：由字符集中的字符組成的最小的語法單位。――――詞法分析的對象。 標識符 保留字（關(guān)鍵字，基本字） 常數(shù) 運算符 界符。如：，,；,括號等。句子：按語法規(guī)則由單詞組成。――語法分析的對象，語義檢查的對象。表達式，語句，分程序，函數(shù)，過程，程序等。第5頁，共28頁，2023年，2月20日，星期二(2)語法規(guī)則和語義規(guī)則a)什么是語法規(guī)則？語法規(guī)則詞法規(guī)則：單詞符號的形成規(guī)則。語法規(guī)則：規(guī)定了從單詞符號形成更大的結(jié)構(gòu)（即語法單位又稱句子）詞法和語法規(guī)則定義了程序的形式結(jié)構(gòu)，它是判斷輸入字符串是否構(gòu)成一個形式上正確的程序的依據(jù)。b)語法規(guī)則（又稱文法）的表示文法的表示BNF范式：便于存儲語法圖：直觀第6頁，共28頁，2023年，2月20日，星期二ⅰ>.BNF范式構(gòu)成：用終結(jié)符，非終結(jié)符，：：＝和︱等構(gòu)成的式子來描述文法。例：“標識符”語法成分用BNF范式表示：字母開頭的字母數(shù)字串：<標識符>：：＝<字母>|<標識符><字母>|<標識符><數(shù)字><字母>：：＝A|B|C|…|Y|Z|a|b|…|z<數(shù)字>：：＝0|1|2|3|4|5|6|7|8|9根據(jù)標識符定義，可以推出字符串a(chǎn)4是一個標識符：

<標識符>=><標識符><數(shù)字> =><標識符>4 =><字母>4 =>a4擴充的BNF范式表示文法的方法將在后面介紹。第7頁，共28頁，2023年，2月20日，星期二由箭頭，方框和圓框組成的有向圖來描述文法。方框中的符號為非終結(jié)符；圓框中的符號為終結(jié)符；箭頭指示了語法單位之間的構(gòu)成關(guān)系。例：“標識符”的語法圖標識符字母字母數(shù)字ⅱ>.語法圖第8頁，共28頁，2023年，2月20日，星期二字母ABCZaz……數(shù)字012789…第9頁，共28頁，2023年，2月20日，星期二c)語義規(guī)則定義單詞符號及語法單位的含義。（包括語句的動作含義，單詞的存儲分配的含義等）例：賦值語句，x:=x+1；求表達式x+1的值，且將該值賦給x表示的存儲單元。又如：intx;說明分配x表示的單元，該單元的存儲空間為一個整數(shù)最大值的位數(shù)。語義在文法中用屬性文法定義。第10頁，共28頁，2023年，2月20日，星期二2.程序,文法及編譯程序關(guān)系：

源程序編譯程序目標程序語言文法第11頁，共28頁，2023年，2月20日，星期二盡管只有少數(shù)人去構(gòu)造或維護編譯程序系統(tǒng)。但在軟件開發(fā)中需要用到編譯原理中的技術(shù)： 詞法分析器中的串匹配技術(shù)：用于正文編輯器，信息檢索系統(tǒng)及模式識別程序中。 上下文無關(guān)文法和語法制導(dǎo)語義：用于排版繪圖和語言結(jié)構(gòu)化編輯器的設(shè)計。 代碼優(yōu)化技術(shù)：用于程序驗證器及從非結(jié)構(gòu)化到結(jié)構(gòu)化的編輯器的開發(fā)當中。第12頁，共28頁，2023年，2月20日，星期二二、編譯程序概述1.翻譯程序的主要方法 翻譯程序的基本方法： 編譯程序法（編譯方式） 解釋程序法（解釋方式）a)編譯程序法編譯程序：將高級語言源程序翻譯成等價的機器語言或匯編語言的目標程序。處理方式：第13頁，共28頁，2023年，2月20日，星期二ii)

高級語言源程序編譯程序機器語言目標程序結(jié)果初始數(shù)據(jù)運行系統(tǒng)編譯階段運行階段第14頁，共28頁，2023年，2月20日，星期二ii)機器語言目標程序結(jié)果初始數(shù)據(jù)運行系統(tǒng)運行階段高級語言源程序編譯程序編譯階段匯編語言目標程序匯編程序匯編階段第15頁，共28頁，2023年，2月20日，星期二b)解釋程序法解釋程序：一邊解釋，一邊執(zhí)行源程序的翻譯程序。注：解釋程序不生成目標程序，而編譯程序生成目標程序。（兩者的區(qū)別）第16頁，共28頁，2023年，2月20日，星期二2.編譯程序的基本結(jié)構(gòu)編譯程序一般由五個部分組成：源程序詞法分析語法分析語義分析和中間代碼生成代碼優(yōu)化目標代碼生成表格管理出錯處理第17頁，共28頁，2023年，2月20日，星期二五個部分的工作分別由對應(yīng)的五個程序來完成：詞法分析程序，語法分析程序，語義分析及中間代碼生成程序，代碼優(yōu)化程序，目標代碼生成程序。另外再加表格管理程序和出錯處理程序――構(gòu)成編譯程序的主要組成部分。注:編譯程序各部分之間的邏輯關(guān)系，不一定是執(zhí)行時間上的順序關(guān)系?？捎脪呙璞閿?shù)及各遍掃描的工作描述各部分之間的組合。

第18頁，共28頁，2023年，2月20日，星期二一個編譯過程可由一遍、兩遍或多遍完成。所謂“遍”是對源程序或某等價的中間語言程序從頭到尾掃描并完成規(guī)定任務(wù)的過程。一遍掃描可以完成一個部分或多個部分的工作。 如：一遍掃描完成詞法分析；一遍完成詞法分析和語法分析，甚至一遍掃描完成整個編譯工作。 遍數(shù)的多少主要參考源程序和機器的特征,以及設(shè)計目標;

多遍掃描較一遍掃描編譯程序占存儲空間少，編譯程序邏輯結(jié)構(gòu)清晰，但開銷大，降低編譯效率。第19頁，共28頁，2023年，2月20日，星期二前端與后端工作的組合前端工作：主要依賴源語言而與目標機器無關(guān)的工作，包括：詞法，語法及語義及中間代碼生成，某些優(yōu)化工作（相關(guān)出錯處理和符號表管理工作）。后端工作：依賴于目標機器而與源語言無關(guān)的工作，包括：目標代碼生成工作（相應(yīng)的出錯處理及符號表管理工作）。實現(xiàn)：同一個源語言的編譯程序移植到不同機器上。方法：某一編譯程序的前端＋相應(yīng)不同的后端。在同一機器上生成幾個語言的編譯程序。方法：不同語言編譯的前端生成同一種中間語言，再使用一個共同的后端。第20頁，共28頁，2023年，2月20日，星期二3.編譯過程概述(1)詞法分析任務(wù)：對構(gòu)成源程序的字符流，從左到右進行掃描和分解，按詞法規(guī)則識別出一個一個具有獨立意義的單詞（也稱單詞符號，簡稱符號）單詞類型： 保留字（基本子，關(guān)鍵字）：for,if等。 標識符：ab等 常數(shù)：3。1415等 運算符：*，+，/等 界符：(,),；，等第21頁，共28頁，2023年，2月20日，星期二例：ifa1>0thenb:=b+3;

分解識別的單詞序列：保留字if標識符a1運算符>常數(shù)0保留字then標識符b運算符:=標識符b運算符＋

10.常數(shù)311.界符;第22頁，共28頁，2023年，2月20日，星期二(2)語法分析任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則從單詞符號串中識別出各種語法單位（如表達式，說明，語句等），并進行語法檢查。即檢查語法結(jié)構(gòu)的正確性。例：語法分析程序從下列單詞符號串：

w:=(a1+b)*c1

識別出這是一個<賦值語句>語法成分，而右邊為<表達式>語法成分。第23頁，共28頁，2023年，2月20日，星期二(3)語義分析及中間代碼的生成任務(wù)：首先對每個語法單位進行靜態(tài)的語義審查，然后分析其含義，并用中間代碼描述這種語義（如：四元式）四元式的形式： （運算符，運算對象1，運算對象2，結(jié)果）例：賦值：s:=2*3.14*r*(h+5)

語義：先計算右邊表達式的值，再將該值送到s表示的內(nèi)存單元中，翻譯后的四元表達式表示：(*,2,3.14,T1)(*,T1,r,T2)(+,h,5,T3)(*,T2,T3,T4)(:=,T4,－,S)第24頁，共28頁，2023年，2月20日，星期二其中：T1,T2,T3，T4是編譯程序引進的臨時變量，存放每條指令的運算結(jié)果。四元式表示的語義為：2*3.14＝>T1T1*r＝>T2h+5＝>T3T2*T3＝>T4T4＝>s第25頁，共28頁，2023年，2月20日，星期二(4)代碼優(yōu)化任務(wù)：對中間代碼進行等價變換或改造，以獲得省時、省空間的目標代碼。例：對上面的中間代碼優(yōu)化：(*,6.28,r,T2)(+,h,5,T3)(*,T2,T3,T4)(：=,T4,