從正規(guī)式到詞法

1、1從正規(guī)式到詞法分析器 構(gòu)造詞法分析器的一般方法和步驟： 用正規(guī)式對模式進(jìn)行描述； 為每個正規(guī)式構(gòu)造一個NFA，它識別正規(guī)式所表示的正規(guī)集； 將構(gòu)造出的NFA轉(zhuǎn)換成等價的DFA，這一過程也被稱為確定化； 優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過程也被稱為最小化； 從優(yōu)化后的DFA構(gòu)造詞法分析器。問題： 我們是從DFA構(gòu)造詞法分析器，為何不直接從正規(guī)式構(gòu)造DFA，而要先構(gòu)造NFA，然后轉(zhuǎn)換為DFA？原因： 機(jī)器構(gòu)造需要規(guī)范的算法； 正規(guī)式NFA：有規(guī)范的一對一的構(gòu)造算法 DFA分析器：有便于記號的識別的算法21 從正規(guī)式到NFA 算法 Thompson 算法輸入 字母表上的正規(guī)式r輸出 接受L(r)的

2、NFA N方法 首先分解r，然后根據(jù)下述步驟構(gòu)造NFA： 對，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受； s0f 對上的每一個字符a，構(gòu)造NFA如右s0fa 若N(p)和N(q)是正規(guī)式p和q的NFA，則 （a） 對正規(guī)式p|q，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p)L(q)； （b） 對正規(guī)式pq，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p)L(q)； N(P)N(Q)s0f （c） 對正規(guī)式p*，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p*)； N(P)s0f 對于正規(guī)式(p)，使用p本身的NFA，不再構(gòu)造新

3、的NFA。 s0fN(P)N(Q)31 從正規(guī)式到NFA（續(xù)1）s0fs0faN(P)N(Q)s0fN(P)N(Q)s0fN(P)s0f正規(guī)式 NFAaP|QPQP*定義: 令是一個有限字母表，則上的正規(guī)式及其表示的集合遞歸定義如下: 1 . 是 正 規(guī) 式 ， 它 表 示 集 合L()= 2. 若a是上的字符，則a是正規(guī)式，它表示集合L(a)=a 3. 若正規(guī)式r和s分別表示集合L(r)和L(s)，則 （a） r|s是正規(guī)式，表示集合L(r)L(s)， （b） rs是正規(guī)式，表示集合L(r)L(s)， （c） r*是正規(guī)式，表示集合(L(r)*， （d）(r)是正規(guī)式，表示的集合仍然是L(r

4、)。（加括弧改變優(yōu)先級、結(jié)合性） 可用正規(guī)式描述的語言稱為正規(guī)語言或正規(guī)集。 41 從正規(guī)式到NFA（續(xù)2）例用Thompson算法構(gòu)造正規(guī)式r=(a|b)*abb的NFA N(r) r11r9r10br7r8br5r6r4*( r3 )r1 | r2aba23a45b16078a9b10b 分解正規(guī)式 自下而上構(gòu)造NFA強(qiáng)調(diào)： 算法的構(gòu)造與正規(guī)式一一對應(yīng) 構(gòu)造一個新的NFA最多增加兩個狀態(tài)52 從NFA到DFA NFA識別記號的“并行”方法例從甲地到乙地，可以乘小轎車也可以騎自行車，具體路線如上。其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？（即識別

5、是否有從甲到乙標(biāo)記為cc的路徑） 甲乙123ccccbb試探（串行方式）： 甲 c 2 無路可走，退回 甲 c 1 c 3 無路可走，退回 甲 c 1 c 乙 到達(dá)乙地，成功 并行(假設(shè)有足夠的小汽車，每次都是到達(dá)小汽車可能到達(dá)的全體) 甲 c 1, 2 c 3, 乙 到達(dá)乙地，成功 由于并行的方法在每試探一步時，考慮了所有的下一狀態(tài)轉(zhuǎn)移，因此所走的每一步都是確定的。 用NFA識別記號，并不采用串行的方法（算法不易構(gòu)造，復(fù)雜度高且回溯），而是采用并行的方法，核心思想是將不確定的下一狀態(tài)確定化。6NFA上識別記號的確定化方法 2 從NFA到DFA（續(xù)1）確定化的兩個步驟（回顧DFA定義）計(jì)算下一

6、狀態(tài)轉(zhuǎn)移時： 消除 狀態(tài)轉(zhuǎn)移：-閉包(T) 消除多于一個的下一狀態(tài)轉(zhuǎn)移：smove(S, a)smove(S, a)：從狀態(tài)集S出發(fā)，標(biāo)記為a的下一狀態(tài)全體。 與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài)-閉包(T)：從狀態(tài)T出發(fā)，不經(jīng)任何字符達(dá)到的狀態(tài)全體。s1s2as3as4s5定義 狀態(tài)集T的-閉包(T)是一個狀態(tài)集，且滿足：（1） T中所有狀態(tài)屬于-閉包(T)；（2） 任何smove(-閉包(T)，)屬于-閉包(T)；（3） 再無其他狀態(tài)屬于-閉包(T)。 根據(jù)定義，上圖中-閉包(s2)應(yīng)該包括：1. s2自身s2（1）2. s4s2, s4（2）3. s5s2, s4, s5（

