【正文】 。 Wensheng Li BUPT @ 2022 63/78 一、 LEX源程序 —— ? 對翻譯規(guī)則的補充 ? 翻譯規(guī)則部分中某些動作需要調用的過程，如果不是 C語言的庫函數(shù)，則要在此給出具體的定義。 ? 這些過程也可以存入另外的程序文件中，單獨編譯，然后和詞法分析器連接裝配在一起。 Wensheng Li BUPT @ 2022 64/78 LEX源程序舉例 ? LEX生成的詞法分析器的執(zhí)行：最長匹配原則 ? 傳遞單詞的屬性，是把屬性值賦給全程變量 yylval ? 正規(guī)定義式： if ? if then ? then else ? else relop ? | = | = | | | = id ? letter(letter|digit)* num ? digit+(.digit+)?(E(+|)?digit+)? Wensheng Li BUPT @ 2022 65/78 相應的 LEX規(guī)格說明 /* 說明部分 */ %{ include /* C語言描述的標識符常量的定義，如 LT、 LE、 EQ、 NE、 GT、GE、 IF、 THEN、 ELSE、 ID、 NUMBER、 RELOP */ extern yylval。 %} /* 正規(guī)定義式 */ delim [ \t\n] ws {delim}+ letter [AZaz] digit [09] id {letter}({letter}|{digit})* num {digit}+(\.{digit}+)?(E[+\]?{digit}+)? %% Wensheng Li BUPT @ 2022 66/78 /* 規(guī)則部分 */ {ws} {/* 沒有動作，也不返回 */} if { return(IF)。 } then { return(THEN)。 } else { return(ELSE)。 } {id} { yylval=install_id()。 return(ID)。 } {num} { yylval=install_num()。 return(NUMBER)。 } “” { yylval=LT。 return(RELOP)。 } “=” { yylval=LE。 return(RELOP)。 } “=” { yylval=EQ。 return(RELOP)。 } “” { yylval=NE。 return(RELOP)。 } “” { yylval=GT。 return(RELOP)。 } “=” { yylval=GE。 return(RELOP)。 } %% 相應的 LEX規(guī)格說明（續(xù)） 如果沒有 return語句，則，處理完整個輸入之后才會返回！！ Wensheng Li BUPT @ 2022 67/78 /* 輔助過程 */ int install_id() { /* 把單詞插入符號表并返回該單詞在符號表中的位置 yytext指向該單詞的第一個字符 yyleng給出它的長度 */ } int install_num() { /* 類似于上面的過程，但單詞是常數(shù) */ } 相應的 LEX規(guī)格說明（續(xù)） Wensheng Li BUPT @ 2022 68/78 LEX解決沖突的方式 1. 根據(jù)規(guī)則定義的先后次序 解決了例子中關鍵字和標識符的沖突 2. 最長匹配原則 解決了例子中諸如 “ ” 和 “ =” 的沖突 ?Wensheng Li BUPT @ 2022 69/78 二、 LEX的工作原理 —— ? 掃描每一條翻譯規(guī)則 Pi，為之構造一個非確定的有限自動機 NFA Mi ? 將各條翻譯規(guī)則對應的 NFA Mi合并為一個新的 NFA M 0 q1 q2 qn p1 p2 pn NFA M1 NFA M1 NFA M1 ? ? ? ? ? ? ? ? ? 開始 ? 將 NFA M確定化為 DFA D，并生成該 DFA D的狀態(tài)轉換矩陣和控制執(zhí)行程序。 Wensheng Li BUPT @ 2022 70/78 二、 LEX的工作原理 —— ? 最長匹配原則 – 在識別單詞符號過程中，當有幾個規(guī)則看來都適用時，則實施最長匹配的那個規(guī)則 ? 優(yōu)先匹配原則 – 如有幾條規(guī)則可以同時匹配一字符串，并且匹配的長度相同，則實施最上面的規(guī)則。 Wensheng Li BUPT @ 2022 71/78 二、 LEX的工作原理 —— %% a { } abb { } {a}*b* { } %% Wensheng Li BUPT @ 2022 72/78 讀 LEX源程序，分別生成非確定的有限自動機 開始 1 2 a 開始 3 4 5 6 b b a 開始 7 8 b b a a abb {a}*b* Wensheng Li BUPT @ 2022 73/78 合并為一個 NFA M 1 3 7 2 4 8 5 6 a b b a b b a 開始 0 ? ? ? Wensheng Li BUPT @ 2022 74/78 將該 NFA M確定化為 DFA D DFA D=({a,b},{A,B,C,D,E,F},A,{},?) 其中： A={0,1,3,7} B={2,4,7} C={8} D={7} E={5,8} F={6,8} A 開始 B E F C D a b a b a b b b b Wensheng Li BUPT @ 2022 75/78 控制執(zhí)行程序 —— 最長匹配原則 輸入字符串為 aba… 讀入 狀態(tài) A A 開始 B E F C D a b a b a b b b b A={0,1,3,7} B={2,4,7} C={8} D={7} E={5,8} F={6,8} 規(guī)則順序： a 終態(tài)： B abb 終態(tài)： F {a}*b* 終態(tài)： C,E,F a B b E a Wensheng Li BUPT @ 2022 76/78 控制執(zhí)行程序 —— 優(yōu)先匹配原則 輸入字符串為 abba… 讀入 狀態(tài) A a B b E b F a A 開始 B E F C D a b a b a b b b b A={0,1,3,7} B={2,4,7} C={8} D={7} E={5,8} F={6,8} 規(guī)則順序： a 終態(tài)： B abb 終態(tài)： F {a}*b* 終態(tài)： C,E,F Wensheng Li BUPT @ 2022 77/78 小 結 ? 詞法分析器的作用 ? 與語法分析器的關系 – 獨立、子程序、協(xié)同程序 ? 配對緩沖區(qū) – 必要性、算法 ? 記號 – 記號、模式、單詞 – 屬性 – 二元式形式 記號，屬性 – 描述：正規(guī)表達式、正規(guī)文法 – 識別：狀態(tài)轉換圖 Wensheng Li BUPT @ 2022 78/78 小 結 （續(xù)） ? 詞法分析器的設計與實現(xiàn) – 各類單詞符號的正規(guī)表達式 – 各類單詞符號的正規(guī)文法 – 構造與文法相應的狀態(tài)轉換圖 – 合并為詞法分析器的狀態(tài)轉換圖 – 增加語義動作，構造詞法分析器的程序框圖 – 確定輸出形式、設計翻譯表 – 定義變量和過程 – 編碼實現(xiàn)