編譯原理課件(龍書為教材)

編譯原理2/5/20231自我介紹姓名：辛明影電話： 86413213教研室：計算機軟件基礎(chǔ)辦公室：綜合樓513

xmy63@xmy63@126.com助課教師：洪曉鵬，綜合樓614單麗麗，新技術(shù)樓6082/5/20232辛明影開課目的及應(yīng)用前景：

介紹設(shè)計與構(gòu)造程序設(shè)計語言編譯程序的原理與方法源程序編譯程序目標程序連接可執(zhí)行程序預(yù)備知識：形式語言與自動機、兩門以上的高級程序設(shè)計語言匯編語言數(shù)據(jù)結(jié)構(gòu)等How?2/5/20233辛明影內(nèi)容簡介：第一章：編譯器的基本結(jié)構(gòu)第二章：高級語言及其語法描述第三章：詞法分析器第四章：語法分析技術(shù)第五章：語法制導(dǎo)翻譯的主要概念及中間代碼第六章：程序運行時的存貯分配問題第七章：代碼優(yōu)化第八章：目標代碼生成2/5/20234辛明影教學(xué)設(shè)計：(1)自頂向下，逐步求精的方法(2)問題驅(qū)動(3)將課程設(shè)計成一個應(yīng)用平臺(4)用實驗拓廣課堂教學(xué)(5)精講多練(6)承前啟后教學(xué)目標：2/5/20235辛明影第一章緒論編譯器就是一個程序，它讀入用某種語言編寫的源程序，并翻譯成一個與之等價的另一種語言編寫的源程序。編譯器源程序目標程序錯誤信息Fortran、Pascal、Java、C…..另一種程序設(shè)計語言、匯編語言、機器語言1.1什么叫編譯程序2/5/20236辛明影1.2編譯過程概述編譯程序的工作，從輸入源程序開始，到輸出目標程序結(jié)束，與自然語言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經(jīng)下列步驟：識別出句子中的單詞分析句子的語法結(jié)構(gòu)根據(jù)句子的含義進行初步分析對譯文進行修飾寫出最后的譯文編譯程序詞法分析代碼優(yōu)化語法分析語義分析及中間代碼生成目標代碼生成構(gòu)成編譯程序各個階段Iamaexperiencedteacher.2/5/20237辛明影編譯器的各個階段：編譯器是分階段執(zhí)行的。每個階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個階段2/5/20238辛明影各分析階段隨著編譯器各個階段的進展，源程序的內(nèi)部表示不斷地發(fā)生變化。以a=b+c*d為例1。詞法分析讀入源程序完成的任務(wù)：識別出單詞：a、=、b、+、c、*、d并用記號方式表示識別出的單詞關(guān)鍵字、標識符、常數(shù)、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*記號表示邏輯上相關(guān)的字符序列，常用整數(shù)來表示上述單詞表示為：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)2/5/20239辛明影語法分析在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串組成各類語法單位.具體的說，語法分析是在單詞流的基礎(chǔ)上建立一個層次結(jié)構(gòu)-----建立語法樹賦值語句標識符=表達式a表達式標識符b+表達式表達式*標識符c表達式標識符d2/5/202310辛明影語義分析階段語義分析利用語法分析階段確定的層次結(jié)構(gòu)來識別表達式和語句中的操作信息及類型信息=+ab*cdtemp1=c*dtemp2=b+temp1temp1temp2a=temp22/5/202311辛明影中間代碼生成階段本階段將產(chǎn)生源程序的一個顯式中間表示這種中間表示可以看成是某種抽象的程序，通常是與平臺無關(guān)的其重要性質(zhì)：1.易于產(chǎn)生2.易于翻譯成目標程序下面是用三地址碼和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)2/5/202312辛明影代碼優(yōu)化階段試圖改進中間代碼，以產(chǎn)生執(zhí)行速度較快的機器代碼對上面中間代碼進行優(yōu)化處理后，產(chǎn)生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp22/5/202313辛明影代碼生成階段生成可重定位的機器代碼或匯編代碼MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R22/5/202314辛明影1.3符號表管理inta,b;floate,fcharch1,ch2;為什么要先說明?

定義了變量的類型，也就規(guī)定了變量在內(nèi)存中的存放形式，在其上所能進行的運算解決符號地址到存貯地址上的映射2/5/202315辛明影

編譯器的一個基本功能是記錄源程序中使用的標識符并將它們記載到符號表中。符號表是一個數(shù)據(jù)結(jié)構(gòu)。每個標識符在符號表中都有一條記錄名字記號類型種屬……addrid1(25)id2(25)ba例：inta,b;int簡變04

