第3章-詞法分析

1

詞法分析是編譯的第一個階段，它的主要任務(wù)是從左到右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞序列。詞法分析階段設(shè)計的主要問題是字符串（單詞）的識別問題。具體說，如何判定任意的一個字符串是否為合法字符串(單詞)的問題。第1頁/共68頁2

字符串（單詞）集合可用不同的工具來表示，常見的有：因此，要研究如何從正規(guī)表達式或自動機構(gòu)造出相應(yīng)的單詞識別器的問題。這種識別器在編譯器中稱為詞法分析器。單詞的描述技術(shù)：正規(guī)式。識別機制：有窮自動機（有限自動機）。第2頁/共68頁3

構(gòu)造詞法分析器的前提是給出語言中單詞結(jié)構(gòu)的定義。不同語言的單詞類別和結(jié)構(gòu)不完全相同，因此不同語言的詞法分析器也不盡相同，但是其構(gòu)造原理是類似的。構(gòu)造方法：①有窮自動機(有限自動機)。②正規(guī)式(正規(guī)集)。第3頁/共68頁4本章重點首先需要描述和刻畫程序設(shè)計語言中的原子單位——單詞，其次需要識別單詞和執(zhí)行某些相關(guān)的動作。程序設(shè)計語言的詞法的描述機制是正則表達式，識別機制是有窮狀態(tài)自動機。單詞的描述工具單詞的識別系統(tǒng)第4頁/共68頁5§3.1

有窮自動機第5頁/共68頁6

有窮自動機(也稱有限自動機)作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合。引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。確定的有窮自動機(DeterministicFiniteAutomata)不確定的有窮自動機(NondeterministicFiniteAutomata)第6頁/共68頁7關(guān)于有窮自動機將討論以下問題一、確定的有窮自動機DFA二、不確定的有窮自動機NFA三、具有ε動作的FA四、NFA到DFA的變換第7頁/共68頁8一、確定的有窮

自動機DFA第8頁/共68頁9確定的有窮自動機DFA的定義

一個確定的有窮自動機（DFA）M是一個五元組：M=（Q，Σ，δ，S，Z）其中

1.Q是一個有窮集，它的每個元素稱為一個狀態(tài)；

2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號；第9頁/共68頁103.δ是轉(zhuǎn)換函數(shù)，是在Q×Σ→Q上的單值映射，如δ

（p，a）=q，（p∈Q，q∈Q）意味著，當(dāng)前狀態(tài)為P，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)Q，我們把q稱作p的一個后繼狀態(tài)；4.S∈Q是唯一的一個初態(tài)；5.Z

Q是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。第10頁/共68頁11對定義的解釋所謂自動機不是一臺實際的機器，而是一種數(shù)學(xué)模型，來模擬計算機的識別功能。所謂確定性是指δ

(p,a)→q，q是唯一的。用上述定義中的5條來識別一個序列是否可被機器接收。接收→格式正確第11頁/共68頁12DFA的例子DFAM=（{S，U，V，Q}，{a，b}，δ，S，{Q}）其中δ定義為：δ

（S，a）=U δ

（V，a）=Uδ

（S，b）=V δ

（V，b）=Qδ

（U，a）=Q δ

（Q，a）=Qδ

（U，b）=V δ

（Q，b）=Q以上定義不直觀，DFA有兩種較直觀的表示方法。第12頁/共68頁13DFA的表示方法1（狀態(tài)轉(zhuǎn)換圖）

一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFAM含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)圖含有m個結(jié)點，每個結(jié)點最多有n個弧射出，每條弧用Σ中的一個不同輸入字符作標(biāo)記。整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=>”，終態(tài)結(jié)點用雙圈表示，若δ

(p,a)=q，則從狀態(tài)結(jié)點p到狀態(tài)結(jié)點q畫標(biāo)記為a的弧；第13頁/共68頁14

DFA的狀態(tài)圖表示bSUVQaaaba，bb第14頁/共68頁15DFA的表示方法2（狀態(tài)轉(zhuǎn)換矩陣）

一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即p行a列為δ

(p,a)的值。用雙箭頭“=>”標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。第15頁/共68頁16狀態(tài)轉(zhuǎn)換矩陣表示字符狀態(tài)0001第16頁/共68頁17DFA的識別功能

對于∑*中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標(biāo)記符連接成的字符串等于t，則稱t為DFAM所接受（識別）。

若M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則ε可被識別。第17頁/共68頁1800011110100011100000010001100第18頁/共68頁19

