第四章詞法分析

1、第四章詞法分析本章將討論詞法分析程序的設(shè)計(jì)原則，單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析程序的自動(dòng)構(gòu)造 原理。4.2正規(guī)表達(dá)式與正規(guī)集(正規(guī)語(yǔ)言)4.3有窮自動(dòng)機(jī)4.4正規(guī)式和有窮0動(dòng)機(jī)的等價(jià)性4. 5正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換本章重點(diǎn)4.1詞法分析程序1. 回顧什麼是詞法分析程序?qū)崿F(xiàn)詞法分析(lexical analysis)的程序一逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的 最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在一起 作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單同

2、供語(yǔ)法分析使用。2. 常常遇到的術(shù)語(yǔ)token單詞,詞標(biāo)，符號(hào)lexeme詞素，詞位pattern模式，式樣3. 詞法分析工作從語(yǔ)法分析工作獨(dú)立出來(lái)的原因：簡(jiǎn)化設(shè)計(jì)改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性4. 2正規(guī)表達(dá)式與正規(guī)集(正規(guī)語(yǔ)言)程序設(shè)計(jì)語(yǔ)言中的單詞是基本語(yǔ)法成分.單詞符號(hào)的語(yǔ)法可以用有效的工具加以描述，并且 基于這類描述工具，實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造.一.正規(guī)式也稱正則表達(dá)式，正規(guī)表達(dá)式(regular expression)是說(shuō)明單fej的模式(pattern) 的一種重要的表示法(記號(hào))，是定義正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號(hào)。下面是 正規(guī)式和它所表示的正規(guī)集的遞歸定義。1

