編譯原理第1章概論

編譯原理任課教師：邵翀E_mail：教學(xué)計劃時間：2017~2018第學(xué)1期周學(xué)時：2周數(shù)：18（上機(jī)9課時）考核方式：考試教材：呂映之,《編譯原理》,清華大學(xué)參考書：《程序設(shè)計語言編譯原理》本課程前后繼課程高級程序設(shè)計語言匯編程序設(shè)計語言數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)編譯原理形式語言與自動機(jī)可計算性理論并行編譯自然語言理解課程簡介《編譯原理》是計算機(jī)類專業(yè)的一門主干專業(yè)課程。設(shè)置本課程的目的是系統(tǒng)向?qū)W生講述編譯程序一般構(gòu)造原理、基本設(shè)計方法和實現(xiàn)技術(shù)，學(xué)生通過本課程的學(xué)習(xí)，既掌握編譯理論和方法方面的基本知識，而且也具備設(shè)計、實現(xiàn)、分析和移植編譯程序的初步能力。特點：抽象;算法多難點：形式語言基本理論；自動機(jī)基本理論；語義分析；第一章概述編譯程序是計算機(jī)系統(tǒng)中重要的系統(tǒng)軟件，是高級語言的支撐基礎(chǔ)。學(xué)習(xí)目標(biāo)：編譯程序的概念編譯的各個階段編譯程序的結(jié)構(gòu)編譯程序生成方法編譯原理是編譯程序的構(gòu)造原理和技術(shù)。1.1

翻譯程序與編譯程序一、程序設(shè)計語言1.計算機(jī)語言的分類計算機(jī)語言低級語言高級語言：如PASCAL，C等機(jī)器語言匯編語言(1)把高級語言程序或匯編語言程序轉(zhuǎn)換成計算機(jī)所能理解的語言程序—機(jī)器語言程序。

完成轉(zhuǎn)換的程序叫翻譯程序。(2)運行所得的機(jī)器語言程序得到計算結(jié)果。2.高級語言或匯編語言的執(zhí)行步驟：1.1翻譯程序與編譯程序1.翻譯程序是這樣一種程序,它能夠把某一種語言程序(稱為源語言程序)轉(zhuǎn)換成另一種語言程序(稱為目標(biāo)語言程序),而后者與前者在邏輯上是等價的。二、翻譯程序源程序翻譯程序目標(biāo)程序1.1翻譯程序與編譯程序2.翻譯程序通常有兩種方式：編譯和解釋三.編譯方式和編譯程序1.1翻譯程序與編譯程序1.編譯方式

編譯方式是一種分階段進(jìn)行的方式。一般來說，首先進(jìn)行“翻譯”，把用高級語言或匯編語言程序翻譯成與之等價的機(jī)器語言程序，然后對翻譯出來的程序進(jìn)行運行計算。前一階段翻譯工作由翻譯程序完成，后一階段的運行計算需要由運行程序來配合完成。所謂運行程序是指運行目標(biāo)程序時必須配置的各種子程序全體，通常以庫子程序的形式存在，如連接裝配程序及連接庫等。1.1翻譯程序與編譯程序2.編譯程序（1）將用高級語言（如FORTRAN,PASCAL或C）書寫的程序翻譯成等價的某特定計算機(jī)系統(tǒng)的低級語言程序（匯編語言或機(jī)器語言），這種翻譯程序稱為編譯程序。高級語言程序編譯程序低級語言程序（2）如果將匯編語言書寫的程序翻譯成某特定計算機(jī)系統(tǒng)的機(jī)器語言程序，這種翻譯程序稱為匯編程序。1.解釋方式在解釋方式下，源程序的執(zhí)行只有一個階段——解釋執(zhí)行階段。具體地說，完成解釋工作的解釋程序?qū)丛闯绦蛑姓Z句的動態(tài)順序逐句地進(jìn)行分析解釋，并立即予以執(zhí)行。與編譯方式的主要區(qū)別:不產(chǎn)生目標(biāo)程序。而是直接執(zhí)行源程序本身。四、解釋方式及解釋程序1.1翻譯程序與編譯程序2解釋程序是這樣一個程序,它以某一語言寫的源程序作為輸入,但不產(chǎn)生目標(biāo)程序,而是邊解釋邊執(zhí)行源程序本身。源程序運行結(jié)果解釋程序邊翻譯邊執(zhí)行1.1翻譯程序與編譯程序編譯程序vs.解釋程序編譯解釋編譯過程是一種語言的翻譯過程，類似于外文的翻譯過程。例如：一段英文翻譯為中文時，通常經(jīng)過以下步驟：