DFAM所能接受的符號串的全體記為L(M)。對于任何兩個有窮自動機M和M′，如果L(M)=L(M′)，則稱M與M′是等價的。DFA的等價第19頁/共68頁20確定性DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)δ:Q×Σ→Q是一個單值函數(shù)，也就是說，對任何狀態(tài)P∈K，和輸入符號a∈Σ，δ(p,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表Σ含有n個輸入字符，那末任何一個狀態(tài)結(jié)點最多有n條弧射出，而且每條弧以一個不同的輸入字符標(biāo)記。第20頁/共68頁21二、非確定的有

窮自動機NFA第21頁/共68頁22不確定的有窮自動機NFA的定義NFAM=Q，，δ

，S，Z，其中Q為狀態(tài)的有窮非空集，（與DFA相同）

為有窮輸入字母表，（與DFA相同）映射δ為Q→Q的多值映射，S∈Q是唯一的一個初態(tài)，（與DFA相同）

ZQ為終止?fàn)顟B(tài)集。（與DFA相同）第22頁/共68頁23NFA的表示方法1（狀態(tài)轉(zhuǎn)換圖）

一個含有m個狀態(tài)和n個輸入字符的NFA可表示成一個狀態(tài)轉(zhuǎn)換圖：這張圖含有m個狀態(tài)結(jié)，每個結(jié)可射出若干條箭弧與別的結(jié)相連接，每條弧用Σ中的一個字符作標(biāo)記，整個圖含有一個初態(tài)結(jié)和若干個終態(tài)結(jié)。第23頁/共68頁24

NFA的識別功能

對于Σ﹡中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串等于t，則稱t可為NFAM所識別(讀出或接受)。

NFAM所能接受的符號串的全體記為L(M)。第24頁/共68頁25三、具有ε動作的FA第25頁/共68頁26

前面在定義NFA和DFA時，對映射的限制是僅當(dāng)FA掃視Σ中的一個字符時，才發(fā)生狀態(tài)的轉(zhuǎn)移。如果弧上允許標(biāo)記ε，即允許FA對ε也作狀態(tài)的轉(zhuǎn)移，則稱此自動機為ε自動機，記為εNFA。第26頁/共68頁27FA中映射δ的擴充映射δ為Q*到Q的子集。

對于Σ﹡中的任何一個串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理睬那些標(biāo)記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。每個弧線用Σ*中的一個字作標(biāo)記（字符串）第27頁/共68頁28

若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為ε，那么空字可為M所接受。第28頁/共68頁29四、NFA到DFA的變換第29頁/共68頁30

在NFA中，由于某些狀態(tài)的轉(zhuǎn)移須從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個NFA對符號串的識別必然是一個試探的過程。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。

子集法——將具有ε動作的NFA轉(zhuǎn)換成接受同樣語言的DFA。第30頁/共68頁31NFA的確定化（子集法）

所謂確定化是指NFA→DFA的等價轉(zhuǎn)化，用子集法來進行確定化。

為此，首先定義一個狀態(tài)集合I的ε—閉包的概念。第31頁/共68頁32狀態(tài)集合I的幾個有關(guān)運算1.狀態(tài)集合I的ε-閉包表示為ε-closure(I)，其中I是NFA的狀態(tài)集的一個子集。①若s∈I，則s∈ε-closure(I)。狀態(tài)集合I的任何狀態(tài)s都屬于ε-closure(I)。②若s∈I，那么從s出發(fā)經(jīng)任意條ε弧而能到達的任何狀態(tài)都屬于ε-closure(I)。第32頁/共68頁332.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，即J=move(I,a)。其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。

Ia=ε-closure(J)第33頁/共68頁34狀態(tài)集合I的有關(guān)運算的例子I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；J=move({1,2},a)=Ia=-closure({5,3,4})=12534687aa

a{5,3,4}{2,3,4,5,6,7,8}；第34頁/共68頁35NFA確定化的步驟設(shè)∑＝{a,b},則NFA的確定化步驟如下：1、造一張表，包含三列，第一列為I，余下的兩列為Ia，Ib。2、置首行首列為ε_closure{S}。3、若某行首列對應(yīng)子集已確定，則計算Ia，以及Ib；新出現(xiàn)狀態(tài)子集加入下行首列。4、重復(fù)3，直至狀態(tài)子集收斂。5、狀態(tài)子集重新命名。第35頁/共68頁364Y35621X

aaaabbbb第36頁/共68頁37

等價的DFAa34215F0baaaaabbbbbab6第37頁/共68頁38§3.2

正規(guī)集、正規(guī)文法和正規(guī)式第38頁/共68頁39本節(jié)將討論以下問題一、正規(guī)式與正規(guī)集二、正規(guī)集與正規(guī)文法三、正規(guī)文法和正規(guī)式第39頁/共68頁40一、正規(guī)式與

正規(guī)集

第40頁/共68頁41正規(guī)式

正規(guī)式也稱正則表達式,正規(guī)表達式（regularexpression）是說明單詞的模式的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號。程序設(shè)計語言的單詞都能用正規(guī)式來定義。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。第41頁/共68頁42設(shè)字母表為：

和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和{}；

任何a

，a是上的一個正規(guī)式，它所表示的正規(guī)集為{a}；

假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。

僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。第42頁/共68頁43正規(guī)式中的符號在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“

”、“

”、“”。連接符“

”一般可省略不寫。“

”、“

