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

編譯原理12/17/20241自我介紹姓名：辛明影電話： 86413213

教研室：計算機軟件基礎辦公室：綜合樓513

xmy63@xmy63@126.com助課教師：洪曉鵬，綜合樓614

單麗麗，新技術樓60812/17/2024計算機學院

2辛明影開課目的及應用前景：

介紹設計與構造程序設計語言編譯程序的原理與方法源程序編譯程序目標程序連接可執(zhí)行程序預備知識：形式語言與自動機、兩門以上的高級程序設計語言匯編語言數據結構等How?12/17/2024計算機學院

3辛明影內容簡介：第一章：編譯器的基本結構第二章：高級語言及其語法描述第三章：詞法分析器第四章：語法分析技術第五章：語法制導翻譯的主要概念及中間代碼第六章：程序運行時的存貯分配問題第七章：代碼優(yōu)化第八章：目標代碼生成12/17/2024計算機學院

4辛明影教學設計：(1)自頂向下，逐步求精的方法(2)問題驅動(3)將課程設計成一個應用平臺(4)用實驗拓廣課堂教學(5)精講多練(6)承前啟后教學目標：12/17/2024計算機學院

5辛明影第一章緒論編譯器就是一個程序，它讀入用某種語言編寫的源程序，并翻譯成一個與之等價的另一種語言編寫的源程序。編譯器源程序目標程序錯誤信息Fortran、Pascal、Java、C…..另一種程序設計語言、匯編語言、機器語言1.1什么叫編譯程序12/17/2024計算機學院

6辛明影1.2編譯過程概述編譯程序的工作，從輸入源程序開始，到輸出目標程序結束，與自然語言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經下列步驟：識別出句子中的單詞分析句子的語法結構根據句子的含義進行初步分析對譯文進行修飾寫出最后的譯文編譯程序詞法分析代碼優(yōu)化語法分析語義分析及中間代碼生成目標代碼生成構成編譯程序各個階段Iamaexperiencedteacher.12/17/2024計算機學院

7辛明影編譯器的各個階段：編譯器是分階段執(zhí)行的。每個階段將源程序從一種表示轉換成另一種表示源程序詞法分析器錯誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個階段12/17/2024計算機學院

8辛明影各分析階段隨著編譯器各個階段的進展，源程序的內部表示不斷地發(fā)生變化。以a=b+c*d

為例1。詞法分析讀入源程序完成的任務：識別出單詞：a、=、b、+、c、*、d并用記號方式表示識別出的單詞關鍵字、標識符、常數、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*記號表示邏輯上相關的字符序列，常用整數來表示上述單詞表示為：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)12/17/2024計算機學院

9辛明影語法分析在詞法分析的基礎上，根據語言的語法規(guī)則，把單詞符號串組成各類語法單位.具體的說，語法分析是在單詞流的基礎上建立一個層次結構-----建立語法樹賦值語句標識符=表達式a表達式標識符b+表達式表達式*標識符c表達式標識符d12/17/2024計算機學院

10辛明影語義分析階段語義分析利用語法分析階段確定的層次結構來識別表達式和語句中的操作信息及類型信息=+ab*c

dtemp1=c*dtemp2=b+temp1temp1temp2a=temp212/17/2024計算機學院

11辛明影中間代碼生成階段本階段將產生源程序的一個顯式中間表示這種中間表示可以看成是某種抽象的程序，通常是與平臺無關的其重要性質：1.易于產生

2.易于翻譯成目標程序下面是用三地址碼和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)12/17/2024計算機學院

12辛明影代碼優(yōu)化階段試圖改進中間代碼，以產生執(zhí)行速度較快的機器代碼對上面中間代碼進行優(yōu)化處理后，產生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp212/17/2024計算機學院

13辛明影代碼生成階段生成可重定位的機器代碼或匯編代碼MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R212/17/2024計算機學院

14辛明影1.3符號表管理int

a,b;floate,fcharch1,ch2;為什么要先說明?

定義了變量的類型，也就規(guī)定了變量在內存中的存放形式，在其上所能進行的運算解決符號地址到存貯地址上的映射12/17/2024計算機學院

15辛明影

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

0

4

并收集與每個標識符相關的各種屬性信息，int簡變12/17/2024計算機學院

16辛明影符號表的接口：符號表的作用就是存放字符串或詞素當一個字符串或詞素被保存時，與之相對應的記號也被保存符號表上的操作：Insert(s,t):將符號串s和記號t插入符號表，返回相應表項的指針Lookup(s):在符號表中查找字符串s，查找成功返回相應指針，否則返回012/17/2024計算機學院