7、2）算法7算法 模擬NFA 2 從NFA到DFA（續(xù)2） 輸入 NFA N，x（eof）， s0， F 輸出 若N接受x，回答“yes”，否則“no” 方法 用下邊的過程對x進(jìn)行識別。S是一個狀態(tài)的集合 S := -閉包(s0); - 所有可能初態(tài)的集合a := nextchar;while a eof loop S:=-閉包(smove(S，a)； - 所有下一狀態(tài)的集合 a := nextchar;end loop;if SF then return “yes”; else return “no”; end if; 算法2.582 NFA到DFA（續(xù)3）例 在NFA上識別輸入序列abb和a

8、bab 23a45b16078a9b10b識別abb: 1 計(jì)算初態(tài)集-閉包(0) = 0,1,2,4,7， A2 從A出發(fā)經(jīng)a到達(dá)-閉包(smove(A, a) = 3,8,6,7,1,2,4， B3 從B出發(fā)經(jīng)b到達(dá)： -閉包(smove(B, b) = 5,9,6,7,1,2,4， C4 從C出發(fā)經(jīng)b到達(dá)： -閉包(smove(C, b) = 5,10,6,7,1,2,4， D5 結(jié)束且D10=10，接受。識別的路徑為：A a B b C b D識別abab: 初態(tài)集：-閉包(s0)=0,1,2,4,7 A從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A, a) = 3,8,6,7,1,2,4

9、B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 5,9,6,7,1,2,4 C從C出發(fā)經(jīng)a到達(dá)：-閉包(smove(C, a) = 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 5,9,6,7,1,2,4 C識別路徑為：A a B b C a B b C。由于C10=，所以不接受 9 “子集法”構(gòu)造DFA 2 NFA到DFA（續(xù)4） “并行”模擬NFA的弱點(diǎn)：每次動態(tài)計(jì)算下一狀態(tài)轉(zhuǎn)移的集合，效率低。 改進(jìn)方法：將NFA上的全部路徑均確定化并且記錄下來，得到與NFA等價的DFA。 甲乙123ccccbb甲1,23,乙3乙cbcbb 回顧從甲地到乙地的

10、路徑，它的數(shù)學(xué)模型實(shí)質(zhì)上是一個NFA （右上） 。 可以找到一個等價的DFA（右下），它們識別的路徑均是：ccccbcbb例 用DFA識別cc和cbc： 甲 c 1,2 c 3,乙， 接受 甲 c 1,2 b 3 c ?，不接受 優(yōu)點(diǎn)： 1. 消除了不確定性（將NFA的下一狀態(tài)集合并為一個狀態(tài)） 2. 無需動態(tài)計(jì)算狀態(tài)集合（針對模擬NFA的算法）10算法 從NFA構(gòu)造DFA（子集法） 2 NFA到DFA（續(xù)5）輸入 NFA N輸出 等價的DFA D。初態(tài)含有NFA初態(tài)，終態(tài)集是含有NFA終態(tài)的狀態(tài)集合方法 用下述過程構(gòu)造DFA ：-閉包(s0)是Dstates僅有的狀態(tài)，且尚未標(biāo)記;while

11、 Dstates有尚未標(biāo)記的狀態(tài)T loop 標(biāo)記T; for 每一個輸入字符a loop U := -閉包(smove(T，a); if U不在Dstates中 then U作為尚未標(biāo)記的狀態(tài)加入Dstates; end if; DtranT，a := U;- 記錄狀態(tài)轉(zhuǎn)移 end loop;end loop; 兩個數(shù)據(jù)結(jié)構(gòu)：Dstates(狀態(tài))，Dtran(狀態(tài)轉(zhuǎn)移)112 NFA到DFA（續(xù)6）例 構(gòu)造(a|b)*abb的DFA 010124356789ababb-閉包(0)=0,1,2,4,7* A-閉包(smove(A, a)=3,8,6,7,1,2,4* B-閉包(smove(A

12、, b)=5,6,7,1,2,4* C-閉包(smove(B, a)=3,8,6,7,1,2,4 B-閉包(smove(B, b)=5,9,6,7,1,2,4* D-閉包(smove(C, a)=3,8,6,7,1,2,4 B-閉包(smove(C, b)=5,6,7,1,2,4 C-閉包(smove(D, a)=3,8,6,7,1,2,4 B-閉包(smove(D, b)=5,10,6,7,1,2,4* E-閉包(smove(E, a)=3,8,6,7,1,2,4 B-閉包(smove(E, b)=5,6,7,1,2,4 C1032aabbbbaa問題：用哪個DFA識別輸入序列？識別abb和

13、abab：A a B b D b E 接受 A a B b D a B b D 不接受 ABabCaDbabaEbab123 最小化DFA 定義: 對于任何兩個狀態(tài)t和s，若從一狀態(tài)出發(fā)接受輸入字符串，而從另一狀態(tài)出發(fā)不接受，或者從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)，則稱對狀態(tài)t和s是可區(qū)分的。 反方向思考定義： 設(shè)想任何輸入序列對s和t均是不可區(qū)分的，則說明從s出發(fā)和從t出發(fā)，分析任何輸入序列均得到相同結(jié)果。 因此，s和t可以合并成一個狀態(tài)。 引入一個“可區(qū)分”的概念：正規(guī)式NFADFA13算法 最小化DFA的狀態(tài)數(shù) 3 最小化DFA（續(xù)1）輸入 DFA D=S，move，s0，F(xiàn)。輸出 等

14、價的D=S，move，s0，F(xiàn)，（D狀態(tài)數(shù)最少）方法 執(zhí)行如下步驟：1. 初始劃分=S-F，F(xiàn)1，F(xiàn)2，.，F(xiàn)i是F的子集，接受不同記號；2. 應(yīng)用下述過程構(gòu)造新的劃分new： for 的每一個組G loop 劃分G，G的兩個狀態(tài)s和t在同一組中的充要條件是: a.(move(s,a)Gimove(t,a)Gi)；- Gi是中某個組 用新劃分的組替代G，形成新的劃分new； end loop；3. 若new=，令final=，轉(zhuǎn)4；否則令=new并重復(fù)步驟2； 4. 在final每個組Gi中選一個代表si，使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D中均從si出發(fā)，D中所有轉(zhuǎn)向Gi中的狀態(tài)轉(zhuǎn)移在D

15、中均轉(zhuǎn)向si；含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構(gòu)成D的終態(tài)集F； 5. 刪除死狀態(tài)，即不是終態(tài)且對所有輸入字符均轉(zhuǎn)向其自身，或從初態(tài)不可到達(dá)的狀態(tài)。 14最小化DFA算法的主要步驟： 3 最小化DFA（續(xù)2） 初始劃分：終態(tài)與非終態(tài)； 利用可區(qū)分的概念，反復(fù)分裂劃分中的組Gi，直到不可再分裂； 由最終劃分構(gòu)造D，關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移； 消除可能的死狀態(tài)和不可達(dá)狀態(tài)。 BAEDabbbbaCbaaa例 用算法2.6化簡DFAm(A,a)=B, m(A,b)=Cm(B,a)=B, m(B,b)=Dm(C,a)=B, m(C,b)=Cm(D,a

16、)=B, m(D,b)=Em(E,a)=B, m(E,b)=C1初始化劃分1=ABCD，E2根據(jù)算法中步驟2，反復(fù)分裂劃分中的組： m(D, b)=E 2=ABC，D，E m(B, b)=D 3=AC，B，D，E 3？ 于是：final=AC，B，D，E 4根據(jù)final構(gòu)造D： 選代表，用A代表AC組； 修改狀態(tài)轉(zhuǎn)移： m(A,a)=B, m(A,b)=Am(B,a)=B, m(B,b)=Dm(D,a)=B, m(D,b)=Em(E,a)=B, m(E,b)=A用0、1、2、3代替A、B、D、E，得： 1032aabbbbaa154 由DFA構(gòu)造詞法分析器 表驅(qū)動型的詞法分析器 驅(qū)動器（算法

17、2.1）輸入字符序列分析表（DFA）記號流其中，需要：1. 有適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存放DFA；2.修改算法2.1，以適應(yīng)實(shí)際輸入： 識別整個文件，而不是一個 記號； 滿足最長匹配原則。對于輸入序列：result := a + b 正確的識別：id := id + id 錯誤的識別： 1. 僅識別一個： id （result） 2. 不滿足最長匹配：id id .（r或re或res . ） 16 直接編碼的詞法分析器 在表驅(qū)動的詞法分析器中，DFA是被動的，需要一個驅(qū)動器來模擬DFA的行為，以實(shí)現(xiàn)對輸入序列的分析。 直接編碼的詞法分析器，將DFA和DFA識別輸入序列的過程合并在一起，直接用程序代碼模擬

18、DFA識別輸入序列的過程。問題： 如何用程序模擬DFA識別輸入序列的過程？即如何用程序模擬DFA的狀態(tài)和它的狀態(tài)轉(zhuǎn)移？1. 狀態(tài)和狀態(tài)轉(zhuǎn)移與語句的對應(yīng)關(guān)系 初態(tài)程序的開始； 終態(tài)程序的結(jié)束（return語句，不同終態(tài)return不同記號）； 狀態(tài)轉(zhuǎn)移分情況或者條件語句（case/if）； 環(huán)循環(huán)語句（loop）； return滿足最長匹配原則。17 直接編碼的詞法分析器（續(xù)1）1032aabbbbaa2. 識別(a|b)*abb的程序框架main() char buf=abba#, *ptr=buf; while (*ptr!=# ) l0: while (*ptr=b) ptr+;/ sta

19、te 0l1: while (*ptr=a) ptr+;/ state 1 switch (*ptr) case a: goto l1; case b: ptr+; switch (*ptr)/ state 2 case a: goto l1; case b: ptr+; switch (*ptr) / state3 case a: goto l1; case b: goto l0; case #: coutyesendl; return; default: break; default: break; default: break; break; / 遇到非法字符 cout no endl;

20、18 兩類分析器的比較 表驅(qū)動直接編碼分析器的速度慢快程序與模式的關(guān)系無關(guān)有關(guān)分析器的規(guī)模較大較小適合的編寫方法工具生成手工編寫5 詞法分析器生成器簡介 構(gòu)造詞法分析器的全過程均有算法：正規(guī)式NFADFA最小化DFA詞法分析器（分析表） LEX的基本結(jié)構(gòu)根據(jù)正規(guī)式構(gòu)造的分析表驅(qū)動器框架（不變的） 利用LEX構(gòu)造詞法分析器的關(guān)鍵 用LEX提供的正規(guī)式集合設(shè)計(jì)記號的模式； 用LEX提供的語義支持識別記號或指出輸入中的錯誤。195 小結(jié)（略） 詞法分析的兩個重要環(huán)節(jié)：規(guī)定所有合法輸入識別合法輸入重要內(nèi)容： 記號、模式與單詞 記號的說明：模式的形式化描述正規(guī)式 記號的識別：有限自動機(jī)NFA：與正規(guī)式有

21、對應(yīng)關(guān)系，易于構(gòu)造，狀態(tài)數(shù)少；DFA：確定性便于記號的識別，不易構(gòu)造，狀態(tài)數(shù)可能會多；記號識別的方法： a. 模擬DFA： b. 模擬NFA（特殊情況下）：需要動態(tài)計(jì)算狀態(tài)子集。 從正規(guī)式到詞法分析器（等價變換的過程）正規(guī)式描述模式由正規(guī)式構(gòu)造NFANFA的確定化（子集法：smove， -閉包）DFA的最小化（可區(qū)分概念）詞法分析器：表驅(qū)動（自動生成）與直接編碼（手工編寫）20算法 求-閉包輸入 狀態(tài)集T。輸出 狀態(tài)集T的-閉包方法 用下邊的函數(shù)計(jì)算-閉包 function -閉包(T) isbegin for T中每個狀態(tài)t loop 加入t到U; push(t); end loop; wh

22、ile 棧不空 loop pop(t); for 每個u=move(t, ) loop if u不在U中 then 加入u到U; push(u); end if; end loop; end loop; return U;end-閉包; 用算法計(jì)算-閉包(s2)： U stack1. s2s22. s2, s4s43. s2, s4, s5s54. s2, s4, s5問題：試將函數(shù)直接寫為遞歸的兩個數(shù)據(jù)結(jié)構(gòu)： 閉包U和模擬遞歸的stacks1s2as3as4s521LexLex與與Yacc Yacc 快速入門快速入門22Lex Lex 和和 Yacc Yacc 介紹介紹 lex 和和 yac

23、c 是什么是什么vLex :Lexical Analyzar, 是一種生成掃描器的工具。是一種生成掃描器的工具。 Yacc :Yet Another Compiler Compiler vlex 和和 yacc 是是自動編譯代碼的工具自動編譯代碼的工具，適合于解析簡單，適合于解析簡單的語言。的語言。vlex 和和 yacc 是一對配對工具。是一對配對工具。lex 將文件分解為成組將文件分解為成組的的“記號（記號（tokens） ”，大體上類似于單詞。，大體上類似于單詞。yacc 接接受成組的記號，并將它們裝配為高層次的結(jié)構(gòu)，類似受成組的記號，并將它們裝配為高層次的結(jié)構(gòu)，類似于句子。于句子。vy

24、acc 設(shè)計(jì)用來處理設(shè)計(jì)用來處理 lex 的輸出，不過您也可以編寫自的輸出，不過您也可以編寫自己的代碼來完成此任務(wù)。同樣，己的代碼來完成此任務(wù)。同樣，lex 的輸出很大程度的輸出很大程度上設(shè)計(jì)用于為某類解析器提供數(shù)據(jù)。上設(shè)計(jì)用于為某類解析器提供數(shù)據(jù)。 23實(shí)驗(yàn)工具簡介總攬實(shí)驗(yàn)工具簡介總攬(1/2)LEXYACC代碼產(chǎn)生支撐函數(shù)24實(shí)驗(yàn)工具簡介總攬實(shí)驗(yàn)工具簡介總攬(2/2)25實(shí)驗(yàn)工具簡介-LEXLex：一個詞匯分析器生成器：一個詞匯分析器生成器 。 當(dāng)當(dāng) Lex 接收到文件或文本形式的輸入時，它試圖將文接收到文件或文本形式的輸入時，它試圖將文本與常規(guī)表達(dá)式進(jìn)行匹配。它一次讀入一個輸入字符，本與

25、常規(guī)表達(dá)式進(jìn)行匹配。它一次讀入一個輸入字符，直到找到一個匹配的模式。如果能夠直到找到一個匹配的模式。如果能夠找到一個匹配的找到一個匹配的模式模式，Lex 就執(zhí)行相關(guān)的動作就執(zhí)行相關(guān)的動作（可能包括返回一個標(biāo)（可能包括返回一個標(biāo)記）。另一方面，如果記）。另一方面，如果沒有沒有可以匹配的常規(guī)表達(dá)式，可以匹配的常規(guī)表達(dá)式，將會將會停止停止進(jìn)一步的處理，進(jìn)一步的處理，Lex 將將顯示一個錯誤消息顯示一個錯誤消息。 程序有三個部分，用程序有三個部分，用 % 符號隔開。符號隔開。第一部分和最后第一部分和最后一個部分一個部分是普通而是普通而古老的古老的 C 代碼代碼。中間中間是有趣的一部是有趣的一部分。它分

26、。它由一系列規(guī)則構(gòu)成由一系列規(guī)則構(gòu)成，lex 將這些規(guī)則翻譯為詞匯將這些規(guī)則翻譯為詞匯分析器。每一個規(guī)則依次包含一個正則表達(dá)式以及該分析器。每一個規(guī)則依次包含一個正則表達(dá)式以及該正則表達(dá)式得到匹配時要運(yùn)行的一些代碼。任何沒有正則表達(dá)式得到匹配時要運(yùn)行的一些代碼。任何沒有得到匹配的文本則簡單地拷貝到標(biāo)準(zhǔn)輸出。得到匹配的文本則簡單地拷貝到標(biāo)準(zhǔn)輸出。26Lex 的常規(guī)表達(dá)式（的常規(guī)表達(dá)式（1）字符字符 含義含義 A-Z, 0-9, a-z 構(gòu)成了部分模式的字符和數(shù)字。構(gòu)成了部分模式的字符和數(shù)字。. 匹配任意字符，除了匹配任意字符，除了 n。- 用來指定范圍。例如：用來指定范圍。例如：A-Z 指從指從

27、 A 到到 Z 之間的所有之間的所有字符。字符。 一個字符集合。匹配括號內(nèi)的一個字符集合。匹配括號內(nèi)的 任意任意 字符。如果第一字符。如果第一個字符是個字符是 那么它表示否定模式。例如：那么它表示否定模式。例如：abC 匹配匹配 a, b 和和 C中的任何一個。中的任何一個。 * 匹配匹配 0個個或者多個上述的模式?；蛘叨鄠€上述的模式。 + 匹配匹配 1個個或者多個上述模式。或者多個上述模式。 ? 匹配匹配 0個或個或1個個上述模式。上述模式。 $ 作為模式的最后一個字符匹配一行的結(jié)尾。作為模式的最后一個字符匹配一行的結(jié)尾。27Lex 的常規(guī)表達(dá)式（的常規(guī)表達(dá)式（2）字符字符 含義含義 指出一

28、個模式可能出現(xiàn)的次數(shù)。指出一個模式可能出現(xiàn)的次數(shù)。 例如：例如：A1,3 表示表示 A 可能出現(xiàn)可能出現(xiàn)1次或次或3次。次。 用來轉(zhuǎn)義元字符。同樣用來覆蓋字符在此表中用來轉(zhuǎn)義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。定義的特殊意義，只取字符的本意。 否定。否定。| 表達(dá)式間的邏輯或。表達(dá)式間的邏輯或。 字符的字面含義。元字符具有。字符的字面含義。元字符具有。/ 向前匹配。如果在匹配的模版中的向前匹配。如果在匹配的模版中的“/”后跟有后后跟有后續(xù)表達(dá)式，只匹配模版中續(xù)表達(dá)式，只匹配模版中“/”前面的部分。如：前面的部分。如：如果輸入如果輸入 A01，那么在模版，那么在模版

29、A0/1 中的中的 A0 是匹是匹配的。配的。( ) 將一系列常規(guī)表達(dá)式分組。將一系列常規(guī)表達(dá)式分組。28常規(guī)表達(dá)式舉例常規(guī)表達(dá)式舉例常規(guī)表達(dá)式常規(guī)表達(dá)式 含義含義 jokers 匹配匹配 jokes 或或 joker。A1,2shis+ 匹配匹配 AAshis, Ashis, Ashiss, Ashisss。(Ab-e)+ 匹配在匹配在 A 出現(xiàn)位置后跟隨的從出現(xiàn)位置后跟隨的從 b 到到 e 的的所有字符中的所有字符中的 1 個或個或 多個。多個。29標(biāo)記聲明舉例標(biāo)記聲明舉例標(biāo)記標(biāo)記 相關(guān)表達(dá)式相關(guān)表達(dá)式 含義含義 數(shù)字?jǐn)?shù)字(number) (0-9)+1個或多個數(shù)字個或多個數(shù)字字符字符(c

30、hars)A-Za-z任意字符任意字符空格空格(blank) 一個空格一個空格字字(word)(chars)+1個或多個個或多個 chars 變量變量(variable)(字符字符)+(數(shù)字?jǐn)?shù)字)*(字字符符)*(數(shù)字?jǐn)?shù)字)*30Lex 編程編程Lex 編程可以分為三步：編程可以分為三步： 以以 Lex 可以理解的格式指定模式相關(guān)的動作。可以理解的格式指定模式相關(guān)的動作。 在這一文件上運(yùn)行在這一文件上運(yùn)行 Lex，生成掃描器的，生成掃描器的 C 代碼。代碼。 編譯和鏈接編譯和鏈接 C 代碼，生成可執(zhí)行的掃描器。代碼，生成可執(zhí)行的掃描器。Lex 的輸入格式的輸入格式 一個一個 Lex 程序分為三

31、個段：程序分為三個段：第一段：是第一段：是 C 和和 Lex 的全局聲明的全局聲明第二段：包括模式（第二段：包括模式（C 代碼）代碼）第三段：是補(bǔ)充的第三段：是補(bǔ)充的 C 函數(shù)。函數(shù)。 這些段以這些段以%來分界。來分界。31（1）C 和和 Lex 的全局聲明的全局聲明 這一段中我們可以增加這一段中我們可以增加 C 變量聲明。變量聲明。 % int wordCount = 0; /*保存統(tǒng)計(jì)出來的字?jǐn)?shù)保存統(tǒng)計(jì)出來的字?jǐn)?shù) */ % chars A-Za-z numbers (0-9)+ delim nt whitespace delim+ words chars+ % 兩個百分號標(biāo)記指出了兩個百分

32、號標(biāo)記指出了 Lex 程序中這一段的結(jié)束程序中這一段的結(jié)束和三段中第二段的開始。和三段中第二段的開始。 32（2）Lex 的模式匹配規(guī)則的模式匹配規(guī)則words wordCount+; /* increase the word count by one*/ whitespace /* do nothing*/ numbers /* one may want to add some processing here*/ % 33（3）C 代碼代碼 Lex 編程的第三段，也就是最后一段覆蓋了編程的第三段，也就是最后一段覆蓋了 C 的函數(shù)聲明（有時是主函數(shù)）。的函數(shù)聲明（有時是主函數(shù)）。Lex 有一套

33、可供有一套可供使用的函數(shù)和變量。使用的函數(shù)和變量。 其中之一就是其中之一就是 yywrap。一。一般來說，般來說，yywrap() 的定義如下例的定義如下例。 void main() yylex(); /* start the analysis*/ printf( No of words: %dn, wordCount); int yywrap() return 1; 34Lex 變量變量 Lex 有幾個函數(shù)和變量提供了不同的信息，可以用來編譯有幾個函數(shù)和變量提供了不同的信息，可以用來編譯實(shí)現(xiàn)復(fù)雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以實(shí)現(xiàn)復(fù)雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以及它們

34、的使用。及它們的使用。yyinFILE* 類型。類型。 它指向它指向 lexer 正在解析的當(dāng)前文件。正在解析的當(dāng)前文件。yyoutFILE* 類型。類型。 它指向記錄它指向記錄 lexer 輸出的位置。輸出的位置。 缺缺省情況下，省情況下，yyin 和和 yyout 都指向標(biāo)準(zhǔn)輸入和輸出。都指向標(biāo)準(zhǔn)輸入和輸出。yytext匹配模式的文本存儲在這一變量中（匹配模式的文本存儲在這一變量中（char*）。）。yyleng給出匹配模式的長度。給出匹配模式的長度。yylineno 提供當(dāng)前的行數(shù)信息。（提供當(dāng)前的行數(shù)信息。（lexer不一定支持。）不一定支持。）35Lex 函數(shù)函數(shù)yylex()這一函

35、數(shù)開始分析。這一函數(shù)開始分析。 它由它由 Lex 自動生成。自動生成。yywrap()這一函數(shù)在文件（或輸入）的末尾調(diào)用。如果函這一函數(shù)在文件（或輸入）的末尾調(diào)用。如果函數(shù)的返回值是數(shù)的返回值是1，就停止解析。，就停止解析。 因此它可以用因此它可以用來解析多個文件。代碼可以寫在第三段，這來解析多個文件。代碼可以寫在第三段，這就能夠解析多個文件。就能夠解析多個文件。 方法是使用方法是使用 yyin 文件文件指針（見上表）指向不同的文件，直到所有指針（見上表）指向不同的文件，直到所有的文件都被解析。最后，的文件都被解析。最后，yywrap() 可以返回可以返回 1 來表示解析的結(jié)束。來表示解析的結(jié)

36、束。yyless(int n)這一函數(shù)可以用來送回除了前這一函數(shù)可以用來送回除了前n 個字符外的所有個字符外的所有讀出標(biāo)記。讀出標(biāo)記。yymore()這一函數(shù)告訴這一函數(shù)告訴 Lexer 將下一個標(biāo)記附加到當(dāng)前將下一個標(biāo)記附加到當(dāng)前標(biāo)記后。標(biāo)記后。36例：識別例：識別PL/0單詞的單詞的LEX程序程序%#include #include “code.h”#include “symbol.h”#include “y.tab.h”extern int level;int cc=0;%IDENT a-zA-Z a-zA-Z0-9*NUMBER 0-90-9*%37“ “ cc+ +; “t “ ta

37、blize( ); /* adjust cc to tab-position */“n“ cc=0;line_copy( ); /* copy a line of input file */“ “ cc+ +; return GT;“= “ cc+ +; return ET;“# “ cc+ +; return NT;“, “ cc+ +; return colon;“. “ cc+ +; return Period;“( “ cc+ +; return Lparen;“) “ cc+ +; return Rparen;“=“ cc+ +; cc+ +; return GE;“:= “ cc+

38、 +; cc+ +; return ASGN;“; “ cc+ +; return Semicolon;38NUMBER int n; cc += yyleng; sscanf(yytext,”%d”,&n); yylval.numder=n; return NUMBER; IDENT Symbol *s; cc += yyleng; if (s=lookup(yytext)=0) s=install(yytext,VARIABLE,level,0); if (s-type=C) yylval.numder=s-adr; else yylval.sym=s; return s-type

39、; %39int yywrap() return 1; 40實(shí)驗(yàn)工具簡介實(shí)驗(yàn)工具簡介-YACC-YACC yacc：另一個編譯器的編譯器：另一個編譯器的編譯器 將輸入拆分為一連串的記號?，F(xiàn)在您需要一些將輸入拆分為一連串的記號?，F(xiàn)在您需要一些方法來識別高層次的模式。這就是方法來識別高層次的模式。這就是 yacc 要做要做的：的：yacc 讓您可以描述希望怎樣處理記號。讓您可以描述希望怎樣處理記號。 411 1. . E - E + E E - E + E2. E - E 2. E - E * * E E3. E - id 3. E - id 1 . x + y 1 . x + y * * z s

40、hift z shift 2 x . + y 2 x . + y * * z reduce(r3) z reduce(r3) 3 E . + y 3 E . + y * * z shift z shift 4 E + . y 4 E + . y * * z shift z shift 5 E + y . 5 E + y . * * z reduce(r3) z reduce(r3) 6 E + E . 6 E + E . * * z shift z shift 7 E + E 7 E + E * * . z shift . z shift 8 E + E 8 E + E * * z . red

41、uce(r3) z . reduce(r3) 9 E + E 9 E + E * * E . reduce(r2) emit E . reduce(r2) emit multiply multiply 10 E + E . reduce(r1) emit 10 E + E . reduce(r1) emit add add 11 E . accept 11 E . accept Input:x + y Input:x + y * * z z4243 用用 Yacc 編寫語法編寫語法 如同如同 Lex 一樣一樣, 一個一個 Yacc 程序也用雙百分號程序也用雙百分號分為三段。它們是：聲明、語法規(guī)

42、則和分為三段。它們是：聲明、語法規(guī)則和 C 代代碼。碼。44 C 與與 Yacc 的聲明的聲明C 聲明可能會定義動作中使用的類型和聲明可能會定義動作中使用的類型和變量，以及宏。還可以包含頭文件。每變量，以及宏。還可以包含頭文件。每個個 Yacc 聲明段聲明了終端符號和非終端聲明段聲明了終端符號和非終端符號（標(biāo)記）的名稱，還可能描述操作符號（標(biāo)記）的名稱，還可能描述操作符優(yōu)先級和針對不同符號的數(shù)據(jù)類型。符優(yōu)先級和針對不同符號的數(shù)據(jù)類型。 lexer (Lex) 一般返回這些標(biāo)記。所有這些一般返回這些標(biāo)記。所有這些標(biāo)記都必須在標(biāo)記都必須在 Yacc 聲明中進(jìn)行說明。聲明中進(jìn)行說明。45 終端和非終

43、端符號終端和非終端符號 終端符號終端符號: 代表一類在語法結(jié)構(gòu)上等效的標(biāo)記。終端符代表一類在語法結(jié)構(gòu)上等效的標(biāo)記。終端符號有三種類型：號有三種類型：命名標(biāo)記命名標(biāo)記: 這些由這些由 %token 標(biāo)識符來定義。按照慣例，標(biāo)識符來定義。按照慣例，它們都是大寫。它們都是大寫。字符標(biāo)記字符標(biāo)記: 字符常量的寫法與字符常量的寫法與 C 相同。例如相同。例如, ? 就是就是一個字符標(biāo)記。一個字符標(biāo)記。字符串標(biāo)記字符串標(biāo)記 : 寫法與寫法與 C 的字符串常量相同。例如，的字符串常量相同。例如， 就是一個字符串標(biāo)記。就是一個字符串標(biāo)記。 非終端符號非終端符號: 是一組非終端符號和終端符號組成的符號。是一組非

44、終端符號和終端符號組成的符號。按照慣例，它們都是小寫。按照慣例，它們都是小寫。 在例子中，在例子中，file 是一個非終是一個非終端標(biāo)記而端標(biāo)記而 NAME 是一個終端標(biāo)記。是一個終端標(biāo)記。46這意味著表達(dá)式可以是幾種這意味著表達(dá)式可以是幾種格式中的任意一種；例如，格式中的任意一種；例如，一個變量、一個加號或者一一個變量、一個加號或者一個數(shù)字都可以是一個表達(dá)式個數(shù)字都可以是一個表達(dá)式。管道字符（。管道字符（|）表明可供）表明可供選擇。選擇。lexer 生成的符號稱生成的符號稱為為 終結(jié)符（終結(jié)符（terminals） 或或者者 記號（記號（tokens）。從它。從它們裝配而來的內(nèi)容稱為們裝配而

45、來的內(nèi)容稱為 非非終結(jié)符（終結(jié)符（non-terminals）。所以，在這個例子中，。所以，在這個例子中，NUMBER 是一個終結(jié)符；是一個終結(jié)符；lexer 正是生成這種結(jié)果。正是生成這種結(jié)果。相反，相反，value 是一個非終結(jié)是一個非終結(jié)符，它是通過裝配終結(jié)符而符，它是通過裝配終結(jié)符而創(chuàng)建出來的。創(chuàng)建出來的。 47 yacc 可以識別出記號的模式；例如，如上面例子可以識別出記號的模式；例如，如上面例子中所示，它可以識別出一個表達(dá)式可能由一個值、中所示，它可以識別出一個表達(dá)式可能由一個值、一個加號或者減號以及另一個值構(gòu)成。它還可以一個加號或者減號以及另一個值構(gòu)成。它還可以采取動作；當(dāng)解析器

46、達(dá)到表達(dá)式中的那個條件點(diǎn)采取動作；當(dāng)解析器達(dá)到表達(dá)式中的那個條件點(diǎn)時，封裝在時，封裝在 中的代碼塊將會被執(zhí)行。例如，有中的代碼塊將會被執(zhí)行。例如，有人可能會編寫：人可能會編寫： expression: value + value printf(Matched a + expression.n); 48你可能會覺得你可能會覺得 YYSTYPE 有點(diǎn)奇怪。但是類似有點(diǎn)奇怪。但是類似 Lex, Yacc 也有一套變量也有一套變量和函數(shù)可供用戶來進(jìn)行功和函數(shù)可供用戶來進(jìn)行功能擴(kuò)展。能擴(kuò)展。 YYSTYPE 定定義了用來將值從義了用來將值從 lexer 拷拷貝到解析器或者貝到解析器或者 Yacc 的的

47、yylval （另一個（另一個 Yacc 變變量）的類型。默認(rèn)的類型量）的類型。默認(rèn)的類型是是 int。 由于字符串可以由于字符串可以從從 lexer 拷貝，類型被重拷貝，類型被重定義為定義為 char*。 49 Yacc 語法規(guī)則語法規(guī)則vYacc 語法規(guī)則具有以下一般格式：語法規(guī)則具有以下一般格式：vresult: components /* action to be taken in C */ ; v在這個例子中，在這個例子中，result 是規(guī)則描述的非終是規(guī)則描述的非終端符號。端符號。Components 是根據(jù)規(guī)則放在一是根據(jù)規(guī)則放在一起的不同的終端和非終端符號。起的不同的終端和非

48、終端符號。 如果匹配如果匹配特定序列的話特定序列的話 Components 后面可以跟隨后面可以跟隨要執(zhí)行的動作。要執(zhí)行的動作。50 考慮如下的例子：考慮如下的例子：param : NAME EQ NAME printf(tName:%stValue(name):%sn, $1,$3); | NAME EQ VALUE printf(tName:%stValue(value):%sn,$1,$3); ; 如果上例中序列如果上例中序列 NAME EQ NAME 被匹配，將執(zhí)行相應(yīng)的被匹配，將執(zhí)行相應(yīng)的 括號中的動作。括號中的動作。 這里另一個有用的就是這里另一個有用的就是 $1 和和 $3 的使

49、用的使用, 它們引用了標(biāo)記它們引用了標(biāo)記 NAME 和和 NAME（或者第二行的（或者第二行的 VALUE）的值。的值。51附加附加 C 代碼代碼現(xiàn)在讓我們看一下語法文件的最現(xiàn)在讓我們看一下語法文件的最后一段，附加后一段，附加 C 代碼。（這一代碼。（這一段是可選的，如果有人想要略過段是可選的，如果有人想要略過它的話：）一個函數(shù)如它的話：）一個函數(shù)如 main() 調(diào)用調(diào)用 yyparse() 函數(shù)（函數(shù)（Lex 的的 yylex() 等效函數(shù)）。等效函數(shù)）。 一般來說一般來說，Yacc 最好提供最好提供 yyerror(char msg) 函數(shù)的代碼。函數(shù)的代碼。 當(dāng)解析器遇當(dāng)解析器遇到錯誤時調(diào)用到錯誤時調(diào)用 yyerror(char msg)。錯誤消息作為參數(shù)來傳。錯誤消息作為參數(shù)來傳遞。遞。 52Lex Lex 與與 Yacc Yacc 結(jié)合起來結(jié)合起來定義節(jié)定義節(jié)%規(guī)則節(jié)規(guī)則節(jié)%支撐函數(shù)節(jié)支撐函數(shù)節(jié) Token定義C codeSample%token %token INTEGERINTEGER#ifndef YYSTYPE #ifndef YYSTYPE #define YYSTYPE int #define YYSTYPE int #endif #endif #define INTEGER 258 #define INTEGER 258 ex