第三章詞法分析

詞法分析的作用：逐個讀入源程序字符并按照構(gòu)詞規(guī)則分成一系列單詞。單詞中包括保留字、標(biāo)識符、運(yùn)算符、標(biāo)點(diǎn)符號和常量等。詞法分析是編譯過程中的一個階段。前面我們講過，詞法分析采用正規(guī)文法來定義和識別詞法分析程序的功能根據(jù)詞法規(guī)則把源程序字符流轉(zhuǎn)換為語義關(guān)聯(lián)的單詞符號的序列，同時進(jìn)行詞法檢查對數(shù)字常數(shù)完成數(shù)字字符串到（二進(jìn)制）數(shù)值的轉(zhuǎn)換刪去空格字符和注解第三章詞法分析及詞法分析程序源程序詞法分析程序語法分析程序Tokengettoken….1.詞法分析單獨(dú)作為一遍2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn):結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低詞法分析實(shí)現(xiàn)方案：基本上有兩種Whilei<>jdoifi>jtheni:=i-jelsej:=j-I

‘while’，‘i’，‘<>’，‘j’，‘do’，‘if’，‘i’，‘>’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'詞法分析器

Pascal程序段詞類和屬性

computern.Calculatingmachine.一般程序語言單詞的分類：

1．關(guān)鍵字(保留字或基本字)：begin,end2．標(biāo)識符：用來表示各種名字3．常量：256，3.14，true,‘a(chǎn)bs’4．運(yùn)算符：如，＋、－、*、/等等5．分界符：如逗號，分號，冒號等單詞的詞類和屬性詞法分析器的二元式輸出形式—：（詞類編碼，單詞自身的屬性值）詞類編碼提供給語法分析程序使用單詞自身的屬性值提供給語義分析程序使用具體的分類設(shè)計以方便語法分析程序使用為原則單詞自身的屬性值提供的內(nèi)容，是由詞法分析和語義分析的任務(wù)劃分決定的單詞的詞類和屬性Pascal源程序經(jīng)詞法分析器的輸出〈while，——〉〈id，指向i的符號表入口的指針〉〈relational－op,NE〉〈id，指向j的符號表入口的指針〉〈do，——〉〈if，——〉〈id，指向i的符號表入口的指針〉

〈id，指向j的符號表入口的指針〉Whilei<>jdo程序段的單詞輸出例子：3.2正規(guī)文法和狀態(tài)轉(zhuǎn)換圖正規(guī)文法定義了3型語言，常見的單詞可由正規(guī)文法定義。狀態(tài)轉(zhuǎn)換圖可用于識別3型語言；它是設(shè)計和實(shí)現(xiàn)掃描器的一種有效工具，是有限自動機(jī)的直觀圖示3.2.1由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖程序設(shè)計語言的單詞都能用正規(guī)文法描述；例如，標(biāo)識符可定義為

<標(biāo)識符><標(biāo)識符>字母<標(biāo)識符><標(biāo)識符>數(shù)字