17辛明影關鍵字的處理通常情況下，將關鍵字存在符號表中，作為符號表的初值。當詞法分析程序識別出一個標識符s后，用lookup(s)查找符號表，如果是關鍵字，返回相應的記號；如果是變量名，返回記號id12/17/2024計算機學院

18辛明影符號表的實現固定長標識符：采用前面的結構不定長標識符：使用單獨的數組lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放標識符的字符串,符號表中存放標識符在lexemes的起始位置和相應記號12/17/2024計算機學院

19辛明影1.4編譯各階段的分組一、前端和后端前端包括詞法分析、詞法分析、語義分析，以及相關的錯誤處理和符號表的建立前端依賴于源程序并在很大程度上獨立于目標機器。12/17/2024計算機學院

20辛明影后端主要包括代碼優(yōu)化、代碼生成和相關錯誤處理。后端依賴于目標機器。后端處理對象是由前端產生的結果，即中間代碼前端生成與平臺無關的字節(jié)碼后端是由與平臺有關的解釋器對所生成的字節(jié)碼文件進行解釋執(zhí)行Java語言的編譯采用的是前端后端方式。12/17/2024計算機學院

21辛明影二、編譯的遍編譯的若干階段通常是以一遍來實現的，每遍讀一次輸入文件、產生一個輸出文件。12/17/2024計算機學院

22辛明影在編譯的各個階段都會發(fā)現源程序中的錯誤，1.5錯誤檢測與報告為了使編譯器能繼續(xù)運行，以檢測出源程序中更多的錯誤，在檢測到錯誤后，必須以合適的方式進行錯誤處理。error12/17/2024計算機學院

23辛明影第二章高級語言

及其語法描述12/17/202424內容簡介：本章概述程序設計語言的結構2.1程序語言的定義任何語言實現的基礎是語言定義。語言的定義決定了該語言

具有什么樣的語言功能、

什么樣的數據結構、

什么樣的程序結構、

以及具體的使用形式等細節(jié)問題。和主要的共同特征，并介紹程序設計語言主要語句的文法描述與形式定義。12/17/2024計算機學院

25辛明影

對于編譯程序設計者來說：語言定義就是具體實現的理論依據。

對于語言用戶來說：語言定義就是一本用戶手冊。2.1.1語法語言的語法是指這樣一組規(guī)則，用它可產生一個程序。規(guī)則：詞法規(guī)則語法規(guī)則12/17/2024計算機學院

26辛明影詞法規(guī)則是指單詞符號的形成規(guī)則字母表就是一個有窮字符集。C語言的字母表為：

∑={a---z、

A—Z、

0—9、(、)、

[、]、

、.、!、~、+、-、*、

/、&、%、<、>、=、^、

|、?、,、;}C語言的標識符的構成規(guī)則：

字母、下劃線打頭的字母、數字和下劃線構成的符號串。如：a1、ave

、_day一.詞法規(guī)則12/17/2024計算機學院

27辛明影上述的定義是用文字來描述的，當設計編譯程序時，就要把它用形式的方式描述出來，就要用到形式語言。各類型的常數、標識符、基本字、算符和界符等正規(guī)式和有窮自動機是描述詞法結構和進行詞法分析的有效工具在現今多數程序設計語言中，單詞符號一般包括：12/17/2024計算機學院

28辛明影C語言的標識符的文法和自動機描述：例：C語言標識符的文法描述L（G）={w/w為字母或‘-’打頭的字母數字串}解：P:I→aBI→-BI→aB→aB

B→dBB→aB→d識別L（G）的自動機IBTa-a,d其它12/17/2024計算機學院

29辛明影SACDFEB7ddddddd

ee+–T*例：C語言實常數的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e2412/17/2024計算機學院

30辛明影二.語法規(guī)則語法規(guī)則規(guī)定了如何從單詞符號形成更大的結構（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則一般的程序設計語言的語法單位有：表達式、語句、分程序、函數、過程和程序等

下推自動機理論和上下文無關文法是我們討論語法分析的理論基礎12/17/2024計算機學院

31辛明影表達式：

E→E+TE→E-TE→TT→T*FT→T/F

T→FF→(E)F→id主要語句的形式描述：12/17/2024計算機學院

32辛明影布爾表達式：