識別句子中的一個個單詞；分析句子的語法結(jié)構(gòu)；分析句子的含義；進(jìn)行初步翻譯；對譯文進(jìn)行修飾；寫出最后的譯文。詞法分析語法分析語義分析中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成1.2編譯程序組成及邏輯結(jié)構(gòu)1.2編譯程序組成及邏輯結(jié)構(gòu)編譯程序的一般需完成五個方面任務(wù):詞法分析詞法分析程序語法分析語法分析程序語義及中間代碼產(chǎn)生語義分析（和中間代碼生成）程序中間代碼優(yōu)化中間代碼優(yōu)化程序目標(biāo)代碼產(chǎn)生目標(biāo)代碼生成程序一、編譯程序組成1、詞法分析（1）任務(wù):輸入源程序,對構(gòu)成源程序的字符串(從左到右)進(jìn)行掃描和分解,根據(jù)語言的詞法規(guī)則識別出一個個的最小語法單位(也稱為單詞符號或語法符號)。刪除無用的空白字符及其他與輸入介質(zhì)相關(guān)的非實質(zhì)性字符（空格、回車等）刪除注釋。進(jìn)行詞法檢查,報告所發(fā)現(xiàn)的錯誤。1.2編譯程序組成及邏輯結(jié)構(gòu)例：計算圓柱體表面積

floatr,h,s;S=2*3.1416*r*(h+r);保留字:float標(biāo)識符:r,h,s運算符:*，+常數(shù)：2,3,1416界符:();,=1.2編譯程序組成及邏輯結(jié)構(gòu)2、語法分析任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號重構(gòu)成各類語法范疇(語法單位)。分析時如發(fā)現(xiàn)有不符合語法規(guī)則的地方，語法分析程序便把這些出錯的地方及出錯性質(zhì)打印輸出；如無語法錯誤，則以另一種內(nèi)部表示給出正確的語法結(jié)構(gòu)。如“表達(dá)式”、“語句”、“程序段”和“程序”等2*3.1416*r*(h+r)S=2*3.1416*r*(h+r);1.2編譯程序組成及邏輯結(jié)構(gòu)3、語義分析（1）任務(wù)依據(jù)語言的語義規(guī)則對語法分析程序所識別出的各類語法成分進(jìn)行靜態(tài)語義檢查，以保證源程序在語義上的正確性，并用另一種語言形式表示出來，或直接用目標(biāo)語言表示出來。（2）語義的分類

靜態(tài)語義：指在編譯階段能檢查出的語義。如確定類型、類型和運算符合法性檢查、識別語法成分含義與相應(yīng)的語義處理、及其他一些靜態(tài)語義檢查。動態(tài)語義：則指只有在目標(biāo)碼的運行階段才能檢查出的語義。1.2編譯程序組成及邏輯結(jié)構(gòu)4、中間代碼生成（1）任務(wù)：按語言的語義規(guī)則把各類語法范疇翻譯成中間語言代碼。（2）中間代碼的定義：所謂“中間代碼”是一種含義明確、便于處理的記號系統(tǒng),是位于源代碼和目標(biāo)代碼之間的代碼形式,它獨立于具體的硬件。這種記號系統(tǒng)比較容易變換成現(xiàn)代計算機(jī)的機(jī)器指令。（3）中間代碼的形式四元式,三元式,間接三元式,逆波蘭式等。1.2編譯程序組成及邏輯結(jié)構(gòu)例：四元式的格式為:(算符,左操作數(shù),右操作數(shù),結(jié)果)（1）（*，2，3.1416，T1）（2）（*，T1，r，T2）（3）（+，h，r，T3）（4）（*，T2，T3，T4）（5）（=，T4，-，S）T1、T2、T3、T4是編譯期間引進(jìn)的臨時工作變量賦值語句：S=2*3.1416*r*(h+r);語義分析時，首先檢查賦值號左右兩邊表達(dá)式的類型是否匹配,然后再根據(jù)賦值語句的語義對它進(jìn)行翻譯。語義：2*3.1416