<標(biāo)識符>字母若把字母、數(shù)字視為終結(jié)符，則上述產(chǎn)生式為（左線性）正規(guī)文法若我們用d表示0-9間的數(shù)字，則C語言的<無符號數(shù)>的文法也是（右線性）正規(guī)文法（見P49）一般說來，凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法——狀態(tài)轉(zhuǎn)換圖進(jìn)行分析。狀態(tài)轉(zhuǎn)換圖由有限個結(jié)點(diǎn)所組成的有向圖。每個結(jié)點(diǎn)代表在識別分析過程中掃描器所處的狀態(tài)，其中含有一個初始狀態(tài)和若干個終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。狀態(tài)之間可用有向邊連接，其上標(biāo)記一字符a，表示從有向邊的射出狀態(tài)出發(fā)，識別一字符a后，將進(jìn)入箭頭所指狀態(tài)（結(jié)點(diǎn)）由右線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一右線性文法,并設(shè)|VN|=K,則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個狀態(tài)(結(jié)點(diǎn)).用VN中的每個符號分別標(biāo)記其中的K個結(jié)點(diǎn),且令G的開始符S為初態(tài)結(jié)點(diǎn);余下的一個結(jié)點(diǎn)作為終態(tài)結(jié)點(diǎn),用F(VN)標(biāo)記.我們用如下規(guī)則來連接這K+1個結(jié)點(diǎn):(1)對于G中產(chǎn)生式AaB,從結(jié)點(diǎn)A引一有向邊到結(jié)點(diǎn)B,并用a標(biāo)記這一有向邊;(2)對于G中產(chǎn)生式Aa,從結(jié)點(diǎn)A引一有向邊到終態(tài)結(jié)點(diǎn)F,并用a標(biāo)記這一有向邊;(3)對于G中產(chǎn)生式A(若有的話),則將結(jié)點(diǎn)A設(shè)為終態(tài).例如,P49中定義的無符號數(shù)的文法對應(yīng)的狀態(tài)轉(zhuǎn)換圖為(化簡后):0453126d.dddd.E+|-Edd利用狀態(tài)轉(zhuǎn)換圖識別符號串的方法對于已給的字符串w=a1a2…an,aiVT,利用~對w識別的步驟如下:(1)從初始狀態(tài)S出發(fā),自左至右逐個掃描w的各個字符(當(dāng)前為a1),此時在結(jié)點(diǎn)S所射出的諸矢線中,尋找標(biāo)記為a1的矢線(若不存在,則表明w有語法錯誤),讀入a1并沿矢線所指方向前進(jìn),過渡到下一狀態(tài)(設(shè)為A1).(2)設(shè)當(dāng)前處在Ai狀態(tài),所掃描的字符為ai+1,在結(jié)點(diǎn)Ai所射出的諸矢線中,尋找標(biāo)記為ai+1的矢線(若不存在,則表明w有語法錯誤),讀入ai+1,并進(jìn)入狀態(tài)Ai+1;(3)重復(fù)(2),直到w中所有字符被讀完且恰好進(jìn)入終態(tài)F時,宣告整個識別結(jié)束,w可被接受.顯然,若我們從初態(tài)出發(fā),分別沿一切可能的路徑到達(dá)終態(tài)結(jié)點(diǎn),并將中徑中矢線上所標(biāo)記的字符依次連接起來,便得到狀態(tài)轉(zhuǎn)換圖所能識別的全部符號串,這些符號串組成的集合構(gòu)成了該~識別的語言=80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;標(biāo)識符,‘Line’分隔符,‘=’常量,‘80’分隔符,‘；數(shù)字?jǐn)?shù)字字母字母11==0003;;1輸入輸出有限控制器通過動畫演示給出詞法分析程序的完成其功能的過程，同時給出識別的結(jié)果狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)用狀態(tài)轉(zhuǎn)換圖識別符號串w的過程，就是為w建立一個推導(dǎo)S*w的過程。在第一步（在初始狀態(tài)S下，掃描到a1而過渡到下一狀態(tài)A1），由狀態(tài)轉(zhuǎn)換圖的構(gòu)造規(guī)則可知，G中必有產(chǎn)生式Sa1A1;對于識別過程的后續(xù)步驟，由狀態(tài)Ai識別ai+1后過渡到Ai+1恰好對應(yīng)了使用產(chǎn)生式Aiai+1Ai+1,…,最后在狀態(tài)An-1識別an后到達(dá)終態(tài)F，對應(yīng)了使用產(chǎn)生式Aan 進(jìn)行推導(dǎo)：