B→BorBB→BandBB→notBB→(E）

B→idrelopidB→trueB→false12/17/2024計算機學院

33辛明影賦值、分支、循環(huán)語句：

S→id=ES

→ifBthenS

S→ifBthenSelseS

S→whileBdoSS→{L}

L→L;S

L→S12/17/2024計算機學院

34辛明影調用語句：

S→callid(Elist)

Elist→Elist,E

Elist→E|ε12/17/2024計算機學院

35辛明影類型說明和過程說明語句：

P→DD→D;DD→id:TD→id（Elist）D;S

T→intT→float12/17/2024計算機學院

36辛明影數組說明語句：

L→id[Elist]

Elist→Elist,E

Elist→E12/17/2024計算機學院

37辛明影2.1.2

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

對于一個語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義，這就是語義問題對于編譯程序來說，只有了解程序的語義，才知道應把它翻譯成什么樣的目標指令代碼12/17/2024計算機學院

38辛明影2.2構造基礎2.2.1程序結構簡介一個高級語言程序通常由若干子程序段（過程、函數等）組成，許多語言還引入了類、程序包等更高級的結構12/17/2024計算機學院

39辛明影FORTRAN一個FORTRAN程序由一個主程序和若干個輔助程序段組成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定義是并列的12/17/2024計算機學院

40辛明影

FORTRAN

的構成特點：同一名字在不同的程序段中一般都代表不同的對象，也就是說代表不同的存貯單元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.

ENDSUBROUTINESUB1

.END一個名字對應多個對象12/17/2024計算機學院

41辛明影但是不同程序段里的同名公用塊卻代表同一個存貯區(qū)域PROGRAMMAIN.

Commona,bENDSUBROUTINESUB1

commonx,y.ENDPROGRAMMAIN.

ENDSUBROUTINESUB1

.ENDCommona,babA=100B=50

10050Commonx,yxyY=x+100200共享存貯單元多個名字對應一個對象12/17/2024計算機學院

42辛明影二。PascalPascal允許子程序嵌套定義

Programmain

說明部分Begin

可執(zhí)行部分endPascal的程序結構Programmain

BeginendProcedureP1BeginendProcedureP11BeginendProcedureP2Beginend也允許并列定義12/17/2024計算機學院

43辛明影關于名字的作用域的規(guī)定：標識符X的任意一次出現（除去說明語句中）都意味著對某個說明語句中說明的這個變量X的引用此時，說明語句同標識符X應共處一個最小程序中，即：P1中說明的X只在P1中有效

P11是P1的內層子程序，P11中沒有再對X作新的說明，則在P11中對X的引用，實際上引用的就是P1中說明的X，

即內部過程可以引用外部過程中定義的量12/17/2024計算機學院

44辛明影三.javaJava語言是一種面向對象的高級語言，它很重要的方面是類和繼承的概念，同時支持多態(tài)性和動態(tài)綁定等特性Classcar{Intcolor_num;Intdoor_num;Intspeed;.Voidpush_break(){}

Voidadd_oil(){}}Classbenzextendscar

Doubleprice;VoidABS(){}

}12/17/2024計算機學院

45辛明影

一個類把有關的數據及其操作封裝在一起構成一個抽象數據類型一個子類繼承其父類的所有數據和方法，并且可以加入自己新的定義

在java中，變量和方法的定義之前可以加上public、private、pretected等修飾詞，以限制其它類的對象對于這些變量和方法的使用12/17/2024計算機學院

46辛明影2.2.2構造基礎程序設計語言的數據對象：數據、函數、過程常用能反映其本質的、有助于記憶的名字來表示一.名字特性：一個名字對應一個對象，普通變量多個名字對應一個對象一個名字對應多個對象，common,數組、重載、局部變量、重寫、12/17/2024計算機學院

47辛明影

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

值在計算機內的表示，

以及對它能施加什么樣的運算12/17/2024計算機學院

48辛明影二.數據類型1.初等數據類型①數值數據：整形、實型、雙精度等，可施行算術運算②邏輯數據：可施行邏輯運算③字符數據：④指針類型：12/17/2024計算機學院

49辛明影三。數據結構1。數組從邏輯上講，一個數組是由同類型數據所組成的n維矩形結構一個數組所需的存貯空間大小在編譯時就已知道的，則稱此數組是一個確定的數組；否則稱為可變數組設intA[l1‥u1,][l2‥u2]……[ln‥un]為n維數組各維的長度：di=ui-li+1(1≤i≤n)12/17/2024計算機學院

50辛明影任一數組元素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+ln

C是數組計算中不變的部分12/17/2024計算機學院

51辛明影變量部分：v=(……

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

+in-1)dn+in任一數組元素A[i1,i2,……in]的地址:

addr=a-c+v12/17/2024計算機學院