”和“”都是左結(jié)合的。“”讀為“或”；“

”讀為“連接”；“

”讀為“閉包”(任意有限次的自重復(fù)連接)。第43頁/共68頁44令

={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集有：

正規(guī)式 正規(guī)集

a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a{,a,a,……任意個a的串}第44頁/共68頁45

正規(guī)式 正規(guī)集

(ab)

{,a,b,aa,ab……所有由a和b組成的串}(ab)

(aabb)(ab)

{

上所有含有兩個相繼的a或兩個相繼的b組成的串}ba

{b,ba,baa,baaa,baaaa,……}第45頁/共68頁46兩個正規(guī)式等價

若兩個正規(guī)式e1和e2所表示的正規(guī)集相同，則說e1和e2等價，寫做e1=e2。e1=(ab)e2=bae1=b(ab)

e2=(ba)

be1=(ab)

e2=(a

b

)

第46頁/共68頁47性質(zhì)rs=sr “或”服從交換律

r(st)=(rs)t“或”的可結(jié)合律

(rs)t=r(st) “連接”的可結(jié)合律

r(st)=rsrt (st)r=srtr 分配律

εr=rrε=r設(shè)r,s,t為正規(guī)式：第47頁/共68頁48二、正規(guī)集與

正規(guī)文法第48頁/共68頁49

正規(guī)文法是描述正規(guī)集的文法，它可以用來描述高級語言的詞法部分。在寫正規(guī)集的文法時，要特別注意所給出的產(chǎn)生式形式必須滿足正規(guī)文法的限制。第49頁/共68頁50三、正規(guī)文法

和正規(guī)式第50頁/共68頁51

正規(guī)式與正規(guī)文法都用來描述程序語言的詞法結(jié)構(gòu)，它們有著相同的表達能力。對于任意一個正規(guī)文法，存在一個定義同一個語言的正規(guī)式；反之，對每個正規(guī)式，都存在一個生成同一語言的正規(guī)文法。第51頁/共68頁52正規(guī)文法→正規(guī)式

首先求出正規(guī)文法G的各個產(chǎn)生式對應(yīng)的正規(guī)式方程式，獲得一個聯(lián)立方程組。這些方程式中的變元是文法G中的非終結(jié)符，各變元的系數(shù)是正規(guī)式。然后求解這個正規(guī)式方程組，最后得到一個關(guān)于開始符號S的解：

S=w，w∈VT*

解正規(guī)式方程組的基本方法是用代入法逐個替換方程式右部的各非終結(jié)符，最后可得到關(guān)于開始符號S的解。第52頁/共68頁53§3.4

正規(guī)式與NFA第53頁/共68頁54正規(guī)式與FA在描述語言上的等價性對于一個在輸入字母表Σ上的NFAM，一定能夠構(gòu)造一個Σ上的正規(guī)式e，使得L(e)=L(M)。對于一個在輸入字母表Σ上的每一個正規(guī)式e，一定能夠構(gòu)造一個Σ上的NFAM，使得L(M)=L(e)。第54頁/共68頁55正規(guī)式→NFA的方法1.由e構(gòu)造NFAM

把正規(guī)式e表示成拓廣轉(zhuǎn)換圖，XYe然后通過對e進行分裂和加進新結(jié)的方法，逐步把這個圖轉(zhuǎn)變?yōu)椋好織l弧的標(biāo)記為Σ的一個字符或ε。轉(zhuǎn)換規(guī)則如下：第55頁/共68頁56轉(zhuǎn)換規(guī)則szR1R2AsR1zR2szR1|R2zsR1R2szR*s

z

RA第56頁/共68頁571（0|1）*1011（0|1）*101XY1X21Y（0|1）*134101X21Y134105εε01第57頁/共68頁58（a|b)*(aa|bb)(a|b)*XY（a|b)*X21Y（aa|bb)（a|b)*正規(guī)式（a|b)*(aa|bb)(a|b)*第58頁/共68頁594Y35621X

aaaabbbbX4213Yεεεεaabba|ba|b第59頁/共68頁60§3.5

DFA的化簡第60頁/共68頁61

對于一個NFA，當(dāng)把它確定化之后，得到的DFA所具有的狀態(tài)數(shù)可能并不是最小的。所以，DFA的化簡，是指狀態(tài)數(shù)的最小化。定理：對于有同一接受集的FA，與之等價且有最小狀態(tài)數(shù)的DFA在同構(gòu)意義下（即不顧狀態(tài)的命名）是唯一的。第61頁/共68頁62

等價狀態(tài)和可區(qū)分狀態(tài)兩個狀態(tài)s和t等價：滿足兼容性——同是終態(tài)或同是非終態(tài)傳播性——從s出發(fā)讀入某個aa和從t出發(fā)讀入某個a到達的狀態(tài)等價。第62頁/共68頁63等價狀態(tài)的舉例aCDBAEFSbaaaaabbbbbabC和F同是終態(tài)：

讀入a都到達C，讀入b都到達E。