并收集與每個標識符相關(guān)的各種屬性信息，int簡變2/5/202316辛明影符號表的接口：符號表的作用就是存放字符串或詞素當(dāng)一個字符串或詞素被保存時，與之相對應(yīng)的記號也被保存符號表上的操作：Insert(s,t):將符號串s和記號t插入符號表，返回相應(yīng)表項的指針Lookup(s):在符號表中查找字符串s，查找成功返回相應(yīng)指針，否則返回02/5/202317辛明影關(guān)鍵字的處理通常情況下，將關(guān)鍵字存在符號表中，作為符號表的初值。當(dāng)詞法分析程序識別出一個標識符s后，用lookup(s)查找符號表，如果是關(guān)鍵字，返回相應(yīng)的記號；如果是變量名，返回記號id2/5/202318辛明影符號表的實現(xiàn)固定長標識符：采用前面的結(jié)構(gòu)不定長標識符：使用單獨的數(shù)組lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放標識符的字符串,符號表中存放標識符在lexemes的起始位置和相應(yīng)記號2/5/202319辛明影1.4編譯各階段的分組一、前端和后端前端包括詞法分析、詞法分析、語義分析，以及相關(guān)的錯誤處理和符號表的建立前端依賴于源程序并在很大程度上獨立于目標機器。2/5/202320辛明影后端主要包括代碼優(yōu)化、代碼生成和相關(guān)錯誤處理。后端依賴于目標機器。后端處理對象是由前端產(chǎn)生的結(jié)果，即中間代碼前端生成與平臺無關(guān)的字節(jié)碼后端是由與平臺有關(guān)的解釋器對所生成的字節(jié)碼文件進行解釋執(zhí)行Java語言的編譯采用的是前端后端方式。2/5/202321辛明影二、編譯的遍編譯的若干階段通常是以一遍來實現(xiàn)的，每遍讀一次輸入文件、產(chǎn)生一個輸出文件。2/5/202322辛明影在編譯的各個階段都會發(fā)現(xiàn)源程序中的錯誤，1.5錯誤檢測與報告為了使編譯器能繼續(xù)運行，以檢測出源程序中更多的錯誤，在檢測到錯誤后，必須以合適的方式進行錯誤處理。error2/5/202323辛明影第二章高級語言

及其語法描述2/5/202324內(nèi)容簡介：本章概述程序設(shè)計語言的結(jié)構(gòu)2.1程序語言的定義任何語言實現(xiàn)的基礎(chǔ)是語言定義。語言的定義決定了該語言

具有什么樣的語言功能、

什么樣的數(shù)據(jù)結(jié)構(gòu)、

什么樣的程序結(jié)構(gòu)、

以及具體的使用形式等細節(jié)問題。和主要的共同特征，并介紹程序設(shè)計語言主要語句的文法描述與形式定義。2/5/202325辛明影

對于編譯程序設(shè)計者來說：語言定義就是具體實現(xiàn)的理論依據(jù)。

對于語言用戶來說：語言定義就是一本用戶手冊。2.1.1語法語言的語法是指這樣一組規(guī)則，用它可產(chǎn)生一個程序。規(guī)則：詞法規(guī)則語法規(guī)則2/5/202326辛明影詞法規(guī)則是指單詞符號的形成規(guī)則字母表就是一個有窮字符集。C語言的字母表為：∑={a---z、A—Z、0—9、(、)、

[、]、

、.、!、~、+、-、*、/、&、%、<、>、=、^、|、?、,、;}C語言的標識符的構(gòu)成規(guī)則：

字母、下劃線打頭的字母、數(shù)字和下劃線構(gòu)成的符號串。如：a1、ave、_day一.詞法規(guī)則2/5/202327辛明影上述的定義是用文字來描述的，當(dāng)設(shè)計編譯程序時，就要把它用形式的方式描述出來，就要用到形式語言。各類型的常數(shù)、標識符、基本字、算符和界符等正規(guī)式和有窮自動機是描述詞法結(jié)構(gòu)和進行詞法分析的有效工具在現(xiàn)今多數(shù)程序設(shè)計語言中，單詞符號一般包括：2/5/202328辛明影C語言的標識符的文法和自動機描述：例：C語言標識符的文法描述L（G）={w/w為字母或‘-’打頭的字母數(shù)字串}解：P:I→aBI→-BI→aB→aBB→dBB→aB→d識別L（G）的自動機IBTa-a,d其它2/5/202329辛明影SACDFEB7dddddddee+–T*例：C語言實常數(shù)的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e242/5/202330辛明影二.語法規(guī)則語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則一般的程序設(shè)計語言的語法單位有：表達式、語句、分程序、函數(shù)、過程和程序等

下推自動機理論和上下文無關(guān)文法是我們討論語法分析的理論基礎(chǔ)2/5/202331辛明影表達式：E→E+TE→E-TE→TT→T*FT→T/F