52辛明影在編譯時，當遇到說明時，必須把數組的有關信息記錄在一個“內情向量”之中，用于數組元素的地址計算。數組的內情向量包括：維數，各維的上、下限，首地址及數組的類型……lnundn…………l2l1unund1d2N維數C常數T類型A首地址12/17/2024計算機學院

53辛明影對于確定數組來說，內情向量可登記在符號表中；

對于可變數組，內情向量的信息在編譯時無法全部知道，只有到運行階段才能全部確定下來，存貯分配也要等到運行時方能進行12/17/2024計算機學院

54辛明影2.記錄（結構）從邏輯上講，記錄是由已知的數據組合起來的一種結構

Structstudent{charname[20];

boolean

partmember;

intage;}stu;12/17/2024計算機學院

55辛明影記錄結構最簡單的存貯方式是連續(xù)存放上述的變量stu共占7個字，共28個字節(jié)

SStu.partmember

Stu.age3.字符串、表格和隊列kK+1….K+20….K+24….….……….12/17/2024計算機學院

56辛明影四.抽象數據類型一個抽象數據類型包括：⑶這種類型對象的封裝⑵作用于這些數據對象的抽象運算的集合⑴數據對象的一個集合C++、Java語言通過類對抽象類型提供支持12/17/2024計算機學院

57辛明影五.語句與控制結構1.表達式要解決的問題：①優(yōu)先級②結合率2.語句語句可分為：①說明語句：②可執(zhí)行語句：定義各種不同數據類型的變量和運算描述語句的動作執(zhí)行語句分為：賦值、控制和I/O語句12/17/2024計算機學院

58辛明影⑴賦值句A=B左值右值名字的左值指它所代表的存貯單元地址名字的右值指該單元的內容12/17/2024計算機學院

59辛明影⑵控制語句無條件轉移語句：Goto

lable條件語句：IfBthenSIfBthenSelseS循環(huán)語句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3過程調用語句：CallP(x1,x2,….xn)返回語句：Return(E)12/17/2024計算機學院

60辛明影⑶說明語句說明語句用于定義名字的性質。編譯程序把這些性質登記在符號表中，并檢查程序中名字的引用和說明是否一致。許多說明語句不產生目標代碼但有的說明語句，如過程說明和可變數組說明，則要產生相應的目標代碼12/17/2024計算機學院

61辛明影⑷簡單句和復合句簡單句是指不包含其它語句成分的基本句。賦值、goto語句等復合句則指那些句中有句的語句If(x==0)thenx=1{x=1;y=2;gotol1;}12/17/2024計算機學院

62辛明影

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參數傳遞

結果是什么？12/17/2024計算機學院

63辛明影1傳值調用

實在參數和形式參數結合的方法：傳值調用（call-by-value）

引用調用（call-by-reference）

復制恢復（copy-restore）

傳名調用（call-by-name）12/17/2024計算機學院

64辛明影

子程序為每一個形參開辟一個存貯單元，用于存放相應實參的值。子程序執(zhí)行時，每當訪問形參時，就直接訪問形參單元。實參：形參：傳值調用可以實現如下：主調過程計算實在參數，并把它們的右-值放入到形式參數的存儲空間中。12/17/2024計算機學院

65辛明影使用傳值的方法，調用swap（a,b）等價于下面幾步：

x：=a

y：=b

temp：=x

x：=y

y：=temp12/17/2024計算機學院

66辛明影2引用調用（傳地址）

把實在參數的地址傳遞給相應的形式參數,

在目標代碼中，在被調用過程中對形式參數的一次引用就成為對傳遞給被調用過程的指針的一個間接引用。Referenceabxy12swapabtemp12/17/2024計算機學院

67辛明影子程序為每個形參開辟一個單元，用于存放相應實參的地址，執(zhí)行時，子程序間址方式訪問這些形參單元

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

x:=y;y:=temp;temp:=a;a:=b;b:=temp;12/17/2024計算機學院

68辛明影3復制恢復（傳值結果）實現：

1.當控制流入到被調用過程之前，把實在參數的右-值和左-值傳遞到被調用過程中；

2.當控制返回時，把形式參數的現行右-值復制回到相應的實在參數的左-值中。12/17/2024計算機學院

69辛明影

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

執(zhí)行時，對B2單元使用直接訪問形式；返回前，按B1中的地址把B2中的內容存入主調程序的實參單元中。實參：地址形參：B1B2@B112/17/2024計算機學院

70辛明影

在主調程序中設置計算實參地址和右值的形實替換子程序THUNK

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