3、. 定義(正規(guī)式和它所表示的正規(guī)集)：設(shè)字母表為2：,輔助字母表=, e , i，*,(，)。1。s和0都是z上的正規(guī)式，它們所表示的正規(guī)集分別為w和 ;2。任何ae 2： , a是2：上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a;3。假定e:和都是e上的正規(guī)式，它們所表示的正規(guī)集分別為l(ei)和l(e2),那么， (ej, ej e2, ei*e2, e/也都是正規(guī)式，它們所表示的正規(guī)集分別為l(ej, l(ei)ul(e2), l(e,)l(e2)和(l(ei)* o4。僅由有限次使用上述三步驟而定義的表達(dá)式才是z上的正規(guī)式，僅由這些正規(guī)式所表 示的集合才是s上的正規(guī)集。2. 正規(guī)式中的符號(hào)規(guī)定

4、兌符的優(yōu)先順序?yàn)椤? ”、“ ”、 “i ” 。連接符“* ”一般可省略不寫?！啊焙汀皘 ”都是左結(jié)合的。3. 例子令b, s上的正規(guī)式和相應(yīng)的正規(guī)集的例子宥：正規(guī)式正規(guī)集aaa | ba, babab(a | b) (a | b)aa, ab, ba, bba *e , a, a,任意個(gè)a的串(a|b)*e , a, b, aa, ab 所有由a和b組成的串(a|b)*(aa|bb) (a|b)*z*上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串4. 等價(jià)：若兩個(gè)正規(guī)式e,和所表示的正規(guī)集相同，則說(shuō)&和等價(jià)，寫作ei=e2。5. 設(shè)r，s，t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：(1) .

5、 r|s=s | r“或”服從交換律(2) . r| (s|t) = (r|s) |t“或”的可結(jié)合律(3) . (rs)t=r(st)連接”的可結(jié)合律.r (s | t):rs | rt(s | t)r=sr | tr分配禪(5) . er=r, re=re是“連接”的恒等兀素岑 律(6) . r|r=r|r|rr|或”的抽取律二、正規(guī)文法和正規(guī)式的等價(jià)性1、將2上的正規(guī)式轉(zhuǎn)換成正規(guī)文法vt = 2對(duì)任何正規(guī)式r,選擇一個(gè)非終結(jié)符s生成產(chǎn)生式s-r，將s為g的開(kāi)始符號(hào)。若x和y都是正規(guī)式，對(duì)a-xy,重寫成：a-xb, b->y;對(duì)形如a->x|y，重寫成：a-x, a-y;對(duì)形

6、如a-x* y,重寫成：a->xa a-y;不斷使用如上規(guī)則，直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止 例如：將r=a(a|d) *轉(zhuǎn)換成正規(guī)文法s-> a(a|d) *將s是文法的開(kāi)始符號(hào)。根據(jù)規(guī)則1形成s->aa, a-(a|d) *根據(jù)規(guī)則3,對(duì)第二條重寫成a-(a|d) a, a->e 最后得出正規(guī)文法為：s-aa, a->aa, a->da, a-> e2、正規(guī)文法轉(zhuǎn)換成正規(guī)式根據(jù)正規(guī)文法寫出聯(lián)立方程組：寫法：_>改為=,將左部相同的寫入一個(gè)方程，為方程的左部，所有右部用+連接 例如:文法 gs為:s->aa, s->a, a-

7、> aa, a-da, a-a, a-d方程組為：s=aa+aa=aa+da+a+d對(duì)方程組求解，開(kāi)始符號(hào)的解即力正規(guī)式定理：形如：a=ra+t的方程的解為：a=r*t4. 3有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文 法所定義的語(yǔ)言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的 自動(dòng)構(gòu)造尋找特殊的方法和工具。有窮自動(dòng)機(jī)分為兩類:確定的有窮自動(dòng)機(jī)(deterministic finite automata)和不確定的有 窮自動(dòng)機(jī)(nondeterministic finite automata)。一.確定的有窮自動(dòng)機(jī)df

8、a(一) .dfa定義:-個(gè)確定的有窮自動(dòng)機(jī)(dfa) 是一個(gè)五元組：m= (k，2，f，s，z)其中1. k是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. s是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱2為輸入符號(hào)表；3. f是轉(zhuǎn)換函數(shù)，是在kx2k上的映射，即，如f (ki, a) =kj, (kigk, kjek)就意味著，當(dāng)前狀態(tài)為ki，輸入符力a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4. sgk是唯一的一個(gè)初態(tài)；5. zc k是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。 一個(gè)dfa的例子：dfa m= (s, u, v, q, a, b, f, s,

9、 q)其中f定義為: f (s, a) =uf (v, a) =uf (s,b)=vf(v，b)=qf (u,a)-qf(q,a)=qf (u,b)=vf(q,b)=q表示：一個(gè)dfa可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。一個(gè)dfa還可以用一個(gè)矩陣表示(二) dfa m所能接受的符號(hào)串的全體記為l(m).(三) 對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)m和,如果l(m)=l(m,),貝lj稱m與m'是等價(jià)的.結(jié)論：z上一個(gè)符號(hào)串集是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)s上的確定有窮自動(dòng)機(jī)m,使得 v=l (m)。dfa的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:kxsk是一個(gè)單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)kek,和輸 入符號(hào)ags

10、, f(k, a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來(lái)看，若字母表2含有n個(gè)輸 入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。二.不確定的有窮自動(dòng)機(jī)nfa1. 定義nfa m=k, z，f, s, zh 其中f 為：kx zu e ->2"上的映射例子nfa m= (s, p, z, 0, 1, f, s, p, z) 其中、 ,di 1j 1j 1j , p z p sfl fl n flii ii ii iio jz lz )z )z2.nfa m所能接受的符號(hào)中的全體記為 l (m)結(jié)論.u z上一個(gè)符號(hào)串集是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)

11、s上的不確定的有窮自動(dòng)機(jī)m, 使得 v=l(m)。三：nfa確定化：假設(shè)nfa n=(k, ,1(0,10按如下辦法構(gòu)造一個(gè)01 m=(s, z, d, so, st),使得l(m)=l(n): (1). m的狀態(tài)集s由k的一些子集組成。用s： s2. sj表示s的元素，其中sb s2. sjsk的狀態(tài)。m和n的輸入字母表是相同的，即是z ;轉(zhuǎn)換函數(shù)是這樣定義的:d(s, s2,. sj,a)= r1r2. rt其中rlr2.rt= e-closure (move (si, s2.，s；, a)so=e-closure(k。)為m的開(kāi)始狀態(tài)；(5) st=si sk. s j,其中si sk.

12、 sjes 且s：，sk.,. senk,(d定義對(duì)狀態(tài)集合i的兒個(gè)有關(guān)運(yùn)算：狀態(tài)集合i的閉包，表示為e-closure(i)，定義力一狀態(tài)集，是狀態(tài)集i中的任何狀態(tài)s經(jīng)任意條e弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合i的任何狀態(tài)s都屬于e -closure（i） o狀態(tài)集合i的a弧轉(zhuǎn)換，表示為moved, a）定義為狀態(tài)集合j，其中j是所有那些可從1屮的某一 狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。構(gòu)造nfa n的狀態(tài)k的子集的算法：假定所構(gòu)造的子集族為c,即c= （1，t2.,. tj,其中l(wèi), t2.，. l為狀態(tài)k的子集。開(kāi)始，令e-closure（k。）為c中唯一成員，并且它是未被標(biāo)記的。whi

13、le （c中存在尚未被標(biāo)記的子集t） do 標(biāo)記t; for每個(gè)輸入字母ado u:= e-closure（move（t, a）；if u不在c屮 then將u作為未標(biāo)記的子集加在c中l(wèi)alb1,2,31,2.41，2,41,2,3l，2,4,5,6，f l，2,4,6，fl，2,4,5,6，fl，2,4,5,6，fl，2,4,6，fl，2,4,5,6，f等價(jià)的dfa四.確定有窮自動(dòng)機(jī)的化簡(jiǎn)1、最小狀態(tài)dfa的含義：沒(méi)有多余狀態(tài)（死狀態(tài)）沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）2、兩個(gè)狀態(tài)s和t不可區(qū)別：滿足 兼容性一一同是終態(tài)或同是非終態(tài)傳播性一一從s出發(fā)讀入某個(gè)a（aes）和從t出發(fā)讀入某個(gè)a到

14、達(dá)的狀態(tài)等價(jià)。3、“分割法，dfa的最算法的核心把一個(gè)dfa的狀態(tài)分成一些不ffl交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同 一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.dfa的最小化算法dea m = (k, s,f, k,., kt人最小狀態(tài)dp'a m1. 構(gòu)造狀態(tài)的初始劃分：終態(tài)k,.和非終態(tài)k- k,兩組(group)2. 尋找子集屮不等價(jià)狀態(tài)進(jìn)行細(xì)化，重復(fù)執(zhí)行直到不能細(xì)化為止 例：最小化：1. 將m的狀態(tài)分成非終態(tài)和終態(tài)集 s,a,b c,d,e,f2. 尋找子集中不等價(jià)狀態(tài) s,a, b->as, b->a s bc, d, e, f4. 4有窮自動(dòng)機(jī)和正規(guī)

15、表達(dá)式的等價(jià)性性，即：1. 對(duì)于e上的一個(gè)nfa m,可以構(gòu)造一個(gè)e上的正規(guī)式r,使得l(r)=l(1)。第一步，在m的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個(gè)結(jié)點(diǎn)，一個(gè)為x結(jié)點(diǎn)，一個(gè)為y結(jié)點(diǎn)，從x結(jié)點(diǎn)用e弧 連接到m的所有初態(tài)結(jié)點(diǎn)，從m的所有終態(tài)結(jié)點(diǎn)用弧連接到y(tǒng)結(jié)點(diǎn)，形成一個(gè)與m等價(jià)的 m'，m'只有一個(gè)初態(tài)和一個(gè)終態(tài).第二步，逐步消去m'中的所有結(jié)點(diǎn)，直至只剩下x和y結(jié)點(diǎn)最后x和y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式。2. 對(duì)于e上的一個(gè)正規(guī)式r,可以構(gòu)造一個(gè)z上的nfa m，使的l(m)=l(r)。1)從小到大進(jìn)行構(gòu)造：例：2)從大到小進(jìn)行構(gòu)造:例：r= (a | b) *ab 構(gòu)造為nfa na|babr= (a|bf 構(gòu)造為 nfa n解：從左到右分解r,令r1=a，則有令 r2=b，則有 )0.令r3=a|b，則有c4.5正規(guī)文法和宥窮自動(dòng)機(jī)間的轉(zhuǎn)換1、從正規(guī)文法構(gòu)造nfa m字母表與g的終結(jié)符集相同。為g的每個(gè)非終結(jié)符生成m的一個(gè)狀態(tài)，g的開(kāi)始符號(hào)s是初態(tài)增加一個(gè)新?tīng)顟B(tài)z,作為nfa的終態(tài)。對(duì)g中的形如a-tb的產(chǎn)生式，其中t為終結(jié)符或e, a和b為非終結(jié)符，構(gòu)造m的一個(gè)轉(zhuǎn)換函數(shù)f(a, t)=b;g中的形如a-t的產(chǎn)生式,構(gòu)造m的一個(gè)轉(zhuǎn)換函數(shù)f (a, t)=z;口*3 o例如：求文法gs等價(jià)的n