1、第 2 講西北農(nóng)林科技大學本科教程 主講教師： 第二章詞法分析前三節(jié)2.1 詞法分析器的設計方法2.2 一個簡單的詞法分析器2.3 正規(guī)表達式與有限自動機簡介重點掌握 狀態(tài)轉(zhuǎn)換圖的概念正規(guī)表達式的概念和運算本講目標 第二章第二章 詞法分析詞法分析2.1 詞法分析器的設計方法2.2 一個簡單的詞法分析器2.3 正規(guī)表達式與有限自動機簡介2.4 正規(guī)表達式到有限自動機的構造2.5 詞法分析器的自動生成回顧詞法分析器：定位詞法分析是編譯的第一個階段任務從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞（Token）符號功能輸入源程序，輸出單詞符號（流）不斷訪問、更新符號表2.1 詞法分析器的設計方法

2、 詞法分析器的處理結構（2種）：第一種：詞法分析器和語法分析器完全分開詞法分析器的輸出（單詞符號流）作為語法分析器的輸入 將詞法分析工作作為獨立的一遍來完成，在這個過程中不斷查詢和完善符號表2.1 詞法分析器的設計方法 圖圖2-1(a) 詞法分析程序作為主程序詞法分析程序作為主程序詞法分析器的處理結構（2種）：第二種：詞法分析器作為語法分析器調(diào)用的子程序每當語法分析器需要一個單詞時便調(diào)用詞法分析器詞法分析和語法分析交替進行2.1 詞法分析器的設計方法 圖2-1 (b) 詞法分析程序作為子程序：單詞符號的分類與輸出形式分類：單詞符號是程序語言的基本語法單位，具有確定的語法意義。程序語言的單詞符號

3、通常可分為下面五種：保留字：如C語言中的if、else、while和do等幾乎所有的程序語言都禁止用戶使用保留字作為標識符標識符：用戶自己定義的常量名、變量名、方法名等常數(shù)：布爾常數(shù)（true/false）和其它常數(shù)運算符： “+”、“-”、“*”、“/”、“”、“1) b=100;如果采用每種單詞對應一個整數(shù)碼，對應的如果采用每種單詞對應一個整數(shù)碼，對應的二元式序列？二元式序列？假如五類單詞的種別規(guī)定如下：假如五類單詞的種別規(guī)定如下：保留字保留字if種別：種別：2標識符種別：標識符種別：10常量種別：常量種別： 11 “=”種別：種別： 17 “”種別：種別： 23“;”種別：種別： 26“

4、(”種別：種別： 29“)”種別：種別： 30102.1 單詞符號分類舉例 上面的子程序輸出的二元式序列：( 2, ） if ( 29, ) ( 10,a ) a( 23, ) ( 11,1的二進制） 1 ( 30, ) )( 10,b ) b( 17, ) =( 11,100的二進制) 100（ 26， ) ;采用第一種表示：狀態(tài)轉(zhuǎn)換圖（概念）上一小節(jié)解決了單詞符號的表示，但是如何識別單詞呢？ 答：借助“狀態(tài)轉(zhuǎn)換圖” 在詞法分析中，可以用狀態(tài)轉(zhuǎn)換圖來識別單詞。狀態(tài)轉(zhuǎn)換圖是狀態(tài)有限的有向圖，結點代表狀態(tài)，用圓圈表示；結點之間可由有向邊連接，代表狀態(tài)轉(zhuǎn)換關系，有向邊上可標記字符，表示前一狀態(tài)接受

