第3章 詞法分析

第３章詞法分析

任務(wù)：從左至右逐個字符地對源程序進行掃 描，產(chǎn)生一個個的單詞符號，把作為 字符串的源程序改造成為單詞符號串。內(nèi)容簡介§3.1對于詞法分析器的要求

一．功能和輸出形式二．接口設(shè)計§3.2詞法分析器的設(shè)計

一．輸入和預處理二．單詞符號的識別三．狀態(tài)轉(zhuǎn)換圖及其實現(xiàn)§3.3正規(guī)表達式與有限自動機

一．單詞符號的描述

1.正規(guī)式與正規(guī)集2.正規(guī)文法二．有限自動機

1.DFA2.NFA

3.NFA與DFA的等價4.DFA的化簡

三．正規(guī)式與有限自動機的等價性四．正規(guī)文法與有限自動機的等價性§3.4詞法分析器的自動產(chǎn)生（LEX）2§３.１對于詞法分析器的要求一、功能和輸出形式１、功能：輸入源程序，輸出單詞符號２、單詞符號的分類（１）關(guān)鍵字：由程序語言定義的具有固定意義的標識符，也稱為保留字或基本字。例如：Pascal語言中的begin，end，if，while等。（２）標識符：用來表示各種名字。 例如變量名、數(shù)組名、過程名等。（３）常數(shù)：整型、實型、布爾型、文字型等 例如：100，3.14159，true，‘sample’（４）運算符：+、-、*、/（５）界符：，；（）等3３、輸出的單詞符號形式 二元式：（單詞種別，單詞符號的屬性值）§３.１對于詞法分析器的要求單詞符號的編碼：標識符：一般統(tǒng)歸為一種常數(shù)：常按整型、實型、布爾型等分類關(guān)鍵字：全體視為一種／一字一種運算符：一符一種界符：一符一種通常用“整數(shù)編碼”“單詞符號的特征或特性”4例：考慮下述Ｃ++代碼段：while(i>=j)i--;§３.１對于詞法分析器的要求經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：

<while,-><(,-><id,指向i的符號表項的指針><>=,->

<

id,指向j的符號表項的指針><),-><id,指向i的符號表項的指針><--,-><;,->5§３.１對于詞法分析器的要求二、接口設(shè)計１、詞法分析器作為獨立的一遍

２、詞法分析器作為一個獨立的子程序，但并不一定作為獨立的一遍

語法分析器詞法分析器調(diào)用（取下一個單詞）單詞優(yōu)點：使整個編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化。

詞法分析 字符流 單詞序列（源程序） （輸出在一個中間文件上）6１、預處理：剔掉空白符、跳格符、回車符、換行符、注解部分等.一、輸入、預處理§３.２詞法分析器的設(shè)計

原因：

編輯性字符除了出現(xiàn)在文字常數(shù)中之外，在別處的任何出現(xiàn)都無意義.

注解部分不是程序的必要組成部分，它的作用僅在于改善程序的易讀性和易理解性.

7

每當詞法分析器調(diào)用時，就處理出一串確定長度（如120個字符）的輸入字符，并將其裝進詞法分析器所確定的掃描緩沖區(qū)中。２、預處理子程序§３.２詞法分析器的設(shè)計8

起點指示器搜索指示器掃描緩沖區(qū)的兩個指示器：一個指向當前正在識別的單詞的開始位置（即新 單詞的首字符）

起點指示器一個用于向前搜索以尋找單詞的終點

搜索指示器

圖_源程序輸入緩沖區(qū)的對半互補結(jié)構(gòu)§３.２詞法分析器的設(shè)計9二.單詞符號的識別——超前搜索

1．關(guān)鍵字的識別2．標識符的識別

3．常數(shù)的識別4．算符和界符的識別§３.２詞法分析器的設(shè)計10三、狀態(tài)轉(zhuǎn)換圖及其實現(xiàn)1、狀態(tài)轉(zhuǎn)換圖及其示例