T→FF→(E)F→id主要語句的形式描述：2/5/202332辛明影布爾表達式：B→BorBB→BandBB→notBB→(E）B→idrelopidB→trueB→false2/5/202333辛明影賦值、分支、循環(huán)語句：S→id=ES

→ifBthenS

S→ifBthenSelseS

S→whileBdoSS→{L}

L→L;SL→S2/5/202334辛明影調(diào)用語句：S→callid(Elist)Elist→Elist,EElist→E|ε2/5/202335辛明影類型說明和過程說明語句：P→DD→D;DD→id:TD→id（Elist）D;ST→intT→float2/5/202336辛明影數(shù)組說明語句：L→id[Elist]Elist→Elist,EElist→E2/5/202337辛明影2.1.2

語義例：a=b+c*d例do999I=1,10

對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義，這就是語義問題對于編譯程序來說，只有了解程序的語義，才知道應(yīng)把它翻譯成什么樣的目標指令代碼2/5/202338辛明影2.2構(gòu)造基礎(chǔ)2.2.1程序結(jié)構(gòu)簡介一個高級語言程序通常由若干子程序段（過程、函數(shù)等）組成，許多語言還引入了類、程序包等更高級的結(jié)構(gòu)2/5/202339辛明影FORTRAN一個FORTRAN程序由一個主程序和若干個輔助程序段組成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定義是并列的2/5/202340辛明影FORTRAN的構(gòu)成特點：同一名字在不同的程序段中一般都代表不同的對象，也就是說代表不同的存貯單元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.

ENDSUBROUTINESUB1

.END一個名字對應(yīng)多個對象2/5/202341辛明影但是不同程序段里的同名公用塊卻代表同一個存貯區(qū)域PROGRAMMAIN.

Commona,bENDSUBROUTINESUB1

commonx,y.ENDPROGRAMMAIN.

ENDSUBROUTINESUB1

.ENDCommona,babA=100B=5010050Commonx,yxyY=x+100200共享存貯單元多個名字對應(yīng)一個對象2/5/202342辛明影二。PascalPascal允許子程序嵌套定義

Programmain說明部分Begin可執(zhí)行部分endPascal的程序結(jié)構(gòu)Programmain

BeginendProcedureP1BeginendProcedureP11BeginendProcedureP2Beginend也允許并列定義2/5/202343辛明影關(guān)于名字的作用域的規(guī)定：標識符X的任意一次出現(xiàn)（除去說明語句中）都意味著對某個說明語句中說明的這個變量X的引用此時，說明語句同標識符X應(yīng)共處一個最小程序中，即：P1中說明的X只在P1中有效P11是P1的內(nèi)層子程序，P11中沒有再對X作新的說明，則在P11中對X的引用，實際上引用的就是P1中說明的X，

即內(nèi)部過程可以引用外部過程中定義的量2/5/202344辛明影三.javaJava語言是一種面向?qū)ο蟮母呒壵Z言，它很重要的方面是類和繼承的概念，同時支持多態(tài)性和動態(tài)綁定等特性Classcar{Intcolor_num;Intdoor_num;Intspeed;.Voidpush_break(){}

Voidadd_oil(){}}Classbenzextendscar

Doubleprice;VoidABS(){}

}2/5/202345辛明影

一個類把有關(guān)的數(shù)據(jù)及其操作封裝在一起構(gòu)成一個抽象數(shù)據(jù)類型一個子類繼承其父類的所有數(shù)據(jù)和方法，并且可以加入自己新的定義

在java中，變量和方法的定義之前可以加上public、private、pretected等修飾詞，以限制其它類的對象對于這些變量和方法的使用2/5/202346辛明影2.2.2構(gòu)造基礎(chǔ)程序設(shè)計語言的數(shù)據(jù)對象：數(shù)據(jù)、函數(shù)、過程常用能反映其本質(zhì)的、有助于記憶的名字來表示一.名字特性：一個名字對應(yīng)一個對象，普通變量多個名字對應(yīng)一個對象一個名字對應(yīng)多個對象，common,數(shù)組、重載、局部變量、重寫、2/5/202347辛明影

每個對象可以看做是一個存貯單元，可能是一個字，也可能是多個字名字具有屬性，通常由說明語句給出一個名字的屬性，包括：類型和作用域類型決定了它有什么樣的值，作用域規(guī)定了值的存在范圍

值在計算機內(nèi)的表示，

以及對它能施加什么樣的運算2/5/202348辛明影二.數(shù)據(jù)類型1.初等數(shù)據(jù)類型①數(shù)值數(shù)據(jù)：整形、實型、雙精度等，可施行算術(shù)運算②邏輯數(shù)據(jù)：可施行邏輯運算③字符數(shù)據(jù)：④指針類型：2/5/202349辛明影三。數(shù)據(jù)結(jié)構(gòu)1。數(shù)組從邏輯上講，一個數(shù)組是由同類型數(shù)據(jù)所組成的n維矩形結(jié)構(gòu)一個數(shù)組所需的存貯空間大小在編譯時就已知道的，則稱此數(shù)組是一個確定的數(shù)組；否則稱為可變數(shù)組設(shè)intA[l1‥u1,][l2‥u2]……[ln‥un]為n維數(shù)組各維的長度：di=ui-li+1(1≤i≤n)2/5/202350辛明影任一數(shù)組元素A[i1,i2,……in]的地址為：D=a+(i1-l1)d2d3……

dn

+(i2-l2)d2d2……

dn……+(in-1-ln-1)dn+(in-ln)

整理后C=(……

(l1d2+l2)d3+l3)d4+……

+ln-1)dn+lnC是數(shù)組計算中不變的部分2/5/202351辛明影變量部分：v=(……

(i1d2+i2)d3+i3)d4+……

+in-1)dn+in任一數(shù)組元素A[i1,i2,……in]的地址:addr=a-c+v2/5/202352辛明影在編譯時，當(dāng)遇到說明時，必須把數(shù)組的有關(guān)信息記錄在一個“內(nèi)情向量”之中，用于數(shù)組元素的地址計算。數(shù)組的內(nèi)情向量包括：維數(shù)，各維的上、下限，首地址及數(shù)組的類型……lnundn…………l2l1unund1d2N維數(shù)C常數(shù)T類型A首地址2/5/202353辛明影對于確定數(shù)組來說，內(nèi)情向量可登記在符號表中；