執(zhí)行時，每當要對形參進行訪問時，就調用THUNK子程序，以獲得相應實參地址或值4傳名調用對形參的訪問是發(fā)生在實參單元上的12/17/2024計算機學院

71辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end12/17/2024計算機學院

72辛明影傳值：abc實參形參xyz234P(a,b,c);234y=y+1;

輸出：23446Z=z+x;A=2B=3C=412/17/2024計算機學院

73辛明影傳地址：abc實參形參xyz234P(a,b,c);&a&b&cy=y+1;@y=@y+1輸出：24646Z=z+x;@z=@z+@x12/17/2024計算機學院

74辛明影傳值結果：abc實參形參X—B1B2Y—B1B2Z—B1B2234&a&b

y=y+1;

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

按@B1返回B2

的值4

6

2344

612/17/2024計算機學院

75辛明影傳名：abc實參形參xyz234P(a,b,c);&thunk&thunk&thunky=y+1;JSRThunkY→b輸出：24646Z=z+x;

jsr

ThunkZ→c,x→a12/17/2024計算機學院

76辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;P(a+b,a,a);printaend12/17/2024計算機學院

77辛明影傳值：aba+b實參形參xyz23P(a+b,a,a);522y=y+1;

輸出：2

37Z=z+x;A=2B=3512/17/2024計算機學院

78辛明影傳地址：aba+b實參形參xyz235P(a+b,a,a);&a+b&a&ay=y+1;@y=@y+1輸出：83Z=z+x;@z=@z+@x812/17/2024計算機學院

79辛明影傳名：ab實參形參xyz23P(a+b,a,a);&thunk&thunk&thunky=y+1;JSRThunkY→a輸出：939Z=z+x;

jsr

ThunkZ→a,x→a+b12/17/2024計算機學院

80辛明影第三章詞法分析12/17/202481編譯器的各個階段：編譯器是分階段執(zhí)行的。每個階段將源程序從一種表示轉換成另一種表示源程序詞法分析器錯誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個階段12/17/2024計算機學院

82辛明影3.2詞法分析器的手工構造：用DFA能識別3.3詞法分析程序自動構造工具LEX簡介3.1詞法分析程序的設計：

12/17/2024計算機學院

83辛明影=80;0134256eniL字母字母字母字母數字數字數字==；；0124563Line=80;

id(25),‘Line’

=(

36),

num(27),‘80’

;(45),數字字母字母11==0003;;1輸入輸出有窮控制器單詞的詞類和屬性（詞類符號，單詞的屬性）12/17/2024計算機學院

84辛明影

3.1詞法分析程序的設計二、掃描器的任務

一、詞法分析程序的功能

源程序

單詞序列

詞法分析器1、組織源程序的輸入2、識別單詞，轉換成機內表示形式3、刪除注釋行、空格及無用符號4、查填符號表5、檢查詞法錯誤12/17/2024計算機學院

85辛明影<12,><25,符號表入口><39,><25,符號表入口><20,><25,符號表入口><36,><26,常數表入口><8,><25,符號表入口><36,><26,常數表入口>ifi＞jtheni:＝0

elsej:=1詞法分析if

I＞JThenI＝0

elsej=112/17/2024計算機學院

86辛明影三、詞類和屬性2．標識符：用來表示各種名字3．字面常數：256，3.14，true,‘abc’4．運算符：如，＋、－、*、/等等5．分界符：如逗號，分號，冒號等程序語言單詞的分類：

1．關鍵字(保留字或基本字)：while,if12/17/2024計算機學院

87辛明影界符和運算符:詞法分析器的輸出：（詞類編碼，單詞自身的屬性值）關鍵字可分成一類，也可以一個關鍵字分成一類。常數可統(tǒng)歸一類，也可按類型（整型、實型、布爾型等），每個類型的常數劃分成一類。所有的標識符分為一類。詞類編碼原則:一字一碼。一類型一碼。一類一碼。一符一碼。12/17/2024計算機學院

88辛明影

表3.1單詞詞類編碼12/17/2024計算機學院

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

90辛明影對于常數，其單詞自身的屬性常用其在常數表中的入口指針來表示12/17/2024計算機學院

91辛明影

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

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

12/17/2024計算機學院

92辛明影

四、詞法分析的設計形式（1）設計成一個獨立程序，完成詞法分析的任務，結果以文件的形式組織，做為語法分析的輸入源程序詞法分析符號表TOKEN字錯誤信息12/17/2024計算機學院

93辛明影詞法分析語法分析語義分析和中間代碼生成源程序中間代碼

符號表管理