§３.２詞法分析器的設(shè)計例:012

數(shù)字數(shù)字 其它*012

字母或數(shù)字字母 其它*11例:(課本42頁表3.1;43頁圖3.3)§３.２詞法分析器的設(shè)計122、狀態(tài)轉(zhuǎn)換圖的實現(xiàn)實現(xiàn)方法：用程序?qū)崿F(xiàn)，讓每個狀態(tài)結(jié)點對應(yīng)一小段程序。A、變量和過程說明ch 字符變量，存放最新讀進的源程序字符。strToken 字符數(shù)組，存放構(gòu)成單詞符號的字符串。GetChar 子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。④

GetBC 子程序過程，檢查ch中的字符是否為空白。若是，則調(diào)用GetChar直至ch中進入一個非空白字符。⑤Concat 子程序過程，將ch中的字符連接到strToken之后?！欤?２詞法分析器的設(shè)計13IsLetter和IsDigit 布爾函數(shù)過程，它們分別判斷ch中的字符是否為字母和數(shù)字。Reserve 整型函數(shù)過程，對strToken中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值（假定0不是保留字的編碼）。Retract子程序過程，將搜索指示器回調(diào)一個字符位置，將ch置為空白字符。InsertId 整型函數(shù)過程，將strToken中的標識符插入符號表，返回符號表指針。InsertConst整型函數(shù)過程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針?！欤?２詞法分析器的設(shè)計14B、示例圖中結(jié)點i所對應(yīng)的程序段可表示為：GetChar（）;if(IsLetter()){…狀態(tài)j的對應(yīng)程序段…；}elseif(IsDigit()){…狀態(tài)k的對應(yīng)程序段…；}elseif(ch=‘/’){…狀態(tài)l的對應(yīng)程序段…；}else{…錯誤處理…;}圖中結(jié)點i所對應(yīng)的程序段可表示為：GetChar（）;while(IsLetter()orIsDigit())GetChar();…狀態(tài)j的對應(yīng)程序段…lkji字母數(shù)字/ji字母或數(shù)字

其它§３.２詞法分析器的設(shè)計15C、例

