《編譯原理-劉善梅》第3章 詞法分析.ppt

第三章詞法分析 對(duì)于詞法分析器的要求詞法分析器的設(shè)計(jì)正規(guī)表達(dá)式與有窮自動(dòng)機(jī)詞法分析器的自動(dòng)產(chǎn)生 LEX 詞法分析 詞法分析的任務(wù) 從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描 產(chǎn)生一個(gè)個(gè)單詞符號(hào) 詞法分析器 LexicalAnalyzer 又稱掃描器 Scanner 執(zhí)行詞法分析的程序 3 1對(duì)于詞法分析器的要求 一 詞法分析器的功能和輸出形式功能 輸入源程序 輸出單詞符號(hào)單詞符號(hào)的種類 基本字 如begin repeat 標(biāo)識(shí)符 表示各種名字 如變量名 數(shù)組名和過(guò)程名常數(shù) 各種類型的常數(shù)運(yùn)算符 界符 逗號(hào) 分號(hào) 括號(hào)和空白 輸出的單詞符號(hào)的表示形式 單詞種別 單詞自身的值 單詞種別通常用整數(shù)編碼表示 若一個(gè)種別只有一個(gè)單詞符號(hào) 則種別編碼就代表該單詞符號(hào) 假定基本字 運(yùn)算符和界符都是一符一種 若一個(gè)種別有多個(gè)單詞符號(hào) 則對(duì)于每個(gè)單詞符號(hào) 給出種別編碼和自身的值 標(biāo)識(shí)符單列一種 標(biāo)識(shí)符自身的值表示成按機(jī)器字節(jié)劃分的內(nèi)部碼 常數(shù)按類型分種 常數(shù)的值則表示成標(biāo)準(zhǔn)的二進(jìn)制形式 例FORTRAN程序 IF 5 EQ M GOTO100輸出單詞符號(hào) 邏輯IF 34 左括號(hào) 2 整常數(shù) 20 5 的二進(jìn)制 等號(hào) 6 標(biāo)識(shí)符 26 M 右括號(hào) 16 GOTO 30 標(biāo)號(hào) 19 100 的二進(jìn)制 助憶符 直接用編碼表示不便于記憶 因此用助憶符來(lái)表示編碼 例 IF 34 IF 左括號(hào) 2 等號(hào) 6 例C程序 while i j i 輸出單詞符號(hào) 二 詞法分析器作為一個(gè)獨(dú)立子程序 詞法分析是作為一個(gè)獨(dú)立的階段 是否應(yīng)當(dāng)將其處理為一遍呢 作為獨(dú)立階段的優(yōu)點(diǎn) 結(jié)構(gòu)簡(jiǎn)潔 清晰和條理化 有利于集中考慮詞法分析一些枝節(jié)問(wèn)題 不作為一遍 將其處理為一個(gè)子程序 詞法分析器 詞法分析器的結(jié)構(gòu) 預(yù)處理子程序 掃描器 輸入緩沖區(qū) 掃描緩沖區(qū) 單詞符號(hào) 輸入 3 2詞法分析器的設(shè)計(jì) 刪除無(wú)用的空白 跳格 回車和換行等編輯性字符區(qū)分標(biāo)號(hào)區(qū) 捻接續(xù)行和給出句末符等 WhatALong Word WhatALong Wo rd WhatALong Wo rd WhatALong Wo 掃描緩沖區(qū) 起點(diǎn)搜索指示器指示器 一 掃描緩沖區(qū) 二 單詞符號(hào)的識(shí)別 超前搜索 以基本字的識(shí)別為例 例如 DO99K 1 10DO99K 1 10IF 5 EQ M GOTO55IF 5 EQ M GOTO55DO99K 1 10IF 5 55需要超前搜索才能確定哪些是基本字 幾點(diǎn)限制 不必使用超前搜索 所有基本字都是保留字 用戶不能用它們作自己的標(biāo)識(shí)符 基本字作為特殊的標(biāo)識(shí)符來(lái)處理 不用特殊的狀態(tài)圖來(lái)識(shí)別 只要查保留字表 如果基本字 標(biāo)識(shí)符和常數(shù) 或標(biāo)號(hào) 之間沒(méi)有確定的運(yùn)算符或界符作間隔 則必須使用一個(gè)空白符作間隔 三 狀態(tài)轉(zhuǎn)換圖 1概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖 結(jié)點(diǎn)代表狀態(tài) 用圓圈表示 狀態(tài)之間用箭弧連結(jié) 箭弧上的標(biāo)記 字符 代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類 一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài) 其中有一個(gè)為初態(tài) 至少要有一個(gè)終態(tài) 識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖 1 2 3 字母 其他 字母或數(shù)字 識(shí)別整常數(shù)的狀態(tài)轉(zhuǎn)換圖 一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別 或接受 一定的字符串 詞法分析器設(shè)計(jì)流程 某程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)串集 分析詞法規(guī)則 畫出識(shí)別單詞的狀態(tài)圖 根據(jù)狀態(tài)圖寫詞法分析器程序 3狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)思想 每個(gè)狀態(tài)結(jié)對(duì)應(yīng)一小段程序 做法 1 對(duì)不含回路的分叉結(jié) 可用一個(gè)CASE語(yǔ)句或一組IF THEN ELSE語(yǔ)句實(shí)現(xiàn) GetChar if IsLetter 狀態(tài)j的對(duì)應(yīng)程序段 elseif IsDigit 狀態(tài)k的對(duì)應(yīng)程序段 elseif ch 狀態(tài)l的對(duì)應(yīng)程序段 else 錯(cuò)誤處理 3狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)2 對(duì)含回路的狀態(tài)結(jié) 可對(duì)應(yīng)一段由WHILE語(yǔ)句構(gòu)成的程序 GetChar while IsLetter orIsDigit GetChar 狀態(tài)j的對(duì)應(yīng)程序段 3狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)3 終態(tài)結(jié)表示識(shí)別出某種單詞符號(hào) 因此 對(duì)應(yīng)語(yǔ)句為RETURN C VAL 其中 C為單詞種別 VAL為單詞自身值 全局變量與過(guò)程1 ch字符變量 存放最新讀入的源程序字符2 strToken字符數(shù)組 存放構(gòu)成單詞符號(hào)的字符串3 GetChar子程序過(guò)程 把下一個(gè)字符讀入到ch中4 GetBC子程序過(guò)程 跳過(guò)空白符 直至ch中讀入一非空白符5 Concat子程序 把ch中的字符連接到strToken 6 IsLetter和IsDisgital布爾函數(shù) 判斷ch中字符是否為字母和數(shù)字7 Reserve整型函數(shù) 對(duì)于strToken中的字符串查找保留字表 若它是保留字則給出它的編碼 否則回送08 Retract子程序 把搜索指針回調(diào)一個(gè)字符位置9 InsertId整型函數(shù) 將strToken中的標(biāo)識(shí)符插入符號(hào)表 返回符號(hào)表指針10 InsertConst整型函數(shù)過(guò)程 將strToken中的常數(shù)插入常數(shù)表 返回常數(shù)表指針 intcode value strToken 置strToken為空串 GetChar GetBC if IsLetter beginwhile IsLetter orIsDigit beginConcat GetChar endRetract 搜索指針回調(diào)code Reserve 判斷是否為保留字if code 0 標(biāo)識(shí)符beginvalue InsertId strToken return ID value endelsereturn code 保留字end elseif IsDigit beginwhile IsDigit beginConcat GetChar endRetract value InsertConst strToken return INT value endelseif ch return ASSIGN elseif ch return PLUS elseif ch beginGetChar if ch return POWER Retract return STAR endelseif ch return SEMICOLON elseif ch return LPAR elseif ch return RPAR elseProcError 錯(cuò)誤處理 將狀態(tài)圖的代碼一般化 變量curState用于保存現(xiàn)有的狀態(tài)用二維數(shù)組表示狀態(tài)圖 stateTrans state char curState 初態(tài)GetChar While stateTrans curState ch 有定義 存在后繼狀態(tài) 讀入 拼接Contact 轉(zhuǎn)入下一狀態(tài) 讀入下一字符curState stateTrans curState ch IfcurState是終態(tài)then返回strToken中的單詞GetChar 此處給出的只是一個(gè)框架 還有很多細(xì)節(jié)需要考慮 FA 正規(guī)集 正規(guī)式 DFA NFA 正規(guī)文法 3 3 1 3 3 23 3 3 3 3 4 3 3 5 DFA 3 3 6 3 3正規(guī)表達(dá)式與有限自動(dòng)機(jī) 易于程序?qū)崿F(xiàn) 易于人工設(shè)計(jì) 程序的單詞集合 詞法規(guī)則 詞法規(guī)則 3 3正規(guī)表達(dá)式與有限自動(dòng)機(jī) 幾個(gè)概念 考慮一個(gè)有窮字母表 字符集其中每一個(gè)元素稱為一個(gè)字符 上的字 也叫字符串 是指由 中的字符所構(gòu)成的一個(gè)有窮序列不包含任何字符的序列稱為空字 記為 用 表示 上的所有字的全體 包含空字 例如 設(shè) a b 則 a b aa ab ba bb aaa 的子集U和V的連接 積 定義為UV U記V VV 稱V 是V的正規(guī)閉包 3 3 1正規(guī)式和正規(guī)集 正規(guī)集可以用正規(guī)表達(dá)式 簡(jiǎn)稱正規(guī)式 表示 正規(guī)表達(dá)式是表示正規(guī)集一種方法 一個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)式表示 正規(guī)式和正規(guī)集的遞歸定義 對(duì)給定的字母表 1 和 都是 上的正規(guī)式 它們所表示的正規(guī)集為 和 2 任何a a是 上的正規(guī)式 它所表示的正規(guī)集為 a 3 假定e1和e2都是 上的正規(guī)式 它們所表示的正規(guī)集為L(zhǎng) e1 和L e2 則i e1 e2 為正規(guī)式 它所表示的正規(guī)集為L(zhǎng) e1 L e2 ii e1 e2 為正規(guī)式 它所表示的正規(guī)集為L(zhǎng) e1 L e2 連接積 iii e1 為正規(guī)式 它所表示的正規(guī)集為 L e1 閉包 即任意有限次的自重復(fù)連接 僅由有限次使用上述三步驟而定義的表達(dá)式才是 上的正規(guī)式 僅由這些正規(guī)式表示的字集才是 上的正規(guī)集 所有詞法結(jié)構(gòu)一般都可以用正規(guī)式描述 若兩個(gè)正規(guī)式所表示的正規(guī)集相同 則稱這兩個(gè)正規(guī)式等價(jià) 如b ab ba b a b a b L ba b L ba L b L ba L b L b L a L b ba b ba baba bababa b b bab babab bababab L b ab L b L ab L b L ab L b L a L b b ab b ab abab ababab b bab babab bababab L b ab L ba b b ab ba b 對(duì)正規(guī)式 下列等價(jià)成立 e1 e2 e2 e1交換律e1 e2 e3 e1 e2 e3結(jié)合律e1 e2e3 e1e2 e3結(jié)合律e1 e2 e3 e1e2 e1e3分配律 e2 e3 e1 e2e1 e3e1分配律e e ee1e2e2e1 L e1 e2 L e1 L e2 L e2 L e1 L e2 e1 FA 正規(guī)集 正規(guī)式 DFA NFA 3 3 1 3 3 23 3 3 程序的單詞集合 詞法規(guī)則 3 3 2確定有限自動(dòng)機(jī) DFA 對(duì)狀態(tài)圖進(jìn)行形式化 則可以下定義 自動(dòng)機(jī)M是一個(gè)五元式M S f S0 F 其中 1 S 有窮狀態(tài)集 2 輸入字母表 有窮 3 f 狀態(tài)轉(zhuǎn)換函數(shù) 為S S的單值部分映射 f s a s 表示 當(dāng)現(xiàn)行狀態(tài)為s 輸入字符為a時(shí) 將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s 我們把s 稱為s的一個(gè)后繼狀態(tài) 4 S0 S是唯一的一個(gè)初態(tài) 5F S 終態(tài)集 可空 例如 DFAM 0 1 2 3 a b f 0 3 其中 f定義如下 f 0 a 1f 0 b 2f 1 a 3f 1 b 2f 2 a 1f 2 b 3f 3 a 3f 3 b 3 狀態(tài)轉(zhuǎn)換矩陣 對(duì)于 中的任何字符串 若存在一條從初態(tài)到某一終態(tài)的道路 且這條路上所有弧上的標(biāo)記符連接成的字符串等于 則稱 為DFAM所識(shí)別 接收 DFAM所識(shí)別的字符串的全體記為L(zhǎng) M 練習(xí)下圖DFA識(shí)別的L M 是什么 A L M 以aa或bb開頭的字符串 B L M 含aa或bb的字符串 C L M 以aa或bb結(jié)尾的字符串 答案 B 3 3 3非確定有限自動(dòng)機(jī) NFA 1976年圖靈獎(jiǎng)Fortheirjointpaper Finiteautomataandtheirdecisionproblems whichintroducedtheideaofnondeterministicmachines whichhasprovedtobeanenormouslyvaluableconcept Theirclassicpaperhasbeenacontinuoussourceofinspirationforsubsequentworkinthisfield 3 3 3非確定有限自動(dòng)機(jī) NFA 定義 一個(gè)非確定有限自動(dòng)機(jī) NFA M是一個(gè)五元式M S f S0 F 其中 1S 有窮狀態(tài)集 2 輸入字母表 有窮 3f 狀態(tài)轉(zhuǎn)換函數(shù) 為S 2S的部分映射 非單值 4S0 S是非空的初態(tài)集 5F S 終態(tài)集 可空 從狀態(tài)圖可看出NFA和DFA的區(qū)別 1可有多個(gè)初態(tài)2弧上的標(biāo)記可以是 中的一個(gè)字 甚至可以是一個(gè)正規(guī)式 而不一定是單個(gè)字符 3同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧上 DFA是NFA的特例 NFA DFA 對(duì)于 中的任何字 若存在一條從初態(tài)到某一終態(tài)的道路 且這條路上所有弧上的標(biāo)記符連接成的字等于 忽略那些標(biāo)記為 的弧 則稱 為NFAM所識(shí)別 接收 NFAM所識(shí)別的字符串的全體記為L(zhǎng) M 識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)b的字 ambn m n 1 NFA示例 定義 對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和M 如果L M L M 則稱M與M 等價(jià) 自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論 判定兩個(gè)自動(dòng)機(jī)等價(jià)性的算法是存在的 對(duì)于每個(gè)NFAM存在一個(gè)DFAM 使得L M L M 亦即DFA與NFA描述能力相同 NFA與DFA 1 假定NFAM 我們對(duì)NFAM的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造 1 引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y X Y S 從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條 箭弧 從F中任意狀態(tài)結(jié)點(diǎn)連一條 箭弧到Y(jié) 2 按以下3條規(guī)則對(duì)NFAM的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換 直到把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為 上的一個(gè)字符或 其中k是新引入的狀態(tài) NFA轉(zhuǎn)換為等價(jià)的DFA 代之為 代之為 代之為 按下面的3條規(guī)則對(duì)箭弧進(jìn)行分裂 例 識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)b的字 2 把上述NFA確定化 采用子集法 設(shè)I是NFA的狀態(tài)集的一個(gè)子集 定義I的 閉包 closure I 為 i 若s I 則s closure I ii 若s I 則從s出發(fā)經(jīng)過(guò)任意條 弧而能到達(dá)的任何狀態(tài)s 都屬于 closure I 即 closure I I s 從某個(gè)s I出發(fā)經(jīng)過(guò)任意條 弧能到達(dá)s 設(shè)a是 中的一個(gè)字符 定義Ia closure J 其中 J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合 closure 1 1 2 IJ 5 4 3 Ia closure J closure 5 4 3 5 4 3 6 2 7 8 設(shè)a是 中的一個(gè)字符 定義Ia closure J 其中 J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合 Ia 確定化的過(guò)程 不失一般性 設(shè)字母表只包含兩個(gè)a和b 我們構(gòu)造一張表 首先 置第1行第1列為 closure X 求出這一列的Ia Ib 然后 檢查這兩個(gè)Ia Ib 看它們是否已在表中的第一列中出現(xiàn) 把未曾出現(xiàn)的填入后面的空行的第1列上 求出每行第2 3列上的集合 重復(fù)上述過(guò)程 知道所有第2 3列子集全部出現(xiàn)在第一列為止 I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y 現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣 把其中的每個(gè)子集看成一個(gè)狀態(tài) 這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)M 它的初態(tài)是 closure X 它的終態(tài)是含有原終態(tài)Y的子集 不難看出 這個(gè)DFAM與M 等價(jià) I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y FA 正規(guī)集 正規(guī)式 DFA NFA 3 3 1 3 3 23 3 3 程序的單詞集合 詞法規(guī)則 3 3 5 3 3 5正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性 定理 1 對(duì)任何FAM 都存在一個(gè)正規(guī)式r 使得L r L M 2 對(duì)任何正規(guī)式r 都存在一個(gè)FAM 使得L M L r 對(duì)轉(zhuǎn)換圖概念拓廣 令每條弧可用一個(gè)正規(guī)式作標(biāo)記 對(duì)一類輸入符號(hào) 證明 1對(duì) 上任一NFAM 構(gòu)造一個(gè) 上的正規(guī)式r 使得L r L M 首先 在M的轉(zhuǎn)換圖上加進(jìn)兩個(gè)狀態(tài)X和Y 從X用 弧連接到M的所有初態(tài)結(jié)點(diǎn) 從M的所有終態(tài)結(jié)點(diǎn)用 弧連接到Y(jié) 從而形成一個(gè)新的NFA 記為M 它只有一個(gè)初態(tài)X和一個(gè)終態(tài)Y 顯然L M L M 然后 反復(fù)使用下面的一條規(guī)則 逐步消去的所有結(jié)點(diǎn) 直到只剩下X和Y為止 代之為 代之為 代之為 1 2 5 4 V1 U1 U2 W1 V1 U1 U2 W2 V2 U1 U2 W2 V2 U1 U2 W1 最后 X到Y(jié)的弧上標(biāo)記的正規(guī)式即為所構(gòu)造的正規(guī)式r顯然L r L M L M 定理 1 對(duì)任何FAM 都存在一個(gè)正規(guī)式r 使得L r L M 2 對(duì)任何正規(guī)式r 都存在一個(gè)FAM 使得L M L r 證明2 對(duì)于 上的正規(guī)式r 構(gòu)造一個(gè)NFAM 使L M L r 并且M只有一個(gè)終態(tài) 而且沒(méi)有從該終態(tài)出發(fā)的箭弧 下面使用關(guān)于r中運(yùn)算符數(shù)目的歸納法證明上述結(jié)論 1 若r具有零個(gè)運(yùn)算符 則r 或r 或r a 其中a 此時(shí)下圖所示的三個(gè)有限自動(dòng)機(jī)顯然符合上述要求 2 假設(shè)結(jié)論對(duì)于少于k k 1 個(gè)運(yùn)算符的正規(guī)式成立 當(dāng)r中含有k個(gè)運(yùn)算符時(shí) r有三種情形 情形1 r r1 r2 r1 r2中運(yùn)算符個(gè)數(shù)少于k 從而 由歸納假設(shè) 對(duì)ri存在Mi 使得L Mi L ri 并且Mi沒(méi)有從終態(tài)出發(fā)的箭弧 i 1 2 不妨設(shè)S1 S2 在S1 S2中加入兩個(gè)新狀態(tài)q0 f0 令M 其中 定義如下 a q0 q1 q2 b q a 1 q a 當(dāng)q S1 f1 a 1 c q a 2 q a 當(dāng)q S2 f2 a 2 d f1 f2 f0 M的狀態(tài)轉(zhuǎn)換如右圖所示 L M L M1 L M2 L r1 L r2 L r q0 f0 情形2 r r1r2 設(shè)Mi同情形1 i 1 2 令M 其中 定義如下 a q a 1 q a 當(dāng)q S1 f1 a 1 b q a 2 q a 當(dāng)q S2 a 2 c f1 q2 M的狀態(tài)轉(zhuǎn)換如右圖所示 L M L M1 L M2 L r1 L r2 L r 情形3 r r1 設(shè)M1同情形1 令M 其中q0 f0 S1 定義如下 a q0 f1 q1 f0 b q a 1 q a 當(dāng)q S1 f1 a 1 M的狀態(tài)轉(zhuǎn)換如右圖所示 L M L M1 L r1 L r 至此 結(jié)論2獲證 q0 f0 1 構(gòu)造 上的NFAM 使得L V L M 首先 把V表示成 上述證明過(guò)程實(shí)質(zhì)上是一個(gè)將正規(guī)表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)的算法 代之為 代之為 代之為 然后 按下面的三條規(guī)則對(duì)V進(jìn)行分裂 逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為 上的一個(gè)字符或 最后得到一個(gè)NFAM 顯然L M L V a b aa bb a b FA 正規(guī)集 正規(guī)式 DFA NFA 3 3 1 3 3 23 3 3 3 3 5 程序的單詞集合 詞法規(guī)則 易于程序?qū)崿F(xiàn) 易于人工設(shè)計(jì) DFA 3 3 6 3 3 6確定有限自動(dòng)機(jī)的化簡(jiǎn) 對(duì)DFAM的化簡(jiǎn) 尋找一個(gè)狀態(tài)數(shù)比M少的DFAM 使得L M L M 假設(shè)s和t為M的兩個(gè)狀態(tài) 稱s和t等價(jià) 如果從狀態(tài)s出發(fā)能讀出某個(gè)字 而停止于終態(tài) 那么同樣 從t出發(fā)也能讀出 而停止于終態(tài) 反之亦然 兩個(gè)狀態(tài)不等價(jià) 則稱它們是可區(qū)別的 對(duì)一個(gè)DFAM最少化的基本思想 把M的狀態(tài)集劃分為一些不相交的子集 使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的 而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的 最后 讓每個(gè)子集選出一個(gè)代表 同時(shí)消去其他狀態(tài) 具體做法 對(duì)M的狀態(tài)集進(jìn)行劃分首先 把S劃分為終態(tài)和非終態(tài)兩個(gè)子集 形成基本劃分 假定到某個(gè)時(shí)候 已含m個(gè)子集 記為 I 1 I 2 I m 檢查 中的每個(gè)子集看是否能進(jìn)一步劃分 對(duì)某個(gè)I i 令I(lǐng) i s1 s2 sk 若存在一個(gè)輸入字符a使得Ia i 不會(huì)包含在現(xiàn)行 的某個(gè)子集I j 中 即 Ia i 中的元素分布在現(xiàn)行劃分的多個(gè)子集中 則至少應(yīng)把I i 分為兩個(gè)部分 例如 假定狀態(tài)s1和s2經(jīng)a弧分別到達(dá)t1和t2 而t1和t2屬于現(xiàn)行 中的兩個(gè)不同子集 說(shuō)明有一個(gè)字 t1讀出 后到達(dá)終態(tài) 而t2讀出 后不能到達(dá)終態(tài) 或者反之 那么對(duì)于字a s1讀出a 后到達(dá)終態(tài) 而s2讀出a 不能到達(dá)終態(tài) 或者反之 所以s1和s2不等價(jià) s1 t1 a s2 t2 a j i 則將I i 分成兩半 使得一半含有s1 I i1 s s I i 且s經(jīng)a弧到達(dá)t 且t與t1屬于現(xiàn)行 中的同一子集 另一半含有s2 I i2 I i I i1 一般地 對(duì)某個(gè)a和I i 若Ia i 落入現(xiàn)行 中N個(gè)不同子集 則應(yīng)把I i 劃分成N個(gè)不相交的組 使得每個(gè)組J的Ja都落入的 同一子集 這樣構(gòu)成新的劃分 重復(fù)上述過(guò)程 直到 所含子集數(shù)不再增長(zhǎng) 對(duì)于上述最后劃分 中的每個(gè)子集 我們選取每個(gè)子集I中的一個(gè)狀態(tài)代表其他狀態(tài) 則可得到化簡(jiǎn)后的DFAM 若I含有原來(lái)的初態(tài) 則其代表為新的初態(tài) 若I含有原來(lái)的終態(tài) 則其代表為新的終態(tài) I 1 0 1 2 I 2 3 4 5 6 Ia 1 1 3 I 11 0 2 I 12 1 I 2 3 4 5 6 I 11 0 2 Ia 11 1 Ib 11 2 5 I 111 0 I 112 2 I 12 1 I 2 3 4 5 6 Ia 2 3 6 Ib 2 4 5 FA 正規(guī)集 正規(guī)式 DFA NFA 3 3 1 3 3 23 3 3 3 3 5 DFA 3 3 6 程序的單詞集合 詞法規(guī)則 易于程序?qū)崿F(xiàn) 易于人工設(shè)計(jì) 85 一 原理單詞的詞法規(guī)則用正規(guī)式描述正規(guī)式 NFA DFA minDFA LEX編譯器 LEX源程序lex 1 詞法分析程序Lex yy c 二 用LEX建立詞法分析程序的過(guò)程 3 4詞法分析器的自動(dòng)產(chǎn)生 LEX 86 C編譯器 詞法分析程序Lex yy c 詞法分析程序Lex out或lex exe 詞法分析程序L 單詞符號(hào) 輸入串 狀態(tài)轉(zhuǎn)換矩陣 控制執(zhí)行程序 3 4詞法分析器的自動(dòng)產(chǎn)生 LEX 3 4詞法分析器的自動(dòng)產(chǎn)生 LEX lex源程序lex源程序由三部分組成 聲明 識(shí)別規(guī)則