5、某一個字符之后的狀態(tài)轉(zhuǎn)移 2.1 詞法分析器的設計方法 例如，右圖表示在狀態(tài)i下的狀態(tài)轉(zhuǎn)換：若輸入字符為x，則讀入x并轉(zhuǎn)換到狀態(tài)j；若輸入字符為y，則讀入y并轉(zhuǎn)換到狀態(tài)k。：狀態(tài)轉(zhuǎn)換圖（表示）狀態(tài)轉(zhuǎn)換圖的要求狀態(tài)（即結點）個數(shù)有限至少一個初始狀態(tài)，若干終止狀態(tài)每條邊上標有字符（也可以是空字符）狀態(tài)轉(zhuǎn)換圖的表示習慣初始狀態(tài)用“ ”表示非終止狀態(tài)用“”表示狀態(tài)之間的跳轉(zhuǎn)用“ ”（有向邊）表示終止狀態(tài)用“*”表示2.1 詞法分析器的設計方法 字符：狀態(tài)轉(zhuǎn)換圖（表示）特別說明：終止狀態(tài)用“*”表示某些終止狀態(tài)是在讀入了一個其它不屬于該單詞的符號后才得到相應的單詞編碼的，這表明在識別單詞的過程中多讀入了

6、一個符號，所以識別出單詞后應將最后多讀入的這個符號予以回退；我們對此類情況的處理是在終態(tài)上以“*”作為標識。2.1 詞法分析器的設計方法 例如：想要識別數(shù)字數(shù)字，輸入“234a” 讀入2：狀態(tài)0-1 讀入3：狀態(tài)1 讀入4：狀態(tài)1 讀入a：狀態(tài)1-2 回退，識別“234”：狀態(tài)轉(zhuǎn)換圖（舉例）2.1 詞法分析器的設計方法 標識符無符號整數(shù)無符號數(shù)字圖2-4(a) 含分支的狀態(tài)i2.1 詞法分析器的設計方法 圖2-4(b) 含回路的狀態(tài)i：狀態(tài)轉(zhuǎn)換圖（編程）含分支的狀態(tài)對應一個switch()語句或?qū)唤Mif-else語句含回路的狀態(tài)對應一個while語句終態(tài)對應一個return()語句意味著從

7、詞法分析器返回到調(diào)用段，一般指返回到語法分析器第二章第二章 詞法分析詞法分析2.1 詞法分析的設計方法2.2 一個簡單的詞法分析器2.3 正規(guī)表達式與有限自動機簡介2.4 正規(guī)表達式到有限自動機的構造2.5 詞法分析器的自動生成2.2 一個簡單的詞法分析器示例 大多數(shù)程序語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別構造一個C語言子集的詞法分析器：定義C語言子集的單詞符號及內(nèi)碼值C語言子集對應的狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖的代碼實現(xiàn)：C語言子集的單詞符號表示使用種別編碼不利于記憶，故使用助記符和種別編碼對應2.2 一個簡單的詞法分析器示例 ：C語言子集的單詞符號表示2.2 一個簡單的詞法分析器示例 ：C語言

8、子集對應的狀態(tài)轉(zhuǎn)換圖對輸出程序串預處理在設計的狀態(tài)轉(zhuǎn)換圖中，首先對輸入串做預處理，即剔除多余的空白符(在實際的詞法分析中，預處理還包括剔除注釋和制表換行符等編輯性字符的工作)，使詞法分析工作既簡單又清晰。將保留字作為一類特殊的標識符來處理即對保留字不專設對應的狀態(tài)轉(zhuǎn)換圖，當轉(zhuǎn)換圖識別出一個標識符時就去查對表的前五項，確定它是否為一個保留字。當然，也可以專設一個保留字表來進行處理。2.2 一個簡單的詞法分析器示例 圖2-5 簡單詞法分析的狀態(tài)轉(zhuǎn)換圖返回（id，id在符號表中的位置）或返回（保留字，）返回（num，num在常數(shù)表中的位置）* *字母字母非字母與數(shù)字非字母與數(shù)字字母或數(shù)字字母或數(shù)字*