對于可變數(shù)組，內(nèi)情向量的信息在編譯時無法全部知道，只有到運行階段才能全部確定下來，存貯分配也要等到運行時方能進行2/5/202354辛明影2.記錄（結(jié)構(gòu)）從邏輯上講，記錄是由已知的數(shù)據(jù)組合起來的一種結(jié)構(gòu)Structstudent{charname[20];booleanpartmember;intage;}stu;2/5/202355辛明影記錄結(jié)構(gòu)最簡單的存貯方式是連續(xù)存放上述的變量stu共占7個字，共28個字節(jié)SStu.partmemberStu.age3.字符串、表格和隊列kK+1….K+20….K+24….….……….2/5/202356辛明影四.抽象數(shù)據(jù)類型一個抽象數(shù)據(jù)類型包括：⑶這種類型對象的封裝⑵作用于這些數(shù)據(jù)對象的抽象運算的集合⑴數(shù)據(jù)對象的一個集合C++、Java語言通過類對抽象類型提供支持2/5/202357辛明影五.語句與控制結(jié)構(gòu)1.表達式要解決的問題：①優(yōu)先級②結(jié)合率2.語句語句可分為：①說明語句：②可執(zhí)行語句：定義各種不同數(shù)據(jù)類型的變量和運算描述語句的動作執(zhí)行語句分為：賦值、控制和I/O語句2/5/202358辛明影⑴賦值句A=B左值右值名字的左值指它所代表的存貯單元地址名字的右值指該單元的內(nèi)容2/5/202359辛明影⑵控制語句無條件轉(zhuǎn)移語句：Gotolable條件語句：IfBthenSIfBthenSelseS循環(huán)語句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3過程調(diào)用語句：CallP(x1,x2,….xn)返回語句：Return(E)2/5/202360辛明影⑶說明語句說明語句用于定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否一致。許多說明語句不產(chǎn)生目標代碼但有的說明語句，如過程說明和可變數(shù)組說明，則要產(chǎn)生相應(yīng)的目標代碼2/5/202361辛明影⑷簡單句和復(fù)合句簡單句是指不包含其它語句成分的基本句。賦值、goto語句等復(fù)合句則指那些句中有句的語句If(x==0)thenx=1{x=1;y=2;gotol1;}2/5/202362辛明影programreference（input，output）；

vara，b：integer；

procedureswap（x，y：integer）；

vartemp：integer；

begintemp:＝x；

x：＝y(tǒng)；

y：＝temp

end;

begin

a：＝1;b：＝2;

swap(a，b);

writeln('a='，a，

'b=',b）

end.2.2.3參數(shù)傳遞

結(jié)果是什么？2/5/202363辛明影1傳值調(diào)用實在參數(shù)和形式參數(shù)結(jié)合的方法：傳值調(diào)用（call-by-value）引用調(diào)用（call-by-reference）復(fù)制恢復(fù)（copy-restore）傳名調(diào)用（call-by-name）2/5/202364辛明影

子程序為每一個形參開辟一個存貯單元，用于存放相應(yīng)實參的值。子程序執(zhí)行時，每當(dāng)訪問形參時，就直接訪問形參單元。實參：形參：傳值調(diào)用可以實現(xiàn)如下：主調(diào)過程計算實在參數(shù)，并把它們的右-值放入到形式參數(shù)的存儲空間中。2/5/202365辛明影使用傳值的方法，調(diào)用swap（a,b）等價于下面幾步：

x：=a

y：=b

temp：=x

x：=y

y：=temp2/5/202366辛明影2引用調(diào)用（傳地址）

把實在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù),

在目標代碼中，在被調(diào)用過程中對形式參數(shù)的一次引用就成為對傳遞給被調(diào)用過程的指針的一個間接引用。Referenceabxy12swapabtemp2/5/202367辛明影子程序為每個形參開辟一個單元，用于存放相應(yīng)實參的地址，執(zhí)行時，子程序間址方式訪問這些形參單元

當(dāng)實參為表達式或常數(shù)時，則存放它們值的臨時單元。實參：地址形參：@Temp:=x;

x:=y;y:=temp;temp:=a;a:=b;b:=temp;2/5/202368辛明影3復(fù)制恢復(fù)（傳值結(jié)果）實現(xiàn)：

1.當(dāng)控制流入到被調(diào)用過程之前，把實在參數(shù)的右-值和左-值傳遞到被調(diào)用過程中；2.當(dāng)控制返回時，把形式參數(shù)的現(xiàn)行右-值復(fù)制回到相應(yīng)的實在參數(shù)的左-值中。2/5/202369辛明影

子程序為每個形參分配兩個存貯單元B1和B2，B1用于存放實參地址，B2用于存放實參值。

執(zhí)行時，對B2單元使用直接訪問形式；返回前，按B1中的地址把B2中的內(nèi)容存入主調(diào)程序的實參單元中。實參：地址形參：B1B2@B12/5/202370辛明影

在主調(diào)程序中設(shè)置計算實參地址和右值的形實替換子程序THUNK

子程序中為相應(yīng)實參開辟一個形式單元，用于存放該實參的THUNK子程序的入口地址。

執(zhí)行時，每當(dāng)要對形參進行訪問時，就調(diào)用THUNK子程序，以獲得相應(yīng)實參地址或值4傳名調(diào)用對形參的訪問是發(fā)生在實參單元上的2/5/202371辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end2/5/202372辛明影傳值：abc實參形參xyz234P(a,b,c);234y=y+1;

輸出：23446Z=z+x;A=2B=3C=42/5/202373辛明影傳地址：abc實參形參xyz234P(a,b,c);&a&b&cy=y+1;@y=@y+1輸出：24646Z=z+x;@z=@z+@x2/5/202374辛明影傳值結(jié)果：abc實參形參X—B1B2Y—B1B2Z—B1B2234&a&by=y+1;

