從正規(guī)式到詞法

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

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

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

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

6、狀態(tài)轉移時： 消除 狀態(tài)轉移：-閉包(T) 消除多于一個的下一狀態(tài)轉移：smove(S, a)smove(S, a)：從狀態(tài)集S出發(fā)，標記為a的下一狀態(tài)全體。 與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài)-閉包(T)：從狀態(tài)T出發(fā)，不經任何字符達到的狀態(tài)全體。s1s2as3as4s5定義 狀態(tài)集T的-閉包(T)是一個狀態(tài)集，且滿足：（1） T中所有狀態(tài)屬于-閉包(T)；（2） 任何smove(-閉包(T)，)屬于-閉包(T)；（3） 再無其他狀態(tài)屬于-閉包(T)。 根據(jù)定義，上圖中-閉包(s2)應該包括：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進行識別。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 計算初態(tài)集-閉包(0) = 0,1,2,4,7， A2 從A出發(fā)經a到達-閉包(smove(A, a) = 3,8,6,7,1,2,4， B3 從B出發(fā)經b到達： -閉包(smove(B, b) = 5,9,6,7,1,2,4， C4 從C出發(fā)經b到達： -閉包(smove(C, b) = 5,10,6,7,1,2,4， D5 結束且D10=10，接受。識別的路徑為：A a B b C b D識別abab: 初態(tài)集：-閉包(s0)=0,1,2,4,7 A從A出發(fā)經a到達：-閉包(smove(A, a) = 3,8,6,7,1,2,4

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

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

11、 Dstates有尚未標記的狀態(tài)T loop 標記T; for 每一個輸入字符a loop U := -閉包(smove(T，a); if U不在Dstates中 then U作為尚未標記的狀態(tài)加入Dstates; end if; DtranT，a := U;- 記錄狀態(tài)轉移 end loop;end loop; 兩個數(shù)據(jù)結構：Dstates(狀態(tài))，Dtran(狀態(tài)轉移)112 NFA到DFA（續(xù)6）例 構造(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ā)到達不同的接受狀態(tài)，則稱對狀態(tài)t和s是可區(qū)分的。 反方向思考定義： 設想任何輸入序列對s和t均是不可區(qū)分的，則說明從s出發(fā)和從t出發(fā)，分析任何輸入序列均得到相同結果。 因此，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. 應用下述過程構造新的劃分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=，轉4；否則令=new并重復步驟2； 4. 在final每個組Gi中選一個代表si，使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉移在D中均從si出發(fā)，D中所有轉向Gi中的狀態(tài)轉移在D

15、中均轉向si；含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構成D的終態(tài)集F； 5. 刪除死狀態(tài)，即不是終態(tài)且對所有輸入字符均轉向其自身，或從初態(tài)不可到達的狀態(tài)。 14最小化DFA算法的主要步驟： 3 最小化DFA（續(xù)2） 初始劃分：終態(tài)與非終態(tài)； 利用可區(qū)分的概念，反復分裂劃分中的組Gi，直到不可再分裂； 由最終劃分構造D，關鍵是選代表和修改狀態(tài)轉移； 消除可能的死狀態(tài)和不可達狀態(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，反復分裂劃分中的組： 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構造D： 選代表，用A代表AC組； 修改狀態(tài)轉移： 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構造詞法分析器 表驅動型的詞法分析器 驅動器（算法

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

18、DFA識別輸入序列的過程。問題： 如何用程序模擬DFA識別輸入序列的過程？即如何用程序模擬DFA的狀態(tài)和它的狀態(tài)轉移？1. 狀態(tài)和狀態(tài)轉移與語句的對應關系 初態(tài)程序的開始； 終態(tài)程序的結束（return語句，不同終態(tài)return不同記號）； 狀態(tài)轉移分情況或者條件語句（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 兩類分析器的比較 表驅動直接編碼分析器的速度慢快程序與模式的關系無關有關分析器的規(guī)模較大較小適合的編寫方法工具生成手工編寫5 詞法分析器生成器簡介 構造詞法分析器的全過程均有算法：正規(guī)式NFADFA最小化DFA詞法分析器（分析表） LEX的基本結構根據(jù)正規(guī)式構造的分析表驅動器框架（不變的） 利用LEX構造詞法分析器的關鍵 用LEX提供的正規(guī)式集合設計記號的模式； 用LEX提供的語義支持識別記號或指出輸入中的錯誤。195 小結（略） 詞法分析的兩個重要環(huán)節(jié)：規(guī)定所有合法輸入識別合法輸入重要內容： 記號、模式與單詞 記號的說明：模式的形式化描述正規(guī)式 記號的識別：有限自動機NFA：與正規(guī)式有

21、對應關系，易于構造，狀態(tài)數(shù)少；DFA：確定性便于記號的識別，不易構造，狀態(tài)數(shù)可能會多；記號識別的方法： a. 模擬DFA： b. 模擬NFA（特殊情況下）：需要動態(tài)計算狀態(tài)子集。 從正規(guī)式到詞法分析器（等價變換的過程）正規(guī)式描述模式由正規(guī)式構造NFANFA的確定化（子集法：smove， -閉包）DFA的最小化（可區(qū)分概念）詞法分析器：表驅動（自動生成）與直接編碼（手工編寫）20算法 求-閉包輸入 狀態(tài)集T。輸出 狀態(tài)集T的-閉包方法 用下邊的函數(shù)計算-閉包 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-閉包; 用算法計算-閉包(s2)： U stack1. s2s22. s2, s4s43. s2, s4, s5s54. s2, s4, s5問題：試將函數(shù)直接寫為遞歸的兩個數(shù)據(jù)結構： 閉包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 接接受成組的記號，并將它們裝配為高層次的結構，類似受成組的記號，并將它們裝配為高層次的結構，類似于句子。于句子。vy

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

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

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

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

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

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

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

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

32、號標記指出了 Lex 程序中這一段的結束程序中這一段的結束和三段中第二段的開始。和三段中第二段的開始。 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ù)和變量提供了不同的信息，可以用來編譯實現(xiàn)復雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以實現(xiàn)復雜函數(shù)的程序。下表中列出了一些變量和函數(shù)，以及它們

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

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

36、束。yyless(int n)這一函數(shù)可以用來送回除了前這一函數(shù)可以用來送回除了前n 個字符外的所有個字符外的所有讀出標記。讀出標記。yymore()這一函數(shù)告訴這一函數(shù)告訴 Lexer 將下一個標記附加到當前將下一個標記附加到當前標記后。標記后。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實驗工具簡介實驗工具簡介-YACC-YACC yacc：另一個編譯器的編譯器：另一個編譯器的編譯器 將輸入拆分為一連串的記號?，F(xiàn)在您需要一些將輸入拆分為一連串的記號。現(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 聲明段聲明了終端符號和非終端聲明段聲明了終端符號和非終端符號（標記）的名稱，還可能描述操作符號（標記）的名稱，還可能描述操作符優(yōu)先級和針對不同符號的數(shù)據(jù)類型。符優(yōu)先級和針對不同符號的數(shù)據(jù)類型。 lexer (Lex) 一般返回這些標記。所有這些一般返回這些標記。所有這些標記都必須在標記都必須在 Yacc 聲明中進行說明。聲明中進行說明。45 終端和非終

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

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

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

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

47、yylval （另一個（另一個 Yacc 變變量）的類型。默認的類型量）的類型。默認的類型是是 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í)行相應的被匹配，將執(zhí)行相應的 括號中的動作。括號中的動作。 這里另一個有用的就是這里另一個有用的就是 $1 和和 $3 的使

49、用的使用, 它們引用了標記它們引用了標記 NAME 和和 NAME（或者第二行的（或者第二行的 VALUE）的值。的值。51附加附加 C 代碼代碼現(xiàn)在讓我們看一下語法文件的最現(xiàn)在讓我們看一下語法文件的最后一段，附加后一段，附加 C 代碼。（這一代碼。（這一段是可選的，如果有人想要略過段是可選的，如果有人想要略過它的話：）一個函數(shù)如它的話：）一個函數(shù)如 main() 調用調用 yyparse() 函數(shù)（函數(shù)（Lex 的的 yylex() 等效函數(shù)）。等效函數(shù)）。 一般來說一般來說，Yacc 最好提供最好提供 yyerror(char msg) 函數(shù)的代碼。函數(shù)的代碼。 當解析器遇當解析器遇到錯誤時調用到錯誤時調用 yyerror(char msg)。錯誤消息作為參數(shù)來傳。錯誤消息作為參數(shù)來傳遞。遞。 52Lex Lex 與與 Yacc Yacc 結合起來結合起來定義節(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