9、 *空白空白數(shù)字數(shù)字數(shù)字數(shù)字非數(shù)字非數(shù)字* * *其它其它；（其他其他返回（+，）返回（=，）返回（relop，EQ）返回（;）返回（）非法字符錯21：C語言子集對應的狀態(tài)轉(zhuǎn)換圖特別注意：狀態(tài)2在識別標識符和保留字時：1、先看識別出的單詞是否是保留字，否則是標識符2、如果是標識符，查符號表中是否已有，如果表中沒有此標識符，將此標識符登錄到符號表中，并返回（id,id在符號表中的位置/入口指針）；若表中已有此標識符，給出重名錯誤信息。2.2 一個簡單的詞法分析器示例 ：狀態(tài)轉(zhuǎn)換圖的實現(xiàn)實現(xiàn)方法：讓每個狀態(tài)對應一小段程序含分支多的狀態(tài)對應switch()語句，分支少的對應if-else含回路的狀態(tài)

10、對應一個while語句注意：結合圖2-5，讀懂課本P14-P16的代碼character:單個字符，token:單詞符號的字符串getbe()和getchar()的使用區(qū)別reserve():如果token保存的是保留字，則返回編碼（1-5），否則返回0retract()：掃描指針回退一個字符，同時將character置空2.2 一個簡單的詞法分析器示例 第二章第二章 詞法分析詞法分析2.1 詞法分析的設計方法2.2 一個簡單的詞法分析器2.3 正規(guī)表達式與有限自動機簡介2.4 正規(guī)表達式到有限自動機的構造2.5 詞法分析器的自動生成：正規(guī)表達式與正規(guī)集（定義和運算）狀態(tài)轉(zhuǎn)換圖可以構造詞法分析

11、程序，但屬于非形式化描述正規(guī)表達式（簡稱正規(guī)式）是詞法分析的形式化表示方法所謂形式化的方法，是指用一整套帶有嚴格規(guī)定的符號體系來描述問題的方法，優(yōu)點：更加清晰和準確例如：形式化表示標識符，即標識符的正規(guī)式：這里，字母字符用letter表示,數(shù)字字符用digit表示letter與(letter | digit)*的并置表示連接括號中的“ | ”表示letter或digit兩者選一“*”表示零次或多次引用，長度為0,1,2,2.3 正規(guī)表達式與優(yōu)先自動機簡介 letter(letter | digit)*能夠表示的單詞集合稱為正規(guī)集：正規(guī)表達式與正規(guī)集（相關基礎概念）1.字母表：語言元素的非空有窮

12、集合，通常用表示例如： =a,b,c是字母表，它由a,b,c三個元素組成注意：字母表中至少包含一個元素，任何語言的字母表規(guī)定了該語言中允許出現(xiàn)的一切符號。如英文的字母表是26個字母、數(shù)字和標點符號的集合；C語言的字母表是由字母、數(shù)字和若干專用符號組成。2.符號：字母表中的每一個元素，也叫字符2.3 正規(guī)表達式與優(yōu)先自動機簡介：正規(guī)表達式與正規(guī)集（相關基礎概念）3.符號串：由符號組成的有窮序列（可以是0個），也叫字如=a,b，則,a,b,aa,ab,aaa,bbb,都是字4.空字：長度為0的字，用表示5.字的全體：所有字組成的集合，用“ *”表示例如：如果=a,b則 * =，a，b，aa，ab，

13、ba，bb，aaa，6.空語言：不含任何字的語言 ，用表示2.3 正規(guī)表達式與優(yōu)先自動機簡介注意區(qū)分、 和： 是空字，是語言字的集合中的一個元素, 不包含任何字，屬于集合的概念 由空字組成的集合，這個集合比 多一個元素不是的元素：正規(guī)表達式與正規(guī)集（遞歸定義）對于給定的字母表，正規(guī)式和正規(guī)集定義為：(1) 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和。(2) 對于任一個符號a，a是上的一個正規(guī)式，它所表示的正規(guī)集為a。2.3 正規(guī)表達式與優(yōu)先自動機簡介這兩條規(guī)則稱為基礎規(guī)則第二條：從普通的符號產(chǎn)生對應的正規(guī)式和正規(guī)集(3) 如果R和S是上的正規(guī)式，它們所表示的正規(guī)集分別為L(R)和L(S)，則

