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

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