Sa1A1a1a2A2……a1a2…an-1An-1a1a2…an右線性文法與狀態(tài)轉(zhuǎn)換圖設(shè)G是一右線性文法,M是相應(yīng)的狀態(tài)轉(zhuǎn)換圖,則從前面的討論可以看出如下事實(shí)：(1)在利用M對符號串w進(jìn)行識別時,M中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo),即識別方法(或稱分析方法)是“”的;(2)因右線性文法只有形如AaB、Aa的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個非終結(jié)符，所以推導(dǎo)的規(guī)范的，每步所得的句型也必為規(guī)范句型；(3)對于M所識別的任一符號串x,必存在G中的一個推導(dǎo)S*x(即有xL(G);反之,對于L(G)中任一句子y,必存在一條從初態(tài)S到終態(tài)F的路徑,此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號串恰為y由左線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一左線性文法,構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖的方法是:首先用G的VN符標(biāo)記M的結(jié)點(diǎn),其中,開始符S對應(yīng)的結(jié)點(diǎn)為終態(tài)結(jié)點(diǎn).另外,再引入一個新結(jié)點(diǎn)R(VN)作為初態(tài).矢線的連接規(guī)則為:(1)對于G中形如Aa的產(chǎn)生式,引矢線:RA,且標(biāo)記為a;(2)對于G中形如ABa的產(chǎn)生式,引矢線BA,且標(biāo)記為a.由左線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖的例子已給文法G=({S,U},{0,1},{SS1|U1,UU0|0},S)RUSU00UU00SU11SS11用左線性文法構(gòu)造出的狀態(tài)轉(zhuǎn)換圖來識別文法的句子,其過程與前面右線性文法構(gòu)造的狀態(tài)轉(zhuǎn)換圖用法一樣不過,就識別的方法而言,它卻屬于“”分析.我們以句子00011為例,給出其識別的的步驟.見右表.步驟當(dāng)前狀態(tài) 余留的符號串1 R 000112 U 00113 U 0114 U 115 S 16 S (識別結(jié)束)識別符號串與歸約由構(gòu)造狀態(tài)轉(zhuǎn)換圖的方法可知,從初態(tài)R到下一狀態(tài)A的轉(zhuǎn)換,對應(yīng)了形如Ba

的產(chǎn)生式,即將終結(jié)符a歸約成非終結(jié)符B;類似地,從狀態(tài)B轉(zhuǎn)換到狀態(tài)A,對應(yīng)了形如ABa的產(chǎn)生式,即將Ba歸約為A;如此下去,直到從某狀態(tài)A轉(zhuǎn)換到狀態(tài)S(終態(tài)),對應(yīng)了形如SAa的產(chǎn)生式,即將Aa歸約為開始符S.此時歸約成功,也恰好進(jìn)入了終態(tài),即狀態(tài)轉(zhuǎn)換圖識別了(或接受)該符號串.前面識別00011的例子對應(yīng)的歸約過程見右圖00011UUUSS3.3有限自動機(jī)狀態(tài)轉(zhuǎn)換圖實(shí)際上是有限自動機(jī)的圖形表示3.3.1確定的有限自動機(jī)DFA1.抽象地看,狀態(tài)轉(zhuǎn)換圖由五個部分組成:(1)有限個狀態(tài)之集,記作K;(2)有限個輸入符號組成的字母表,記作;(3)從K到K的轉(zhuǎn)換函數(shù)

f:KK.f(p,a)=q表示若當(dāng)前狀態(tài)為p,且輸入符號為a,則進(jìn)入下一個狀態(tài)為q;(4)S0K,初始(開始)狀態(tài);(5)若干個終態(tài)之集:Z(K)由上述五個要素組成的五元式M=(K,,f,S0,Z)稱為一個確定的有限自動機(jī)

(DFA:DeterministicFiniteAutomata)由此可見,一DFA實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述(數(shù)學(xué)定義),狀態(tài)轉(zhuǎn)換圖是DFA的幾何(圖形)表示.DFA的接受集2.為定義DFA所接受(或識別)的符號串集合,我們先將其轉(zhuǎn)換函數(shù)f的定義域拓廣到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定義可知,對于x*,f^(s,x)=t的含義是,當(dāng)M從狀態(tài)s出發(fā),依次掃描完x的各個符號后將進(jìn)入狀態(tài)t.即只要f有定義,f^與f的效果是一致的.我們稱DFAM接受(或識別)某符號串x*,用狀態(tài)轉(zhuǎn)換圖來說,就是從初態(tài)S0出發(fā),經(jīng)一恰好標(biāo)有x的路徑后可達(dá)到某終態(tài)SZ

;用f^描述就是: SZ,f(S0,x)=S

M的接受集我們把一DFAM所接受的符號串的全體稱為M的接受集,記為L(M),即L(M)={x|f(S0,x)Z,x*}確定的有限自動機(jī)我們之所以把前面定義的有限自動機(jī)稱為確定的FA，是因?yàn)樵跔顟B(tài)轉(zhuǎn)換的每一步，根據(jù)FA當(dāng)前的狀態(tài)及掃描的輸入字符，便能唯一地確定FA的下一狀態(tài)。在轉(zhuǎn)換圖上看，若||=n，則任何結(jié)點(diǎn)所引出的矢線至多有n條，且矢線上的標(biāo)記均不同。例如，P52圖3-4所對應(yīng)的DFA為M=({R,U,S},{0,1},f,R,{S})其中，f的定義如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S由DFA與狀態(tài)轉(zhuǎn)換圖的關(guān)系可知，構(gòu)造狀態(tài)轉(zhuǎn)換圖的算法，同樣適用于構(gòu)造DFA。實(shí)際上，我們可以證明，正規(guī)文法G，DFAM，使 L(M)=L(G)，反之亦然。3.3.2非確定的有限自動機(jī)若在一左線性文法中含有多個右部相同的產(chǎn)生式，如 AUaBUaCUaXUa,或在一右線性文法中同時含有形如 UaAUaBUaCUaX的產(chǎn)生式，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會出現(xiàn)這樣的結(jié)點(diǎn)U，它具有多條標(biāo)記為同一輸入符號a的矢線，如右圖所示圖3-8NFA的狀態(tài)轉(zhuǎn)換圖由上圖可知，在U狀態(tài)下，輸入符號為a時，F(xiàn)A的下一狀態(tài)不唯一，而是在狀態(tài)集{A,B,C,…,X}中任選其一。具有這種性質(zhì)的FA稱為非確定的FA（NFA:Nondeterministic

