單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,教學(xué)進(jìn)度,計(jì)算機(jī)科學(xué)與工程系,編譯原理,(Compiler Construction),主講：方鳳美,85280320-505,信息學(xué)院,505,,,09xr2011,關(guān)于編譯原理課程,到底學(xué)什么？,為什么要學(xué)？,怎么學(xué)？,課程知識(shí)點(diǎn)前后關(guān)聯(lián)很緊密，一定要緊跟進(jìn)度。,課程介紹：,編譯原理是計(jì)算機(jī)各專業(yè)的重要專業(yè)基礎(chǔ)課，是一門涉及設(shè)計(jì)和構(gòu)造編譯程序的一般原理、基本方法和主要實(shí)現(xiàn)技術(shù)的課程。內(nèi)容主要包括：高級(jí)語言的形式化、詞法分析方法、語法分析方法、語法制導(dǎo)翻譯技術(shù)、優(yōu)化技術(shù)等。,學(xué)習(xí)指導(dǎo)：,少走彎路,:,學(xué)習(xí)編譯原理的相關(guān)建議,http:/ 徐蘭芳 駱婷 編,電子工業(yè)出版社,ISBN 978-7-121-12938-4,參考教材：,1.,程序設(shè)計(jì)語言編譯原理（第三版）,陳火旺 等編著 國防工業(yè)出版社,2.,編譯原理（,Alfred,V.Aho,等 著）,李建中等譯 機(jī)械工業(yè)出版社,圖片,教學(xué)環(huán)節(jié)：,理論教學(xué)（上課、作業(yè)）,實(shí)驗(yàn)（上機(jī)檢查、實(shí)驗(yàn)報(bào)告）,期末考試,成績評(píng)定：,平時(shí)成績：（,30%,）,實(shí)驗(yàn)、作業(yè)、課堂提問、考勤,期末考試：（,70%,）,二進(jìn)制代碼,匯編指令,用戶,高級(jí)語言程序,計(jì)算機(jī),編譯,編寫,執(zhí)行,學(xué)習(xí)內(nèi)容,第一章 編譯概述,編譯,的概念,編譯過程,編譯器的邏輯結(jié)構(gòu),編譯器的,生成,翻譯程序：將一種語言程序（源）轉(zhuǎn)換成另一種語言程序（目標(biāo)），兩者在邏輯上是等價(jià)的。,如果源語言是高級(jí)語言，目標(biāo)語言是低級(jí)語言，則稱為,編譯程序,。,1.1,編譯的基本概念,先編譯，后執(zhí)行,解釋程序：邊轉(zhuǎn)換邊執(zhí)行，不生成目標(biāo)代碼,編譯程序,(Compiler),目標(biāo)程序,源程序,把高級(jí)語言程序翻譯成等價(jià)的低級(jí)語言 程序。,編譯程序,(Compiler),的功能,1.2,編譯過程和編譯程序的結(jié)構(gòu),編譯過程一般可分為五個(gè)階段：,一、詞法分析,二、語法分析,三、語義分析與中間代碼生成,四、優(yōu)化,五、目標(biāo)代碼生成,例如，有源程序段如下：,float,r,h,s,;,s=2*3.1416*r*(,h+r,);,一、詞法分析：識(shí)別出源程序中的一個(gè)個(gè)單詞符號(hào),float,r,h,s,;,s=2*3.1416*r*(,h+r,);,二、語法分析：把單詞符號(hào)串組合成各類語法單位,（即,s=2*3.1416*r*(,h+r,),）,識(shí)別,2*3.1416*r*(,h+r,),為表達(dá)式,識(shí)別,s=2*3.1416*r*(,h+r,),為賦值語句,詞法分析是線性分析，,語法分析是一種層次結(jié)構(gòu)分析,賦值語句經(jīng)語法分析生成語法分析樹,賦值語句經(jīng)語法分析生成語法分析樹,賦值語句,s=2*3.1416*r*(,h+r,),的語法樹,=,s,*,2,*,3.1416,r,*,r,h,+,表達(dá)式,賦值語句,表達(dá)式,表達(dá)式,表達(dá)式,三、語義分析與中間代碼生成：分析語法范疇的含義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）,中間代碼：一種含義明確、便于處理的記號(hào)系統(tǒng)，通常獨(dú)立于具體的硬件系統(tǒng)。與機(jī)器指令較接近，易于轉(zhuǎn)換成機(jī)器指令。,中間代碼可用四元式、三元式、間接三元式、逆波蘭式、樹形表示等,賦值語句經(jīng)語義分析生成語義樹,例賦值語句,s=2*3.1416*r*(,h+r,),經(jīng)語義分析生成語義樹如下,=,s,*,2,*,3.1416,r,*,r,h,+,生成中間代碼,t1,=2*3.1416;,t2,=t1*r,;,t3,=,h,+r;,t4,=,t2*t3,;,s=t4;,四、優(yōu)化：產(chǎn)生更高效的代碼,t2,=6.2832*r,;,t3,=,h,+r;,s,=,t2*t3,;,四、優(yōu)化：產(chǎn)生更高效的代碼,for (i=1;i=100;i+),M=J+10*i;,N=K+10*i;,M=J;N=K;,for (i=1;i=100;i+),M=M+10;,N=N+10;,M=J;t=K-J;,for (i=1;i=100;i+),M=M+10;,N=,t+M,；,五、生成目標(biāo)代碼：將中間代碼變換成特定機(jī)器上的低級(jí)語言代碼,mov,AX,6.28,;,mul,r,;,mov,t2,AX,;,mov,AX,h,;,add,AX,r ;,mov,t3,AX,;,mov,AX ,t2;,mul,t3,;,mov,s,AX,;,t2,=6.28*r,;,t3,=,h,+r;,s,=,t2*t3,;,編譯程序的邏輯結(jié)構(gòu),編譯程序總框,按編譯過程五階段的任務(wù)劃分模塊得出編譯程序總框如下圖：,詞法分析器,語法分析器,語義分析與中間代碼產(chǎn)生器,優(yōu)化器,目標(biāo)代碼生成器,表 格 管 理,出 錯(cuò) 處 理,源程序,單詞符號(hào),語法范疇,中間代碼,中間代碼,目標(biāo)代碼,源代碼識(shí)別階段,目標(biāo)代碼生成階段,編譯前端與編譯后端,把編譯程序劃分為編譯前端和編譯后端,前端,后端,源程序,中間代碼,目標(biāo)代碼,僅依賴源語言,僅依賴目標(biāo)語言,除了五個(gè)功能模塊，一個(gè)完整的編譯程序還包括：表格管理和出錯(cuò)處理。,表格與表格管理,表格，記錄源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。,符號(hào)表,：記錄名字及其屬性。,編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。,符號(hào)表,名字,種類,類型,層次,偏移量,r,變量,float,1,d,h,變量,float,1,d+4,s,變量,float,1,d+8,錯(cuò)誤的診查處理,編譯程序在各個(gè)階段應(yīng),診斷和報(bào)告源程序中的錯(cuò)誤，包括詞法錯(cuò)誤，語法錯(cuò)誤，語義錯(cuò)誤。,編譯程序應(yīng),報(bào)告出錯(cuò)地點(diǎn)，并給出簡明準(zhǔn)確的提示信息。,遍：,遍（,PASS),：,對(duì)輸入文件（源程序或其等價(jià)的中間形式）從頭到尾掃描一遍，并完成預(yù)定處理工作的過程。,將編譯程序組織成若干遍,遍,輸入文件,輸出文件,1.3,編譯程序的生成,用機(jī)器語言或匯編語言來構(gòu)造編譯程序；,用高級(jí)語言來構(gòu)造編譯程序,編譯程序,源程序,目標(biāo)程序,源語言,目標(biāo)語言,編譯方法,構(gòu)造一個(gè)編譯程序必須掌握：,編譯器實(shí)現(xiàn)語言,1.3,編譯程序的生成,編譯程序自動(dòng)生成工具：,LEX,、,YACC,；,自編,譯技術(shù),移植生成編譯器技術(shù),并行編譯技術(shù),思考題：,1,、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。,2,、,C,語言的編譯程序可以用,C,語言來編寫。,已有,要求,S,T,I,C,A,A,J,A,A,C,A,A,J,A,C,J,A,A,S,T,I,已有,要求,C,A,A,C,B,B,C,B,C,C,A,A,C,B,A,C,B,C,C,B,B,2,1,