第二章詞法分析-閱讀頁(yè)
2025-08-04 19:51本頁(yè)面
【正文】 | b a b (a|b)*ab的分解 從正規(guī)式到有限自動(dòng)機(jī) 1 9 開(kāi)始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 從正規(guī)式到有限自動(dòng)機(jī) 1 9 開(kāi)始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 從正規(guī)式到有限自動(dòng)機(jī) 1 9 開(kāi)始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? r9 r7 r8 r4 r3 r5 r6 * ) ( r2 r1 a | b a b (a|b)*ab的分解 ? (a|b)*ab的兩個(gè) NFA的比較 1 2 開(kāi)始 a 0 a b b 手工構(gòu)造 : 算法構(gòu)造 : 從正規(guī)式到有限自動(dòng)機(jī) 1 9 開(kāi)始 ? 0 a b ? a b 6 7 8 2 3 4 5 ? ? ? ? ? ? ? 小結(jié)：從正規(guī)式建立識(shí)別器的步驟 – 從正規(guī)式構(gòu)造 NFA – 把 NFA變成 DFA – 將 DFA化簡(jiǎn) ? 存在其它辦法 從正規(guī)式到有限自動(dòng)機(jī) ? 用 Lex建立詞法分析器的步驟 Lex 編譯器 Lex源程序 C 編譯器 輸入流 記號(hào)序列 詞法分析器的生成器 ? Lex程序包括三個(gè)部分 聲明 ％％ 翻譯規(guī)則 ％％ 輔助過(guò)程 ? Lex程序的翻譯規(guī)則 p1 {動(dòng)作 1} p2 {動(dòng)作 2} … … pn {動(dòng)作 n} 詞法分析器的生成器 ? 例 ——聲明部分 %{ /* 常量 LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定義 */ %} /* 正規(guī)定義 */ delim [ \t \n ] ws {delim}+ letter [A ?Za ? z] digit [0?9] id {letter}({letter}|{digit})* number {digit}+(\ .{digit}+)?(E[+\?]?{digit}+)? 詞法分析器的生成器 ? 例 ——翻譯規(guī)則部分 {ws} {/* 沒(méi)有動(dòng)作 ， 也不返回 */} while {return (WHILE)。} do {return (DO)。 return (ID)。 return (NUMBER)。 return (RELOP)。 return (RELOP)。 return (RELOP)。 return (RELOP)。 return (RELOP)。 return (RELOP)。 yytext指向該詞法單元的第一個(gè)字符 ， yyleng給出的它的長(zhǎng)度 */ } installNum ( ) { /* 類似上面的過(guò)程 ， 但詞法單元不是標(biāo)識(shí)符而是數(shù) */ } 詞法分析器的生成器 ? 詞法分析器的作用和接口 ， 用高級(jí)語(yǔ)言編寫(xiě)詞法分析器等內(nèi)容 ? 掌握下面涉及的一些概念 ， 它們之間轉(zhuǎn)換的技巧 、 方法或算法 – 非形式描述的語(yǔ)言 ? 正規(guī)式 – 正規(guī)式 ? NFA – 非形式描述的語(yǔ)言 ? NFA – NFA ? DFA – DFA ? 最簡(jiǎn) DFA – 非形式描述的語(yǔ)言 ? DFA（ 或最簡(jiǎn) DFA） 本 章 要 點(diǎn) ? 敘述下面的正規(guī)式描述的語(yǔ)言 ， 并畫(huà)出接受該語(yǔ)言的最簡(jiǎn) DFA的狀態(tài)轉(zhuǎn)換圖 (1|01)* 0* – 描述的語(yǔ)言是 ， 所有不含子串 001的 0和 1的串 3 start 0 0 1 . 1 0 1 2 剛讀過(guò)的不是 0 連續(xù)讀過(guò)一個(gè) 0 連續(xù)讀過(guò) 不少于兩個(gè) 0 例 題 1 bbb a a b b a a b b start abb aaa aab aba bba baa bab a b a b a b a b bbabaabb 例 題 2 ? 用狀態(tài)轉(zhuǎn)換圖表示接受 (a|b)?a(a|b)(a|b)的 DFA ? 寫(xiě)出語(yǔ)言 “ 所有相鄰數(shù)字都不相同的非空數(shù)字串 ” 的正規(guī)定義 123031357106798035790123 answer ? (0 | no_0 0 ) (no_0 0 )? (no_0 | ? ) | no_0 no_0 ? (1 | no_01 1 ) (no_01 1 )? (no_01 | ? ) | no_01 . . . no_08 ? 9 將這些正規(guī)定義逆序排列就是答案 例 題 3 下面 C語(yǔ)言編譯器編譯下面的函數(shù)時(shí) ， 報(bào)告 parse error before ?else? long gcd(p,q) long p,q。 } 例 題 4 現(xiàn)在少了第一個(gè)注釋的結(jié)束符號(hào)后 ， 反而不 報(bào)錯(cuò)了 long gcd(p,q) long p,q。 } 例 題 4 ? 第一次 , (f) (g) ? 第二次 (c) (d)， ( 僅為 (c) )， ， 習(xí) 題
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1