FA）UABCXaaaa...非確定有限自動機(jī)的定義在形式上，NFAM同樣可用五元式定義：M=(K,,f,S0,Z)，其中，K,,S0,Z的含義同DFA,轉(zhuǎn)換函數(shù)f的定義為f:K(K),即將(Si,aj)映射到K的一個子集{Sk1,…,Skm}

類似地，我們可把f的定義域拓廣到K*：(1)f^(S,)={S};(2)f^(S,aw)=f^(f(S,a),w)a,w*.再設(shè)f(S,a)=

{Sk1,…,Skm},且定義這樣，我們已把f的定義域擴(kuò)大到(K)*。根據(jù)類似的理由，我們將對f和f^不加區(qū)分NFA的接受集對于x*,若集合f(S0,x)中含有Z中的元素（終態(tài)），則說明，至少存在一條從初態(tài)S0到某一終態(tài)的路徑，此路徑上的符號之連接恰為x，此時，我們稱x為M所接受所有為M所接受的符號串之集稱為NFAM的接受集（或識別集），記作L(M).即L(M)={x|f(S0,x)Z,x}例3.1給定M=({S,A,B,C},{a,b},f,S,{C}),其狀態(tài)轉(zhuǎn)換圖見右。由圖可知M是一NFA。M識別符號串a(chǎn)babb的路徑為S(a)A(b)B(a)A(b)B(b)C(接受)。(參見書中P60的表)SABCaa,babbaa注意，NFA識別輸入符號串時有一個試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了FA的效率。能否提高其工作效率就是我們下一小節(jié)討論的課題。事實(shí)上，對任一NFAM，總可構(gòu)造一個DFAM’，使L(M’)=L(M)成立。這就是NFA與DFA的等價性。3.3.3NFA與DFA的等價性定理3.1對于字母表上的任一NFAM，必存在與M等價的DFAM’