14、： R|S是上的正規(guī)式，它所表示的正規(guī)集為L(R)L(S)； RS是上的正規(guī)式，它所表示的正規(guī)集為L(R)L(S)； (R) * 是上的正規(guī)式，它所表示的正規(guī)集為(L(R) * ； 2.3 正規(guī)表達式與優(yōu)先自動機簡介第三條規(guī)則稱為歸納規(guī)則根據(jù)已有的正規(guī)式和正規(guī)集生成其它正規(guī)式和正規(guī)集可以看出，歸納規(guī)則中有三種運算： “|” 為或運算 “”為連接運算，通常可省略 “* ”為閉包運算(4)僅由有限次使用規(guī)則(1)(3)得到的表達式是上的正規(guī)式，它所表示的集合是上的正規(guī)集 2.3 正規(guī)表達式與優(yōu)先自動機簡介第四條規(guī)則稱為界限規(guī)則或者終止規(guī)則根據(jù)已有的正規(guī)式和正規(guī)集生成其它正規(guī)式和正規(guī)集注意： 在后面

15、的正規(guī)式中，約定：不做特殊說明情況下，大寫字母（如R、S等）對應字的集合：正規(guī)表達式與正規(guī)集（正規(guī)式的運算）連接運算：字的連接：設“ab”和“aab”是兩個字，則 abaab = abaab正規(guī)式的連接：RS= | R&S 例：A=ab，bc ,B=ac,cb ,則： AB =abac,abcb,bcac,bccb正規(guī)式的冪運算：正規(guī)式自身的n次連接并約定： R0 = 。2.3 正規(guī)表達式與優(yōu)先自動機簡介Rn=RRRn個ABBA：正規(guī)表達式與正規(guī)集（正規(guī)式的運算）閉包運算：集合R的閉包表示為R*,具體定義為： R*=R0R1R2R3集合R的正閉包表示為R+,具體定義為： R+ =R1R

16、2R3 = RR* 顯然： R*= R0R+ 2.3 正規(guī)表達式與優(yōu)先自動機簡介：正規(guī)表達式與正規(guī)集（正規(guī)式的運算性質(zhì)）對于上的正規(guī)式R和S,如果它們的正規(guī)集滿足L(R)=L(S),則稱R和S等價，記為R=S。正規(guī)式的性質(zhì)有：(1)交換律： R | S = S | R(2)結合律： R | (S | T) = (R | S) | T；R(ST) = (RS)T(3)分配律： R(S | T) = RS | RT；(R | S)T=RT | ST(4)同一律： R = R = R2.3 正規(guī)表達式與優(yōu)先自動機簡介2.3 課堂例題例例2.1 令令=a,b，設，設R=a(a | b)* 是是上的正規(guī)

17、上的正規(guī)式，試求其表示的正規(guī)集。式，試求其表示的正規(guī)集。解答 L(R)=L(a(a | b)*)=L(a)L(a | b)*)=L(a)(L(a | b)* =L(a)(L(a)L(b)* =a(ab)*=aa,b* =a, a, b, aa, ab, ba, bb, aaa, =a, aa, ab, aaa, aab, aba, abb, aaaa, 2.3 課堂例題例例2.2 令令=a,b，根據(jù)給出的正規(guī)式，試描述，根據(jù)給出的正規(guī)式，試描述其表示的正規(guī)集。其表示的正規(guī)集。正規(guī)式 正規(guī)集 ba* 上所有的以b為首，并且后跟任意多個a 的字，b, ba,baa,baaa, a(a|b)* 上所有的以a為首的字 (a|b)* (aa|bb) (a|b)* 上所有含有兩個連續(xù)的a或者b的字2.3 課堂例題例例2.3 判斷下述正規(guī)式之間是否等價：判斷下述正規(guī)式之間是否等價：(1) (a | b)*與與a* | b* (2) (ab)*與與a*b* 解答 (1) (a | b)* 對應的正規(guī)集其a、b可任意交替出現(xiàn)，如abbaaaba；而 a* | b* 對應的正規(guī)集只可出現(xiàn)任意個a或者任意個b；因此兩者不等價。 解答 (2) (ab)*對應的正規(guī)集是以任意