課本43頁圖3.3；45--46頁§３.２詞法分析器的設(shè)計16§３.３正規(guī)表達式與有限自動機一、正規(guī)式，正規(guī)集，正規(guī)文法二、確定有限自動機（DFA)三、非確定有限自動機(NFA)四、NFA=>DFA=>化簡五、正規(guī)式有限自動機六、左線性正規(guī)文法有限自動機右線性正規(guī)文法有限自動機17§３.３正規(guī)表達式與有限自動機一、正規(guī)式與正規(guī)集１、遞歸定義正規(guī)式ε，Φa(a∈∑）若U，V是正規(guī)式

U.V,U|V,U*

正規(guī)集{ε}，Φ{a}L(U)，L(V)

L(U)L(V),L(U)∪L(V),(L(U))*

18§３.３正規(guī)表達式與有限自動機例題：Ａ、令∑＝｛ａ，ｂ｝，下面是∑上的正規(guī)式和相應(yīng)的正規(guī)集正規(guī)式

ba* a(a|b)*

(a|b)*(aa|bb)(a|b)*正規(guī)集∑上所有以b為首后跟任意多個a的字∑上所有以a為首的字∑上所有含有兩個相繼的a或兩個相繼的b的字19§３.３正規(guī)表達式與有限自動機正規(guī)式

(A|B)(A|B|0|1)*(0|1)(0|1)*Ｂ、令∑＝｛Ａ，Ｂ，０，１｝，則：一個正規(guī)式的正規(guī)集與之完全等價，只是表達形式不同。正規(guī)集∑上的“標識符”的全體∑上的“數(shù)”的全體20§３.３正規(guī)表達式與有限自動機２、運算

“｜”（或）：表示從各選擇對象中選擇“?”（連接積）：表示“連接”起來“*”（閉包）：任意有限次的自重復連接注：S*=∪Sn={ε}∪S∪SS∪……L(r*)=L(r)*優(yōu)先級：*>

?

>”|”∞n=021§３.３正規(guī)表達式與有限自動機例題：Ａ、L(r|s)

L(rs)L((a|b)c)B、L((a|b)*)={ε,a,b,aa,ab,ba,bb,…}

L(a|(b*))={ε,a,b,bb,bbb,…}C、a|bc*——a|(b(c*))ab|c*d——(ab)|((c*)d)=L(r)∪L(s)={r}∪{s}={r,s}=L(r)L(s)={r}{s}={rs}=L(a|b)L(c)={a,b}{c}={ac,bc}223、等價：若兩個正規(guī)式所表示的正規(guī)集相同，則認 為二者等價。 兩個等價的正規(guī)式Ｕ和Ｖ，記為Ｕ＝Ｖ§３.３正規(guī)表達式與有限自動機例：b(ab)*=(ba)*b(a|b)*=(a*b*)*(a*b*)*=(a|b)*L(a*b*)*=[(L(a))*

(L(b))*]*={ε,a,b,aa,bb,........}*={ε,a,b,ab,...}L(a|b)*={a,b}*={ε,a,b,ab,…}

23４、令Ｕ、Ｖ、Ｗ均為正規(guī)式，則：Ｕ｜Ｖ＝Ｖ｜Ｕ （交換律）Ｕ｜（Ｖ｜Ｗ）＝（Ｕ｜Ｖ）｜Ｗ （結(jié)合律）Ｕ（ＶＷ）＝（ＵＶ）Ｗ （結(jié)合律）

U（V|W）=UV|UW （分配律）（V|W）U=VU|WU

εU=Uε

=UU*=(U|ε)* (U*)*=U*§３.３正規(guī)表達式與有限自動機24例題：Ａ、已知字母表∑={a，b，c}，試求在該字母表上的僅包括一個b的所有串的集合相對應(yīng)的正規(guī)式 §３.３正規(guī)表達式與有限自動機B、已知字母表∑={a，b，c}，若集合是包括了最多一個b的所有串，求其相應(yīng)的正規(guī)式 (a|c)*b(a|c)*(a|c)*(b|ε)(a|c)*25§３.３正規(guī)表達式與有限自動機二、確定有限自動機DFA（DeterministicFiniteAutomata）1、DFAM是一個五元式

M=（S，∑，δ，s0，F(xiàn)）其中：S——有限集，其中的每個元素稱為一個狀態(tài)∑——有窮字母表，其中的每個元素稱為一個輸入字符δ：S×∑S

（即?狀態(tài)s∈S，a∈∑，δ(s,a)唯一的確定下一狀態(tài)）

δ(s,a)=s’:當現(xiàn)行狀態(tài)為s，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)s’

s0∈S，唯一的初態(tài)F?S，是一個終態(tài)集（可空）

s的一個后繼狀態(tài)26§３.３正規(guī)表達式與有限自動機2、DFA的兩種表達方式（1）狀態(tài)轉(zhuǎn)換矩陣例：DFAM=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ為： δ（0，a）=1 δ（0，b）=2 δ（1，a）=3 δ（1，b）=2 δ（2，a）=1 δ（2，b）=3 δ（3，a）=3 δ（3，b）=327則其狀態(tài)轉(zhuǎn)換矩陣為：狀態(tài)ab012132213333§３.３正規(guī)表達式與有限自動機δ（0，a）=1δ（0，b）=2δ（1，a）=3δ（1，b）=2δ（2，a）=1δ（2，b）=3δ（3，a）=3δ（3，b）=328（2）狀態(tài)轉(zhuǎn)換圖§３.３正規(guī)表達式與有限自動機DFAM:

m個狀態(tài)：圖中有