令I(lǐng)是一個狀態(tài)集的子集，定義ε-closure（I）為：1）若s∈I，則s∈ε-closure（I）；2）若s∈I，則從s出發(fā)經(jīng)過任意條ε弧能夠到達(dá)的任何狀態(tài)都屬于ε-closure（I）。狀態(tài)集ε-closure（I）稱為I的ε-閉包我們可以通過一例子來說明狀態(tài)子集的ε-閉包的構(gòu)造方法非確定有限自動機(jī)的確定化集合I的ε-閉包的定義例：如圖所示的狀態(tài)圖：令I(lǐng)={1}，求ε-closure（I）=？156432aεaaε根據(jù)定義：ε-closure（I）={1，3}我們同樣可以通過一例子來說明上述定義,仍采用前面給定的狀態(tài)圖為例----J是從狀態(tài)子集I中的每個狀態(tài)出發(fā),經(jīng)過標(biāo)記為a的弧而達(dá)到的狀態(tài)集合.--Ia是狀態(tài)子集,其元素為J中的狀態(tài),加上從J中每一個狀態(tài)出發(fā)通過ε弧到達(dá)的狀態(tài)定義2:令I(lǐng)是NFAM’的狀態(tài)集的一個子集,a∈Σ,定義:Ia=ε-closure(J)其中J=∪f(s,a)S∈I例：令I(lǐng)={1}Ia=ε-closure(J)=ε-closure(f(1，a))=ε-closure({2，4})={2，4，6}156432aεaaεNFA確定化—子集法設(shè)M=(K,,f,S0,Z)是上的NFA，現(xiàn)構(gòu)造上DFA M’=（K’,,f’,S0’,Z’).方法如下：首先從S0出發(fā)，求出ε-closure(S0)，記為DFA的初態(tài)q0，依次推導(dǎo)直到?jīng)]有新狀態(tài)產(chǎn)生。步驟如下：1、令k’={ε-closure(s0)}(即為DFA的初態(tài))2、對于k’中的任一尚未標(biāo)記的狀態(tài)qi={si1,si2……sik},sik∈K,作i)標(biāo)記qi；ii)對于每個a∈∑，置qj=ε-closure(f(qi,a)),若qj不在k’中，則作為一個未標(biāo)記的狀態(tài)添加到k’中，繼續(xù)循環(huán)。例：有NFAM’

先從狀態(tài)1開始，即I={1}a1234startabaccεI=ε-closure({1})={1,4}Ia=ε-closure(f(1,a)∪f(4,a))=-closure({2,3}∪φ)=ε-closure({2,3})={2,3}Ib=ε-closure(f(1,b)∪f(4,b))=-closure(φ)=φIc=ε-closure(f(1,c)∪f(4,c))=φ從上一步中獲得新狀態(tài){2,3},再計算I={2,3}的Ia,Ib,得到I={2,3},Ia={2},Ib={4},Ic={3,4}…1234startabaccεIIaIbIc

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號DFAM狀態(tài)轉(zhuǎn)換矩陣：符號狀態(tài)abc02341221________3344DFAM的狀態(tài)圖：01423start{1,4}{2,3}{4}{2}acabbc注意：包含原初始狀態(tài)1的狀態(tài)子集為DFAM的初態(tài)包含原終止?fàn)顟B(tài)4的狀態(tài)子集為DFAM的終態(tài)。{3,4}自動機(jī)的簡化一個DFAM的化簡是指尋找一個狀態(tài)數(shù)比較少的DFAM’,使L(M)=L(M’)。DFA的最小化就是尋求最小狀態(tài)DFA1、最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）2、狀態(tài)S和T等價的條件

一致性條件——狀態(tài)S和T必須同時為可接受狀態(tài)或不可接受狀態(tài)。蔓延性條件——對于所有輸入符號，狀態(tài)S和狀態(tài)T必須轉(zhuǎn)換到等價的狀態(tài)里。