T1語義：T1*r

T2語義：h+r

T3語義：T2*T3

T4語義：T4

S1.2編譯程序組成及邏輯結(jié)構(gòu)5、代碼優(yōu)化(1)任務(wù):對前段產(chǎn)生的中間代碼進(jìn)行加工變換,以期在最后階段能產(chǎn)生更為高效(省時間和空間)目標(biāo)代碼。(2)分類：優(yōu)化分為局部優(yōu)化和全局優(yōu)化。(3)優(yōu)化所遵循的原則：程序的等價變換規(guī)則的原則。（1）（*，2，3.1416，T1）（2）（*，T1，r，T2）（3）（+，h，r，T3）（4）（*，T2，T3，T4）（5）（=，T4，_，S）（*，6.28，r，T2）1.2編譯程序組成及邏輯結(jié)構(gòu)6、目標(biāo)代碼生成(1)任務(wù)：把中間代碼（或經(jīng)過優(yōu)化處理之后）變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。例如:(*,count,10.0,T1) (+,first,T1,sum)

生成匯編代碼如下: MOVFcount,R2 MULF#10.0,R2 MOVFfirst,R1 ADDFR1,R2 MOVR1,sum1.2編譯程序組成及邏輯結(jié)構(gòu)絕對地址的機(jī)器指令代碼：這種代碼可以立即執(zhí)行。匯編語言形式的目標(biāo)程序：這種代碼還需要匯編程序匯編之后才能運行。模塊結(jié)構(gòu)的機(jī)器指令(可重定位的指令代碼)

這種代碼在運行前必須借助于一個連接裝配程序把各個目標(biāo)模塊連接在一起，裝入內(nèi)存中，使之成為一個可以運行的絕對地址的機(jī)器指令代碼程序。(2)目標(biāo)代碼的形式1.2編譯程序組成及邏輯結(jié)構(gòu)1.所謂趟或遍是指一個編譯程序在編譯時刻把源程序或源程序的等價物(中間程序)從頭到尾掃描一遍并完成規(guī)定加工處理工作的過程。2.根據(jù)編譯程序在完成翻譯任務(wù)的過程中需要對源程序或其中間等價物掃描的遍數(shù)，可以把編譯程序分為單遍掃描的編譯程序(只需掃描一遍)和多遍掃描的編譯程序(需掃描多遍)。1.2編譯程序組成及邏輯結(jié)構(gòu)二、編譯程序邏輯結(jié)構(gòu)詞法分析程序語法分析程序語義分析程序中間代碼生成代碼優(yōu)化程序目標(biāo)代碼生成信息表管理程序錯誤檢查程序源程序

單詞符號中間代碼中間代碼中間代碼語法單位目標(biāo)代碼3.典型的編譯程序結(jié)構(gòu)1.2編譯程序組成及邏輯結(jié)構(gòu)出錯處理：編譯過程中，發(fā)現(xiàn)源程序有錯誤（詞法錯誤、語法錯誤、語義錯誤），編譯程序應(yīng)報告錯誤的性質(zhì)和出錯的地點，并將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分繼續(xù)被編譯下去。這些工作稱為出錯處理(errorhandling)。表格管理：編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理工作。1.2編譯程序組成及邏輯結(jié)構(gòu)1.3編譯程序的生成方法1.源語言和目標(biāo)語言2.編譯方法3.選擇語言編制程序4.調(diào)試編譯程序5.提交相關(guān)文檔一、構(gòu)造一個編譯程序必須掌握的內(nèi)容1.合理的方法是用另一種已存在編譯器的語言來編寫編譯器。用語言B編譯語言A的編譯器語言A正運行的編譯器語言B已存在的編譯器2.編譯程序生成工具二、編譯程序生成方法1.3編譯程序的生成方法(1)LEX:自動產(chǎn)生詞法分析器詞法規(guī)則說明LEX詞法分析程序(C/C++程序)輸入：詞法（正規(guī)表達(dá)式）識別動作（Ｃ/C++程序段）輸出：

yylex()函數(shù)1.3編譯程序的生成方法語法規(guī)則說明YACC語法分析程序

輸入： 語法規(guī)則（產(chǎn)生式） 語義動作(Ｃ/C++程序段)輸出：

yyparse()函數(shù)(2)YACC:自動產(chǎn)生語法分析器1.3編譯程序