個狀態(tài)結(jié)點; n個輸入符號：每個結(jié)點頂多有

條箭弧射出;

每條箭弧用∑中的一個

（相同/不同)

輸入字符作標記;

整張圖含有

個初態(tài)結(jié)點和若干個 （可為0）終態(tài)結(jié)點.

0132

a a baa，ｂ

b b29例題：構(gòu)造一個DFAM，它接受字母表{a，b，c}上以a或b開始的字符串，或者以c開始但所含的a不多于一個的字符串。

§３.３正規(guī)表達式與有限自動機30§３.３正規(guī)表達式與有限自動機3、識別（讀出/接受）

對于任何∑*中的任何字α，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記符連接成的字等于α，則稱α可為DFAM所識別（接受/讀出）。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字ε可為M所識別/接受。DFAM所能識別的字的全體記為L（M）。若一個DFAM的輸入字母表為∑，則稱M是∑上的一個DFA。31ａａｂｂａａａａｂａａｂａｂａｂａｂａ0132

a a baa，ｂ

b b32§３.３正規(guī)表達式與有限自動機4、定理

∑上的一個字集V?∑*是正規(guī)的，當且僅當存在∑上的DFAM，使得V=L（M）33§３.３正規(guī)表達式與有限自動機三、非確定有限自動機（NFA）1、一個NFA是一個五元式

M=（S，∑，δ，S0，F(xiàn)）其中：S——有限集，其中每個元素稱為一個狀態(tài)∑——有窮字母表，其中的每個元素稱為一個輸入字符δ：S×∑*2S

S的子集

字S0?S，是一個非空初態(tài)集F?S，是一個終態(tài)集（可空）34§３.３正規(guī)表達式與有限自動機三、非確定有限自動機（NFA）DFANFAS∑δ初態(tài)終態(tài)F有限狀態(tài)集字母表S×∑S初態(tài)唯一可為空

同左同左S×∑*2S初態(tài)不一定唯一同左35§３.３正規(guī)表達式與有限自動機2、狀態(tài)轉(zhuǎn)換圖注：含有m個狀態(tài)和n個輸入符號（1）整張圖含有

個狀態(tài)結(jié)點。（2）每個結(jié)點可以射出

條弧，每條弧用

作為輸入字，箭弧上的標記

（允許/不允許）相同。（3）整張圖

至少含有一個初態(tài)結(jié)點以及

若干個（可為0個）終態(tài)結(jié)點。（4）某些結(jié)點既可為初態(tài)結(jié)點也可為終態(tài)結(jié)點?！?中一個字（可以是空字ε）允許36m若干例：q0q111000DFA?NFA?37§３.３正規(guī)表達式與有限自動機3、識別（讀出/接受）

對于∑*中的任何一個α，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的字（忽略那些標記為ε的?。┑扔讦粒瑒t稱α可為NFAM所識別（讀出/接受）。若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的ε通路，則空字