3、DFA的最小化的方法（分割法）方法：將DFA的狀態(tài)分割成一些互不相交的子集?！胺指罘ā盌FA的最小化算法的核心把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.算法：A、將所有狀態(tài)分成兩個子集－－－終態(tài)集和非終態(tài)集B、運(yùn)用狀態(tài)等價原則分別對兩個子集的狀態(tài)進(jìn)行分析和劃分，把互相等價的狀態(tài)構(gòu)成一個子組。兩個狀態(tài)s和t分在同一子組的充要條件是：對所有的輸入符號a，狀態(tài)s和t都轉(zhuǎn)換為同一組中的狀態(tài)。若發(fā)現(xiàn)不等價，繼續(xù)劃分，這樣FA的狀態(tài)被分成互不相交的若干子集。C、從每個子組中選出一個狀態(tài)做代表，即可構(gòu)成簡化的FA例:最小化5724361srartaaaaaaabbbbbbb解:(一)區(qū)分終態(tài)與非終態(tài)12345663731546737414212ab123456637315467374142ab123區(qū)號區(qū)號當(dāng)輸入a時，6，7狀態(tài)在區(qū)號為2的子集內(nèi)，即可以將區(qū)號為1中的1，2化為一個子集123456637315467374142ab12431243123456637315467374142ab5區(qū)號區(qū)號將區(qū)號代替狀態(tài)號得:12345ab5214355231155243aaaaabbbbb到目前為止,我們已了解了對于任意三型語言L(G),存在DFAM使L(M)=L(G),反之,任意的M,存在G,使L(G)=L(M).這稱為描述語言的等價性.本節(jié)將引入正規(guī)表達(dá)式的概念,它們可用于描述三型語言的特征,特別是對自動生成詞法分析程序而言，它是非常有用的工具。所謂正規(guī)表達(dá)式就是用特定的運(yùn)算符及運(yùn)算對象按某種規(guī)則構(gòu)造的表達(dá)式，用于描述給定三型語言的所有句子。3.4正規(guī)表達(dá)式與正規(guī)集3.4.1正規(guī)表達(dá)式及正規(guī)集的定義定義設(shè)是一字母表,則上的正規(guī)表達(dá)式(正則表達(dá)式,正規(guī)式)及其表示的正規(guī)集可遞歸定義如下:(1)是一正規(guī)式,相應(yīng)的正規(guī)集為;(2)是一正規(guī)式,相應(yīng)的正規(guī)集為{};(3)a,a是一正規(guī)式,相應(yīng)的正規(guī)集為{a};(4)設(shè)r,s是正規(guī)式,且它們所表示的正規(guī)集為Lr,Ls,則 1.(r)?(s)是正規(guī)式,相應(yīng)的正規(guī)集為Lr?Ls; 2.(r)|(s)是正規(guī)式,相應(yīng)的正規(guī)集為LrLs; 3.(r)*是正規(guī)式,

相應(yīng)的正規(guī)集為Lr*有限地使用上面的規(guī)則(4),所得的表達(dá)式均是正規(guī)式.定義中的括號主要用于規(guī)定運(yùn)算順序.我們規(guī)定優(yōu)先級從高到低依次為*,?,|,則可以省略一些括號,例如((r)?((s)*)|(r)可簡寫為r?s*|r.另外,?常?？墒÷圆粚?rs*|r正規(guī)式與正規(guī)集的例子給定正規(guī)式,它唯一確定一正規(guī)集;反之不真.即一個正規(guī)集可由多個不同的正規(guī)式表示.若二正規(guī)式描述同一正規(guī)集,則稱二式等價(相等)正規(guī)式間的基本等價關(guān)系見下頁.正規(guī)式公理A1.r|s=s|r A2.r|r=r A3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st) A6.r(s|t)=rs|rtA7.(s|t)r=sr|st A8.r=r=A9.r=r=r A10.r*=(|r)*=|rr*例子例：令={l,d}，則上的正規(guī)式r=l(ld)定義的正規(guī)集為:{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字。正規(guī)式即是“字母(字母|數(shù)字)

”,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,這就是C和多數(shù)程序語言的標(biāo)識符詞法規(guī)則.例：令={d，，e，+，-},則上的正規(guī)式d(dd)(e(+-)dd)表示的是無符號數(shù)的集合。其中d為0~9的數(shù)字。

程序設(shè)計語言的單詞都能用正規(guī)式來定義.利用以下轉(zhuǎn)換規(guī)則,直至只剩下一個開始符號定義的產(chǎn)生式,并且產(chǎn)生式的右部不含非終結(jié)符.3.4.2由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式規(guī)則規(guī)則1規(guī)則2規(guī)則4文法產(chǎn)生式正則式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y規(guī)則3A→Ax|yA=yx*例:有文法G[s]S→aA|a,A→aA|dA|a|d于是:S=aA|aA=(aA|dA)|(a|d)A=(a|d)A|(a|d)由規(guī)則二:A=(a|d)*(a|d)代入:S=a(a|d)*(a|d)|a于是:S=a((a|d)*(a|d)|ε)1)對任何正則式r,選擇一個非終結(jié)符S作為識別符號.并產(chǎn)生產(chǎn)生式：S→r2)若x,y是正則式,對形為A=xy的產(chǎn)生式,重寫為A→xBB→y,其中B為新的非終結(jié)符,B∈VN同樣:對于A=x*yA→xAA→yA=x|yA→xA→y正則式正則文法例:將R=a(a|d)*轉(zhuǎn)