1

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

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

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

有窮自動(dòng)機(jī)第5頁(yè)/共68頁(yè)6

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

自動(dòng)機(jī)DFA第8頁(yè)/共68頁(yè)9確定的有窮自動(dòng)機(jī)DFA的定義

一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（Q，Σ，δ，S，Z）其中

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

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

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

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

(p,a)→q，q是唯一的。用上述定義中的5條來(lái)識(shí)別一個(gè)序列是否可被機(jī)器接收。接收→格式正確第11頁(yè)/共68頁(yè)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頁(yè)/共68頁(yè)13DFA的表示方法1（狀態(tài)轉(zhuǎn)換圖）

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

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

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

一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新?tīng)顟B(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頁(yè)/共68頁(yè)16狀態(tài)轉(zhuǎn)換矩陣表示字符狀態(tài)0001第16頁(yè)/共68頁(yè)17DFA的識(shí)別功能

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

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

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

窮自動(dòng)機(jī)NFA第21頁(yè)/共68頁(yè)22不確定的有窮自動(dòng)機(jī)NFA的定義NFAM=Q，，δ

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

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

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

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

NFA的識(shí)別功能

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

NFAM所能接受的符號(hào)串的全體記為L(zhǎng)(M)。第24頁(yè)/共68頁(yè)25三、具有ε動(dòng)作的FA第25頁(yè)/共68頁(yè)26

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

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

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

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

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

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

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

Ia=ε-closure(J)第33頁(yè)/共68頁(yè)34狀態(tài)集合I的有關(guān)運(yù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頁(yè)/共68頁(yè)35NFA確定化的步驟設(shè)∑＝{a,b},則NFA的確定化步驟如下：1、造一張表，包含三列，第一列為I，余下的兩列為Ia，Ib。2、置首行首列為ε_(tái)closure{S}。3、若某行首列對(duì)應(yīng)子集已確定，則計(jì)算Ia，以及Ib；新出現(xiàn)狀態(tài)子集加入下行首列。4、重復(fù)3，直至狀態(tài)子集收斂。5、狀態(tài)子集重新命名。第35頁(yè)/共68頁(yè)364Y35621X

aaaabbbb第36頁(yè)/共68頁(yè)37

等價(jià)的DFAa34215F0baaaaabbbbbab6第37頁(yè)/共68頁(yè)38§3.2

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

正規(guī)集

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

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

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

任何a

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

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

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

”、“

”、“”。連接符“

”一般可省略不寫(xiě)。“

”、“

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

”讀為“連接”；“

”讀為“閉包”(任意有限次的自重復(fù)連接)。第43頁(yè)/共68頁(yè)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,……任意個(gè)a的串}第44頁(yè)/共68頁(yè)45

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

(ab)

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

(aabb)(ab)

{

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

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

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

e2=(ba)

be1=(ab)

e2=(a

b

)

第46頁(yè)/共68頁(yè)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頁(yè)/共68頁(yè)48二、正規(guī)集與

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

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

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

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

首先求出正規(guī)文法G的各個(gè)產(chǎn)生式對(duì)應(yīng)的正規(guī)式方程式，獲得一個(gè)聯(lián)立方程組。這些方程式中的變?cè)俏姆℅中的非終結(jié)符，各變?cè)南禂?shù)是正規(guī)式。然后求解這個(gè)正規(guī)式方程組，最后得到一個(gè)關(guān)于開(kāi)始符號(hào)S的解：

S=w，w∈VT*

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

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

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

z

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

aaaabbbbX4213Yεεεεaabba|ba|b第59頁(yè)/共68頁(yè)60§3.5

DFA的化簡(jiǎn)第60頁(yè)/共68頁(yè)61

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

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

讀入a都到達(dá)C，讀入b都到達(dá)E。