ε可為M所接受。38§３.３正規(guī)表達式與有限自動機4、定理對于每個NFAM，存在一個DFAM’，使得L（M）=L（M’）。即，假設(shè)L是一個NFA接受的正規(guī)集，則存在一個DFA也接受L。39§３.３正規(guī)表達式與有限自動機四、NFA=>DFA(確定化）=>化簡（最少化）401、ε_CLOSURE（I）：I中的每個狀態(tài)∈ε_CLOSURE（I）；若s∈ε_CLOSURE（I），則狀態(tài)s經(jīng)過標記為ε的弧到達的狀態(tài)s’∈ε_CLOSURE（I）。ε_CLOSURE（{x}）={x,5,1}412、Ia=ε_CLOSURE（J）若s∈Is經(jīng)過1條標記為a的弧到達的狀態(tài)s’∈JI={x,5,1}Ia={x,5,1}a=ε_CLOSURE({5,3})={5,3,1}Ib={x,5,1}b=ε_CLOSURE({5,4})={5,4,1}42IIaIb{X,5,1}ε_CLOSURE(初態(tài)）（一）NFA=>DFA{5,3,1}{5,4,1}{5,3,1}{5,4,1}{5,2,3,1,6,Y}{5,4,1}{5,2,3,1,6,Y}{5,3,1}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,2,3,6,1,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,6,1,Y}{5,3,6,1,Y}{5,6,3,1,Y}{5,2,6,4,1,Y}{5,2,6,3,1,Y}{5,6,4,1,Y}§３.３正規(guī)表達式與有限自動機解：（1）構(gòu)造DFA的狀態(tài)轉(zhuǎn)換矩陣

（2）構(gòu)造重新命名后的狀態(tài)轉(zhuǎn)換矩陣DFAM’’ L(M’’)=L(M’)=L(M)Sab0121322143354645646354445（二）DFA的化簡狀態(tài)s和t等價：s和t到達終態(tài)能夠識別相同的字。

461、首先分為非終態(tài)集和終態(tài)集{0,1,2}和{3,4,5,6}2、分別對每個集合進行試探：（1）{0,1,2}a={1,3,1}把集合分為{0,2}和{1}

{0,2}b={2,5}把集合劃分為{0}和{2}

把集合{0,1,2}劃分為{0}、{1}和{2}472、（1）{0}、{1}、{2}、{3,4,5,6}

（2）{3,4,5,6}a={3,6,6,3}

{3,4,5,6}b={4,5,5,4}

集合{3，4，5，6}不必再劃分。3、最終形成的劃分{0}{1}{2}{3,4,5,6}48{0}{1}{2}{3,4,5,6}用一個狀態(tài)代表一個狀態(tài)子集。0132abababa,b49§３.３正規(guī)表達式與有限自動機五、正規(guī)式有限自動機關(guān)系定理定理：

上的NFAM所能識別的語言L(M)可以用

上的正規(guī)式來表示。即：對

上的NFAM，可構(gòu)造一個正規(guī)式

，使得L(

)=L(M)。定理：

上任何正規(guī)式

，存在DFAM使得L(M)=L(

)。即：由正規(guī)式

可以構(gòu)造一個DFAM，使得L(M)＝L(

)。50§３.３正規(guī)表達式與有限自動機五、正規(guī)式有限自動機1、有限自動機=>正規(guī)式1)把狀態(tài)轉(zhuǎn)換圖的概念拓廣，令每條弧上都可以用一個正規(guī)式作標記。2)在M的轉(zhuǎn)換圖上加兩個結(jié)點：x、y。從x用

弧連接到M的所有初態(tài)結(jié)點；從M的終態(tài)結(jié)點用

弧連接到y(tǒng)。這個新的NFA為M’，且L(M)=L(M’)。3)通過引入的3條有限自動機替換規(guī)則逐步消去M’中的所有結(jié)點，直到只剩下x和y為止。這樣，在x至y的弧線上的標記就是

上的正規(guī)式，也就是M接受的正規(guī)式。51§３.３正規(guī)表達式與有限自動機五、正規(guī)式有限自動機1、有限自動機=>正規(guī)式替換規(guī)則:jiAB

jiA|B

jiA*A

Bjkijki? ?

A代之以代之以代之以jiAB52練習1：53練習1：練習2：55練習2：56§３.３正規(guī)表達式與有限自動機五、正規(guī)式有限自動機2、正規(guī)式=>有限自動機57證明過程如下：（1）若正規(guī)式有零個運算符時：正規(guī)式，構(gòu)造NFA為：對應(yīng)正規(guī)式，構(gòu)造NFA為：對應(yīng)正規(guī)式a，構(gòu)造NFA為：

（2）假設(shè)正規(guī)式有k(k>=1)個運算符時結(jié)論成立。（3）則正規(guī)式有k+1(k>=1)個運算符時：xyxy