輸出：246Z=z+x;&c

按@B1返回B2的值4

6

2344

62/5/202375辛明影傳名：abc實參形參xyz234P(a,b,c);&thunk&thunk&thunky=y+1;JSRThunkY→b輸出：24646Z=z+x;jsrThunkZ→c,x→a2/5/202376辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;P(a+b,a,a);printaend2/5/202377辛明影傳值：aba+b實參形參xyz23P(a+b,a,a);522y=y+1;

輸出：2

37Z=z+x;A=2B=352/5/202378辛明影傳地址：aba+b實參形參xyz235P(a+b,a,a);&a+b&a&ay=y+1;@y=@y+1輸出：83Z=z+x;@z=@z+@x82/5/202379辛明影傳名：ab實參形參xyz23P(a+b,a,a);&thunk&thunk&thunky=y+1;JSRThunkY→a輸出：939Z=z+x;jsrThunkZ→a,x→a+b2/5/202380辛明影第三章詞法分析2/5/202381編譯器的各個階段：編譯器是分階段執(zhí)行的。每個階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個階段2/5/202382辛明影3.2詞法分析器的手工構(gòu)造：用DFA能識別3.3詞法分析程序自動構(gòu)造工具LEX簡介3.1詞法分析程序的設(shè)計：

2/5/202383辛明影=80;0134256eniL字母字母字母字母數(shù)字數(shù)字數(shù)字==；；0124563Line=80;id(25),‘Line’=(36),num(27),‘80’;(45),數(shù)字字母字母11==0003;;1輸入輸出有窮控制器單詞的詞類和屬性（詞類符號，單詞的屬性）2/5/202384辛明影

3.1詞法分析程序的設(shè)計二、掃描器的任務(wù)

一、詞法分析程序的功能

源程序

單詞序列

詞法分析器1、組織源程序的輸入2、識別單詞，轉(zhuǎn)換成機內(nèi)表示形式3、刪除注釋行、空格及無用符號4、查填符號表5、檢查詞法錯誤2/5/202385辛明影<12,><25,符號表入口><39,><25,符號表入口><20,><25,符號表入口><36,><26,常數(shù)表入口><8,><25,符號表入口><36,><26,常數(shù)表入口>ifi＞jtheni:＝0

elsej:=1詞法分析if

I＞JThenI＝0

elsej=12/5/202386辛明影三、詞類和屬性2．標識符：用來表示各種名字3．字面常數(shù)：256，3.14，true,‘a(chǎn)bc’4．運算符：如，＋、－、*、/等等5．分界符：如逗號，分號，冒號等程序語言單詞的分類：

1．關(guān)鍵字(保留字或基本字)：while,if2/5/202387辛明影界符和運算符:詞法分析器的輸出：（詞類編碼，單詞自身的屬性值）關(guān)鍵字可分成一類，也可以一個關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型（整型、實型、布爾型等），每個類型的常數(shù)劃分成一類。所有的標識符分為一類。詞類編碼原則:一字一碼。一類型一碼。一類一碼。一符一碼。2/5/202388辛明影

表3.1單詞詞類編碼2/5/202389辛明影對于關(guān)鍵字、界符、運算符來說，它們的詞類編碼就可以表示其完整的信息，而對于標識符，詞類編碼所反映的信息不夠充分，標識符的具體特性還要通過單詞自身的屬性進行互相區(qū)分。標識符的單詞自身的屬性常用其在符號表中的入口指針來表示故對于這類單詞，其單詞自身的屬性值通常為空2/5/202390辛明影對于常數(shù)，其單詞自身的屬性常用其在常數(shù)表中的入口指針來表示2/5/202391辛明影

以語句子a=b+c*d為例，假設(shè)按表3.1為單詞編碼，詞法分析后的結(jié)果為：Token字符號表a=b+c*da25<25,><36,--------><25,><32,--------><25,>b25<25,>c25

d25<31,-------->

2/5/202392辛明影

四、詞法分析的設(shè)計形式（1）設(shè)計成一個獨立程序，完成詞法分析的任務(wù)，結(jié)果以文件的形式組織，做為語法分析的輸入源程序詞法分析符號表TOKEN字錯誤信息2/5/202393辛明影詞法分析語法分析語義分析和中間代碼生成源程序中間代碼

符號表管理

錯誤的診查處理（2）作為語法分析和語義分析的子程序2/5/202394辛明影

五、詞法分析程序的設(shè)計框圖SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP2/5/202395辛明影32詞法分析器的手工構(gòu)造為了構(gòu)造詞法分析器，要研究構(gòu)詞法，每種詞類的結(jié)構(gòu)模式以及識別它的數(shù)學(xué)模型——有窮自動機。321確定的有限自動機（DFA）322構(gòu)造識別單詞的DFA323編寫詞法分析程序2/5/202396辛明影SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP2/5/202397辛明影一、手工構(gòu)造識別單詞的DFAm根椐DFA識別單詞的定義，在研究給定程序語言單詞結(jié)構(gòu)的基礎(chǔ)上，能直接構(gòu)造出識別它的DFAm。例如：對于C語言整數(shù)：非空數(shù)字串。無符號實數(shù)（用d表示數(shù)字）:(a)dd.ddE(+-)ddddE(+-)dd(c)dd.dd0.1e+1412e-43.141592(d)dd…dd10002/5/202398辛明影IBTTa-a,d其它例：C語言的標識符標識符：字母開始的字母數(shù)字串。2/5/202399辛明影例：C語言實常數(shù)的文法描述01234567dddEdEd-+dd10003.141512e-40.1e+14.2/5/2023100辛明影在識別標識符的過程中，首先要拼寫出來，并和保留字區(qū)別開來；識別出的標識符要填入符號表中二、編寫詞法分析程序根據(jù)畫出的狀態(tài)轉(zhuǎn)換圖（識別單詞的）構(gòu)造詞法分析程序，每個狀態(tài)對應(yīng)一段程序，完成到達此狀態(tài)的工作；在識別常數(shù)的過程中，要把它轉(zhuǎn)換成機器表示以作為屬性值，記錄到常數(shù)表中。