錯誤的診查處理（2）作為語法分析和語義分析的子程序12/17/2024計算機學院

94辛明影

五、詞法分析程序的設計框圖SCANNEROUTPUTsort字母RECOGID數字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP12/17/2024計算機學院

95辛明影3

2詞法分析器的手工構造為了構造詞法分析器，要研究構詞法，每種詞類的結構模式以及識別它的數學模型——有窮自動機。3

21確定的有限自動機（DFA）3

22構造識別單詞的DFA3

23編寫詞法分析程序12/17/2024計算機學院

96辛明影SCANNEROUTPUTsort字母RECOGID數字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP12/17/2024計算機學院

97辛明影一、手工構造識別單詞的DFAm

根椐DFA識別單詞的定義，在研究給定程序語言單詞結構的基礎上，能直接構造出識別它的DFAm。例如：對于C語言整數：非空數字串。無符號實數（用d表示數字）:(a)dd.ddE(+-)ddddE(+-)dd(c)dd.dd0.1e+1412e-43.141592(d)dd…dd100012/17/2024計算機學院

98辛明影IBTTa-a,d其它例：C語言的標識符標識符：字母開始的字母數字串。12/17/2024計算機學院

99辛明影例：C語言實常數的文法描述01234567dddEdEd-+dd10003.141512e-40.1e+14.12/17/2024計算機學院

100辛明影在識別標識符的過程中，首先要拼寫出來，并和保留字區(qū)別開來；識別出的標識符要填入符號表中二、編寫詞法分析程序根據畫出的狀態(tài)轉換圖（識別單詞的）構造詞法分析程序，每個狀態(tài)對應一段程序，完成到達此狀態(tài)的工作；在識別常數的過程中，要把它轉換成機器表示以作為屬性值，記錄到常數表中。

詞法分析程序的控制程序模擬狀態(tài)轉換圖的狀態(tài)轉換。12/17/2024計算機學院

101辛明影programSCANNER;Begininitiate符號表,字符串表,行,列計數器;Open源文件,TOKEN文件,打印機文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符號表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;模塊0：掃描器主控12/17/2024計算機學院

102辛明影單詞分類模塊(SORT)輸入：CH內含單詞首符；procedureSORT(CH);{caseCHof‘字母’:‘字母’:callRECOGID(CH,TOKEN);‘/’:callHANDLECOM(CH,TOKEN);‘數字’:callRECOGDIG(CH,TOKEN);‘’‘callRECOGSTR(CH,TOKEN);otherwisecallRECOGDEL(CH,TOKEN);endcase;writeTOKENintoTOKEN文件;Return}

12/17/2024計算機學院

103辛明影procedureRECOGID(CH,TOKEN);{WORD:=‘’;

WORD:=WORD||CH;Repeat{callGETCH(CH);ifCH是字母或數字thenWORD:=WORD||CH;}untilCH!=字母或數字;ifCH是非法字符thencallPRINTERR(‘非法字符’)else列計數-1;ifWORD是關鍵字thenTOKEN:=(關鍵字種別碼,_)else{callLOOPUP(WORD,'標識符',ENTRY)TOKEN:=(標識符種別碼,ENTRY)};Return};識別標識符；輸入：CH中含標識符的首字母；輸出：TOKEN(二元式形式);12/17/2024計算機學院

104辛明影procedureHANDLECOM(TOKEN);{callGETCH(CH);ifCH!='*'then{列計數-1;TOKEN=(‘/’的識別碼,_);return};TOKEN='-1';GETCH(CH);while列計數<=行長-1do{CH1:=CH;callGETCH(CH);ifCH1='*'andCH='/'thenTOKEN:=‘';}ifTOKEN!=‘’thencallPRINTERR(‘注解未完’);TOKEN:=‘';return}處理注解(HANDLECOM);輸入：‘/’;進入該模塊之前已掃描了一個字符‘/’輸出：‘/’的TOKEN字或空TOKEN字;

12/17/2024計算機學院

105辛明影識別界限符(RECOGDEL)輸入：CH內含單界限符；輸出：各種界符的TOKEN字;procedureRECOGDEL(CH,TOKEN);{caseCHof‘+’:TOKEN:=(‘+’的種別碼,_);‘)’:TOKEN:=(‘)’的種別碼,_);‘<’:{callGETCH(CH);ifCH=‘=’thenTOKEN:=(‘<=’的種別碼,_)elseifCH=‘>’thenTOKEN:=(‘<>’的種別碼,_)

else{列計數-1;TOKEN:=(‘<’的種別碼,_)}}……..