xya58

R=stR=s*xyN(s)

N(s)N(t)

xyN(s)N(t)

R=s|t59書上例子P5660轉(zhuǎn)換規(guī)則：

1)由正規(guī)式

構(gòu)造一個如下僅有兩個結(jié)點x，y的狀

態(tài)圖。

2)按所引入的3條正規(guī)式分裂規(guī)則分裂

。3)重復步驟2直到每個弧上的標記是

上的一個字符或

為止。4)將所得的NFAM(因為包含

弧)進行確定化就得到DFA。xy

61正規(guī)式分裂規(guī)則12

|

12

2

112

3112

*

2

3

62例、根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*，構(gòu)造DFAM，使之等價。xy(a|b)*(aa|bb)(a|b)*1y(a|b)*(a|b)*

2x(aa|bb)1y

2xaa5

bba|b

6

a|b1y

2xa5

ba

6

abb34ab63練習1：L(R)=(a|b)*abb，構(gòu)造NFA使L(N)=L(R)

練習2：L(R)=a*b*abb，構(gòu)造NFA使L(N)=L(R)

64練習1：L(R)=(a|b)*abb，構(gòu)造NFA使L(N)=L(R)

解：xy

(a|b)*abbx

yabb

abx

yabb

a,b

x

y

ababb65x

(a|b)*abby練習2：L(R)=a*b*abb，構(gòu)造NFA使L(N)=L(R)

解：x

ybab

a

bx

a*b*abby661、右線性正規(guī)文法GR有限自動機2、左線性正規(guī)文法GL

有限自動機3、有限自動機

右線性正規(guī)文法GR4、有限自動機

左線性正規(guī)文法GL§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機67

1、右線性正規(guī)文法GR

有限自動機§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例：GR:S→aAA→bBB→cSABfabcδ(S,a)=Aδ(A,b)=Bδ(B,c)=f68

1、右線性正規(guī)文法GR有限自動機§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機GR(VT,VN,S,P)P:A→aBB→bFA(∑,S,δ,S0,F)字母表∑：VT狀態(tài)集S：VN

∪{f}S0：開始符號S對應(yīng)的狀態(tài)F：{f}δ：δ(A,a)=Bδ(B,b)=f69

GR:A→0|0B|1DB→0D|1CC→0|0B|1DD→0D|1D702、左線性正規(guī)文法GL

有限自動機§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例：GL:S→AcA→BbB→aSABfcbaδ(A,c)=Sδ(B,b)=Aδ(q0,a)=Bq0S71

§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機GL(VT,VN,S,P)P:A→BaB→bFA(∑,S,δ,S0,F)字母表∑：VT狀態(tài)集S：VN

∪{q0}S0：q0F：開始符號S對應(yīng)的狀態(tài)δ：δ(B,a)=Aδ(

q0,b)=B722、左線性正規(guī)文法GL

有限自動機

GL:f→0|C0B→0|C0C→B1D→1|C1|D0|D1|B0733、有限自動機

右線性正規(guī)文法GR§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例1：SABCabc引例2：SABCabcd74

3、有限自動機

右線性正規(guī)文法GR§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例1：SABCabc

GR:S→aAA→bBB→cCC→ε75

3、有限自動機

右線性正規(guī)文法GR§３.３正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機

GR:S→aAA→bBB→cC

C→dB|ε引例2：SABCabcd76

規(guī)則：3、有限自動機

右線性正規(guī)文法GRFA(∑,S,δ,s0,F)δ(A,a)=BGR(VT,VN,S,P)VT：

∑VN：狀態(tài)集S對應(yīng)的符號集S：初態(tài)s0對應(yīng)的符號P：A→aB當C是終態(tài)時，增加：C→ε77

ABDabaabbbC

GR:A→aB|bDB→bCC→aA|bDD→aB|bD|ε784、有限自動機

左線性正規(guī)文法GL§３.３正