詞法分析程序的控制程序模擬狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換。2/5/2023101辛明影programSCANNER;Begininitiate符號表,字符串表,行,列計數(shù)器;Open源文件,TOKEN文件,打印機文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符號表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;模塊0：掃描器主控2/5/2023102辛明影單詞分類模塊(SORT)輸入：CH內(nèi)含單詞首符；procedureSORT(CH);{caseCHof‘字母’:‘字母’:callRECOGID(CH,TOKEN);‘/’:callHANDLECOM(CH,TOKEN);‘?dāng)?shù)字’:callRECOGDIG(CH,TOKEN);‘’‘callRECOGSTR(CH,TOKEN);otherwisecallRECOGDEL(CH,TOKEN);endcase;writeTOKENintoTOKEN文件;Return}

2/5/2023103辛明影procedureRECOGID(CH,TOKEN);{WORD:=‘’;WORD:=WORD||CH;Repeat{callGETCH(CH);ifCH是字母或數(shù)字thenWORD:=WORD||CH;}untilCH!=字母或數(shù)字;ifCH是非法字符thencallPRINTERR(‘非法字符’)else列計數(shù)-1;ifWORD是關(guān)鍵字thenTOKEN:=(關(guān)鍵字種別碼,_)else{callLOOPUP(WORD,'標識符',ENTRY)TOKEN:=(標識符種別碼,ENTRY)};Return};識別標識符；輸入：CH中含標識符的首字母；輸出：TOKEN(二元式形式);2/5/2023104辛明影procedureHANDLECOM(TOKEN);{callGETCH(CH);ifCH!='*'then{列計數(shù)-1;TOKEN=(‘/’的識別碼,_);return};TOKEN='-1';GETCH(CH);while列計數(shù)<=行長-1do{CH1:=CH;callGETCH(CH);ifCH1='*'andCH='/'thenTOKEN:=‘';}ifTOKEN!=‘’thencallPRINTERR(‘注解未完’);TOKEN:=‘';return}處理注解(HANDLECOM);輸入：‘/’;進入該模塊之前已掃描了一個字符‘/’輸出：‘/’的TOKEN字或空TOKEN字;

2/5/2023105辛明影識別界限符(RECOGDEL)輸入：CH內(nèi)含單界限符；輸出：各種界符的TOKEN字;procedureRECOGDEL(CH,TOKEN);{caseCHof‘+’:TOKEN:=(‘+’的種別碼,_);‘)’:TOKEN:=(‘)’的種別碼,_);‘<’:{callGETCH(CH);ifCH=‘=’thenTOKEN:=(‘<=’的種別碼,_)elseifCH=‘>’thenTOKEN:=(‘<>’的種別碼,_)else{列計數(shù)-1;TOKEN:=(‘<’的種別碼,_)}}……..endcase;return}2/5/2023106辛明影3.3詞法分析程序的自動構(gòu)造工具LEX簡介一.原理單詞的結(jié)構(gòu)用正規(guī)式描述正規(guī)式NFADFAminDFALEX編譯器LEX源程序lex.1Lex.yy.c二.用LEX建立詞法分析程序的過程2/5/2023107辛明影C編譯器Lex.yy.ca.outa.out輸入流單詞序列三.lex源程序lex源程序由三部分組成2/5/2023108辛明影聲明%%翻譯規(guī)則%%輔助過程2/5/2023109辛明影

聲明包括變量，符號常量和正規(guī)定義式。翻譯規(guī)則的形式為：

p1{動作1}p2{動作2}……pn{動作n}2/5/2023110辛明影