endcase;return}12/17/2024計算機學院

106辛明影3.3詞法分析程序的自動構造工具LEX簡介一.原理單詞的結構用正規(guī)式描述正規(guī)式

NFA

DFA

minDFALEX編譯器LEX源程序lex.1Lex.yy.c二.用LEX建立詞法分析程序的過程12/17/2024計算機學院

107辛明影C編譯器Lex.yy.ca.outa.out輸入流單詞序列三.lex源程序

lex源程序由三部分組成12/17/2024計算機學院

108辛明影聲明%%翻譯規(guī)則%%輔助過程12/17/2024計算機學院

109辛明影

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

p1{動作1}

p2{動作2}……

pn{動作n}12/17/2024計算機學院

110辛明影

每個pi是正規(guī)定義式的名子，每個{動作i}是正規(guī)定義式pi識別某類單詞時，詞法分析器應執(zhí)行動作的程序段。用C書寫。標識符{字母}({字母}|{數字})*%%標識符{入口地址=LOOKUP();}%%LOOKUP()12/17/2024計算機學院

111辛明影輔助過程是動作需要的，這些過程用C書寫，可以分別編譯.例：LOOKUP()12/17/2024計算機學院

112辛明影第四章語法分析該講語法分析了！這可是很重要的章節(jié)12/17/2024113主要內容：本章將重點介紹典型的語法分析方法及相關的概念和實現技術語法分析分為：自上而下:自下而上：遞歸下降分析法

LL（1）預測分析法推導算符優(yōu)先分析法LR分析法歸約從根向葉的方向建立分析樹從葉向根的方向建立分析樹12/17/2024計算機學院

114辛明影4.1語法分析器的功能詞法分析器語法分析器語義分析符號表源程序單詞符號語法樹中間表示完成的任務：

①對詞法分析器產生的單詞符號進行處理，輸出分析樹

②與單詞相關的信息記錄到符號表中③類型檢查④錯誤處理4.1.1語法分析器任務12/17/2024計算機學院

115辛明影4.1.2相關約定一.符號的使用約定1.終結符①.字母表中比較靠前的小寫字,如a,b,c②.操作符，如+、-等③.標點符號，如括號、逗號等④.數字0、1、。。。9⑤.黑體串，如if、id等12/17/2024計算機學院

116辛明影2.下列符號是非終結符①.字母表中比較靠前的大寫字,如A、B、C②.字母S，常用來表示開始符號③.小寫斜體名字，如expr、stmt12/17/2024計算機學院

117辛明影3.字母表中比較靠后的大寫字母，如X、Y、Z等，用來表示文法符號，也就是說，可以是終結符，也可以是非終結符4.字母表中比較靠后的小寫字母，如u、v…z等，表示終結符的串聯5.小寫希臘字母α、β、γ等表示文法符號的串，所以一個產生式可寫作：

A→α12/17/2024計算機學院

118辛明影4.2自頂向下分析法4.2.1使用的技術、存在的問題及解決方法12/17/2024計算機學院

119辛明影一、推導推導：就是用產生式的右部的串來代替左部的非終結符事實上推導給出了自頂向下構成分析樹過程的精確描述例：有描述算術表達式的文法G字符串id+id*id

是該文法的句子，其推導過程如下：E→E+E|E*E|（E）|-E|id12/17/2024計算機學院

120辛明影E幾個約定：=〉E+T=>E+T*F=>E+T*id

=〉E+F*id=〉E+id*idE=〉-EE推導出-E=>一步或多步推導=>零步或多步推導*+=〉T+id*id=〉F+id*id=〉id+id*id12/17/2024計算機學院

121辛明影最左推導：每一步都堅持替換當前句型中

最左非終結符的推導最右推導：每一步都堅持替換當前句型中

最右非終結符的推導，也稱為

規(guī)范推導

+句子：S=〉w稱終結符串w是文法G句子

+句型：S=〉α

稱α是文法G的句型

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

}12/17/2024計算機學院

122辛明影二、語法樹語法描繪了如何從文法的開始符號推導出一個句子的過程語法樹可以看成是推導的圖形表示，但它不能顯示出替代的順序前面句子id+id*id推導過程所對應的分析樹如下：12/17/2024計算機學院

123辛明影

EE+TTT*FFFididid12/17/2024計算機學院

124辛明影4.如杲A是某個內結點的非終結符標記，A1，A2，……An是該結點從左到右排列的所有子結點的標記，則A→A1A2……An是一個產生式3.每個內結點由一個非終結符標記1.樹根標記為開始符號2.每個葉結點由終結符或者ε標記語法具有如下特性的樹：12/17/2024計算機學院

125辛明影語法樹的葉結點從左到右的排列，剛好是這個文法所產生的語言的一個句子一個文法生成的語言就是它的某個分析樹所生成的句子的集合為給定的終結符串（句子）構造一棵分析樹的過程稱為這個串（句子）的語法分析（parsing)12/17/2024計算機學院

126辛明影三、二義性句子id+id*id有兩棵分析樹與之對應EE+EidE*EididEE*EE+Eididid12/17/2024計算機學院

127辛明影給定一個文法G，如果L（G）中存在一個具有兩棵或兩棵以上分析樹的句子，很顯然，描述算術表達式的文法G

E→E+E|E*E|（E）|-E|id

是一個二義性文法造成二義性的原因是：文法中沒有體現出結合率和優(yōu)先級我們就稱該文法為二義性的，G也叫二義性文法。12/17/2024計算機學院

128辛明影

大多數的語法分析器都要求文法是無二義性的消除二義性：可以通過改寫文法來消除二義性例：stmt→ifexprthenstmt|ifexprthenstmtelsestmt|other12/17/2024計算機學院

129辛明影通過例子

ifE1thenifE2thenS2elseS3很容易證明這是一個二義性文法sifEthenSelseSifEthenS12/17/2024計算機學院

130辛明影SifEthenSifEthenSelseS12/17/2024計算機學院

131辛明影在程序設計語言中，我們常常采用“最近匹配”原則來解決這種二義性文法改寫出為：

stmt→matched_stmt|unmatched_stmtmatched_stmt→

ifexprthenmatched_stmt

elsematched_stmt|otherunmatched_stmt→

ifexprthenmatched_stmt

elseunmatched_stmt

|ifexprthen_stmt12/17/2024計算機學院

132辛明影四、左遞歸如果文法G具有一個非終結符A使得對

某個字符串α存在推導A=>Aα,例：下面是描述算術表達式的算法

S→EE→E+T|TT→T*F|FF→(E)|id為句子id*id+id構造分析樹

SE+TE+TE+T：則稱文法G是左遞歸的；如果A→Aα，則稱文法G是直接左遞歸的+12/17/2024計算機學院

133辛明影左遞歸會使分析進入到無限循環(huán)之中消除簡單左遞歸的方法：

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

A→βA’A’→αA’|ε12/17/2024計算機學院

134辛明影例：下面是描述算術表達式的算法

E→E+T|TT→T*F|FF→(E)|id消除E和T的直接左遞歸，得到：

E→TE’

E’→+TE’|εT→FT’F→(E)|idT’→*FT’|ε12/17/2024計算機學院

135辛明影對于一般情況而言，若某一文法G的產生式具有如下形式：

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

|…|Aαm|

β1|β2|…|βn

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

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

ε很容易證明改造前后的文法是等價的12/17/2024計算機學院

136辛明影例：文法G（P）：

P→（Q）|aP|aQ→Q,P|P試消除左遞歸12/17/2024計算機學院

137辛明影消除左遞歸后，方法改為：

P→（Q）|aP｜aQ→PＱ’

Q→，ＰＱ’｜ε12/17/2024計算機學院

138辛明影

S→Qc|cQ→Rb|bR→Sa|aS這樣的遞歸無法用前面的方法消除對于含有間接左遞歸的文法：=>Qc=>Rbc=>Sabc出現了左遞歸12/17/2024計算機學院

139辛明影消除左遞歸的一般算法：輸入：無循環(huán)推導和ε產生式的方法G輸出：與G等價的無左遞歸文法算法：12/17/2024計算機學院

140辛明影1.以某種順序排列非終結符A1A2…An2.fori=1tondobeginforj=1toi-1dobegin

改寫Ai→Aj

γ

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

則Ai→δ1γ

|δ2γ

|…|δnγ；end

消除Ai中的所有直接左遞歸End3.化簡由2所得文法12/17/2024計算機學院

141辛明影

S→Qc|cQ→Rb|bR→Sa|a對如下文法消除左遞歸：1.將非終結符排序為R、Q、S2.R不存在左遞歸，將R代入Q：

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

S→Sabc|abc|bc|c4.消除直接左遞歸后，得文法：12/17/2024計算機學院

142辛明影

S→abcS’|bcS’|cS’

S’→abcS’|ε

Q→Rb|bR→Sa|a5.化簡文法

S→abcS’|bcS’|cS’

S’→abcS’|ε

12/17/2024計算機學院

143辛明影

Z-