每個pi是正規(guī)定義式的名子，每個{動作i}是正規(guī)定義式pi識別某類單詞時，詞法分析器應(yīng)執(zhí)行動作的程序段。用C書寫。標識符{字母}({字母}|{數(shù)字})*%%標識符{入口地址=LOOKUP();}%%LOOKUP()2/5/2023111辛明影輔助過程是動作需要的，這些過程用C書寫，可以分別編譯.例：LOOKUP()2/5/2023112辛明影第四章語法分析該講語法分析了！這可是很重要的章節(jié)2/5/2023113主要內(nèi)容：本章將重點介紹典型的語法分析方法及相關(guān)的概念和實現(xiàn)技術(shù)語法分析分為：自上而下:自下而上：遞歸下降分析法LL（1）預(yù)測分析法推導(dǎo)算符優(yōu)先分析法LR分析法歸約從根向葉的方向建立分析樹從葉向根的方向建立分析樹2/5/2023114辛明影4.1語法分析器的功能詞法分析器語法分析器語義分析符號表源程序單詞符號語法樹中間表示完成的任務(wù)：①對詞法分析器產(chǎn)生的單詞符號進行處理，輸出分析樹②與單詞相關(guān)的信息記錄到符號表中③類型檢查④錯誤處理4.1.1語法分析器任務(wù)2/5/2023115辛明影4.1.2相關(guān)約定一.符號的使用約定1.終結(jié)符①.字母表中比較靠前的小寫字,如a,b,c②.操作符，如+、-等③.標點符號，如括號、逗號等④.數(shù)字0、1、。。。9⑤.黑體串，如if、id等2/5/2023116辛明影2.下列符號是非終結(jié)符①.字母表中比較靠前的大寫字,如A、B、C②.字母S，常用來表示開始符號③.小寫斜體名字，如expr、stmt2/5/2023117辛明影3.字母表中比較靠后的大寫字母，如X、Y、Z等，用來表示文法符號，也就是說，可以是終結(jié)符，也可以是非終結(jié)符4.字母表中比較靠后的小寫字母，如u、v…z等，表示終結(jié)符的串聯(lián)5.小寫希臘字母α、β、γ等表示文法符號的串，所以一個產(chǎn)生式可寫作：A→α2/5/2023118辛明影4.2自頂向下分析法4.2.1使用的技術(shù)、存在的問題及解決方法2/5/2023119辛明影一、推導(dǎo)推導(dǎo)：就是用產(chǎn)生式的右部的串來代替左部的非終結(jié)符事實上推導(dǎo)給出了自頂向下構(gòu)成分析樹過程的精確描述例：有描述算術(shù)表達式的文法G字符串id+id*id是該文法的句子，其推導(dǎo)過程如下：E→E+E|E*E|（E）|-E|id2/5/2023120辛明影E幾個約定：=〉E+T=>E+T*F=>E+T*id

=〉E+F*id=〉E+id*idE=〉-EE推導(dǎo)出-E=>一步或多步推導(dǎo)=>零步或多步推導(dǎo)*+=〉T+id*id=〉F+id*id=〉id+id*id2/5/2023121辛明影最左推導(dǎo)：每一步都堅持替換當(dāng)前句型中

最左非終結(jié)符的推導(dǎo)最右推導(dǎo)：每一步都堅持替換當(dāng)前句型中

最右非終結(jié)符的推導(dǎo)，也稱為

規(guī)范推導(dǎo)+句子：S=〉w稱終結(jié)符串w是文法G句子

+句型：S=〉α

稱α是文法G的句型

+語言：L（G）={w/S=〉w

}2/5/2023122辛明影二、語法樹語法描繪了如何從文法的開始符號推導(dǎo)出一個句子的過程語法樹可以看成是推導(dǎo)的圖形表示，但它不能顯示出替代的順序前面句子id+id*id推導(dǎo)過程所對應(yīng)的分析樹如下：2/5/2023123辛明影EE+TTT*FFFididid2/5/2023124辛明影4.如杲A是某個內(nèi)結(jié)點的非終結(jié)符標記，A1，A2，……An是該結(jié)點從左到右排列的所有子結(jié)點的標記，則A→A1A2……An是一個產(chǎn)生式3.每個內(nèi)結(jié)點由一個非終結(jié)符標記1.樹根標記為開始符號2.每個葉結(jié)點由終結(jié)符或者ε標記語法具有如下特性的樹：2/5/2023125辛明影語法樹的葉結(jié)點從左到右的排列，剛好是這個文法所產(chǎn)生的語言的一個句子一個文法生成的語言就是它的某個分析樹所生成的句子的集合為給定的終結(jié)符串（句子）構(gòu)造一棵分析樹的過程稱為這個串（句子）的語法分析（parsing)2/5/2023126辛明影三、二義性句子id+id*id有兩棵分析樹與之對應(yīng)EE+EidE*EididEE*EE+Eididid2/5/2023127辛明影給定一個文法G，如果L（G）中存在一個具有兩棵或兩棵以上分析樹的句子，很顯然，描述算術(shù)表達式的文法G

E→E+E|E*E|（E）|-E|id是一個二義性文法造成二義性的原因是：文法中沒有體現(xiàn)出結(jié)合率和優(yōu)先級我們就稱該文法為二義性的，G也叫二義性文法。2/5/2023128辛明影

大多數(shù)的語法分析器都要求文法是無二義性的消除二義性：可以通過改寫文法來消除二義性例：stmt→ifexprthenstmt|ifexprthenstmtelsestmt|other2/5/2023129辛明影通過例子ifE1thenifE2thenS2elseS3很容易證明這是一個二義性文法sifEthenSelseSifEthenS2/5/2023130辛明影SifEthenSifEthenSelseS2/5/2023131辛明影在程序設(shè)計語言中，我們常常采用“最近匹配”原則來解決這種二義性文法改寫出為：

stmt→matched_stmt|unmatched_stmtmatched_stmt→

ifexprthenmatched_stmt

elsematched_stmt|otherunmatched_stmt→

ifexprthenmatched_stmt

elseunmatched_stmt

|ifexprthen_stmt2/5/2023132辛明影四、左遞歸如果文法G具有一個非終結(jié)符A使得對

某個字符串α存在推導(dǎo)A=>Aα,例：下面是描述算術(shù)表達式的算法S→EE→E+T|TT→T*F|FF→(E)|id為句子id*id+id構(gòu)造分析樹SE+TE+TE+T：則稱文法G是左遞歸的；如果A→Aα，則稱文法G是直接左遞歸的+2/5/2023133辛明影左遞歸會使分析進入到無限循環(huán)之中消除簡單左遞歸的方法：

對于含有左遞歸的產(chǎn)生式A→Aα|β可用下面的非左遞歸的產(chǎn)生式代替：

A→βA’A’→αA’|ε2/5/2023134辛明影例：下面是描述算術(shù)表達式的算法E→E+T|TT→T*F|FF→(E)|id消除E和T的直接左遞歸，得到：

E→TE’

E’→+TE’|εT→FT’F→(E)|idT’→*FT’|ε2/5/2023135辛明影對于一般情況而言，若某一文法G的產(chǎn)生式具有如下形式：

則可用如下方法消除左遞歸:A→Aα1|Aα2

|…|Aαm|

β1|β2|…|βn

A→β1A’|β2A’|…|βn

A’A’→α1A’|α2A’|…|αmA’|

ε很容易證明改造前后的文法是等價的2/5/2023136辛明影例：文法G（P）：P→（Q）|aP|aQ→Q,P|P試消除左遞歸2/5/2023137辛明影消除左遞歸后，方法改為：P→（Q）|aP｜aQ→PＱ’Q→，ＰＱ’｜ε2/5/2023138辛明影S→Qc|cQ→Rb|bR→Sa|aS這樣的遞歸無法用前面的方法消除對于含有間接左遞歸的文法：=>Qc=>Rbc=>Sabc出現(xiàn)了左遞歸2/5/2023139辛明影消除左遞歸的一般算法：輸入：無循環(huán)推導(dǎo)和ε產(chǎn)生式的方法G輸出：與G等價的無左遞歸文法算法：2/5/2023140辛明影1.以某種順序排列非終結(jié)符A1A2…An2.fori=1tondobeginforj=1toi-1dobegin改寫Ai→Ajγ

規(guī)則，方法如下：如果Aj→δ1|δ2|…|δk

則Ai→δ1γ

|δ2γ

|…|δnγ；end消除Ai中的所有直接左遞歸End3.化簡由2所得文法2/5/2023141辛明影S→Qc|cQ→Rb|bR→Sa|a對如下文法消除左遞歸：1.將非終結(jié)符排序為R、Q、S2.R不存在左遞歸，將R代入Q：

Q→Sab|ab|b3.Q不存在左遞歸，將Q代入S

S→Sabc|abc|bc|c4.消除直接左遞歸后，得文法：2/5/2023142辛明影S→abcS’|bcS’|cS’S’→abcS’|ε

Q→Rb|bR→Sa|a5.化簡文法S→abcS’|bcS’|cS’S’→abcS’|ε

2/5/2023143辛明影

Z->A

A->aB|aC|Ad|Ae

B->bBC|f

C->c

2/5/2023144辛明影五、提取左因子為句子ifE1thenS1elseS2構(gòu)造一棵語法樹文法：stmt→ifexprthenstmt|S|ifexprthenstmtelsestmtstmt

ifexprthenstmtE1ifＥ２

thenstmt

回溯2/5/2023145辛明影造成這種情況的原因是產(chǎn)生式具有相同的首符號，從而導(dǎo)致不清楚該用哪個來替換非終結(jié)符可通過改寫產(chǎn)生式來推遲這種決定，直到看見足夠多的輸入符號，可以作出正確選擇為止上例可改為：

stmt→ifexprthenstmtS’|S

S’→

elsestmt|ε2/5/2023146辛明影stmt

ifexprthenstmtS’

E1

elsestmt

提取左因子算法：輸入：文法G輸出：一個等價的提取了左因子的文法方法：對于A→αβ1|α

β2|…|α

βn|γ可改寫為：A→αA’|γA’→β1|β2|…|βn2/5/2023147辛明影例：文法G（P）：P→（Q）|aP|aQ→Q,P|P試消除回朔2/5/2023148辛明影六、FIRST與FOLLOW集1.FIRST集回朔和左遞歸搞的人真煩哪！

怎樣才能做到每次選的產(chǎn)生都正確呢？

郁悶?zāi)?！FIRST（α

）={a|α=>a…,a∈VT}如果α=>ε則ε∈FIRST（α

）。例：stmt→ifexprthenstmtS’S’→

elsestmtS’→

ε定義：FIRST（α）是由α推導(dǎo)出的所有的第一個終結(jié)符號組成的集合，即：2/5/2023149辛明影算法：求FIRST（X）的算法描述如下：例：First(ifexprthenstmtS’)={if}First(elsestmt)={else}First(ε)={ε}2/5/2023150辛明影⑶如果X是非終結(jié)符，且X→Y1Y2……Yk,則a)Y1=>εFIRST(Y1)中的所有符號都在FIRST（X）中b)Y1Y2……Yi-1=>ε,

FIRST（Yi）,中的所有符號都在FIRST（X）中②如果X→ε是一個產(chǎn)生式，則ε∈FIRST（X）①如果X是終結(jié)符，則FIRST（X）是{X}c)

Y1Y2……Yk=>ε,則ε∈FIRST（X）2/5/2023151辛明影例1：有文法G（S）S→BAA→BSA→dB→aAB→bSB→c試寫出其FIRST集First(B)={a}First(B)=First(B)={c}First(S)=First(BA)={a,b,c}First(A)=First(BS)={a,b,c}First(A)=uckgpnm2/5/2023152辛明影2.FOLLOW集定義：FOLLOW（A）是由所有句型中緊跟在A后面的終結(jié)符a組成的集合*FOLLOW（