《編譯原理》第三章詞法分析.ppt

《《編譯原理》第三章詞法分析.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《編譯原理》第三章詞法分析.ppt（37頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第三章詞法分析 第三章詞法分析 主要章節(jié)3 1詞法分析與詞法分析程序3 2詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)3 3詞法分析程序的自動(dòng)生成 3 1詞法分析程序的功能 詞法分析的功能從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描 產(chǎn)生一個(gè)個(gè)單詞符號(hào) 再轉(zhuǎn)換成詞標(biāo)流的過(guò)程 3 4 while i j if i j i i j elsej j i while i j if i j i i j else j j i 3 1詞法分析程序的功能 3 2詞法分析器的設(shè)計(jì)與實(shí)現(xiàn) 3 2 1單詞與屬性字1 單詞單詞是語(yǔ)言中具有獨(dú)立意義的最小語(yǔ)法單位 要素獨(dú)立的意義最小的語(yǔ)法單位 5 例 A B 單詞是 A 和 B intint1 單詞是 int 和 int1 A B 單詞是 A 和 B 復(fù)習(xí) 流行語(yǔ)言詞法規(guī)則的表示 BNF或EBNF 3型文法 正規(guī)式例 int float for include char V 6 1 關(guān)鍵字 保留字或基本字 關(guān)鍵字一般是語(yǔ)言系統(tǒng)本身定義的 通常是由字母組成的字符串 7 2 標(biāo)識(shí)符 用來(lái)表示各種名字如 變量名 數(shù)組名 結(jié)構(gòu)名 函數(shù)名 文件名等 3 2 1單詞與屬性字 3 常數(shù) 256 3 14 true abc 4 運(yùn)算符 如 等等5 分界符 如逗號(hào) 分號(hào) 括號(hào) 單雙引號(hào)等 8 3 2 1單詞與屬性字 3 2 1單詞與屬性字 注意 1 同一個(gè)字符開頭 后續(xù)字符 跨多個(gè)單詞類 9 2 非單詞成分和預(yù)處理成分 例 源程序注釋 預(yù)處理指令 define include 3 2 1單詞與屬性字 2 屬性字對(duì)所識(shí)別的單詞的數(shù)據(jù)結(jié)構(gòu)表示 L1 T C 屬性字 10 刻畫單詞類別 單詞性質(zhì) 如 標(biāo)識(shí)符 運(yùn)算符 單詞的內(nèi)碼值 可空 TokenCode 說(shuō)明 11 單詞類別通常用整數(shù)編碼單詞類別提供給語(yǔ)法分析程序使用單詞符號(hào)屬性信息記錄單詞符號(hào)的特征或特性單詞的屬性值提供給語(yǔ)義分析程序使用編碼形式 一類一種 關(guān)鍵字 標(biāo)識(shí)符 常數(shù) 運(yùn)算符 界符一字一種 關(guān)鍵字 運(yùn)算符 分界符各一碼 例題 一類一種 intx 10 y 12 注 通常將標(biāo)識(shí)符的屬性放在符號(hào)表中 因此常把指向存放標(biāo)識(shí)符有關(guān)信息的符號(hào)表入口的指針作為標(biāo)識(shí)符的屬性值 13 源程序經(jīng)詞法分析器的輸出 while id 指向i的符號(hào)表入口的指針 relational op id 指向j的符號(hào)表入口的指針 do if id 指向i的符號(hào)表入口的指針 id 指向j的符號(hào)表入口的指針 while i j do if i j then i i j else j j i 例題 一字一種 3 2 2源程序的輸入與預(yù)處理 1 輸入緩沖區(qū)成對(duì)且對(duì)半互補(bǔ)的輸入緩沖區(qū)模式 即將一個(gè)緩沖區(qū)分為兩個(gè)半?yún)^(qū) 每個(gè)半?yún)^(qū)長(zhǎng)度為n n一般為磁盤塊或簇長(zhǎng)的整倍數(shù) 其結(jié)構(gòu)如圖所示 14 n 取2的整次冪 每個(gè)半?yún)^(qū)的末尾設(shè)置標(biāo)志 eof 表示讀入該半?yún)^(qū)的源程序的結(jié)束 B 單詞w開始指針 F 掃描w的指針 兩半?yún)^(qū)互補(bǔ)功能算法 if F 前 eof 重新分配 裝入后半?yún)^(qū) F elseif F 后 eof 重新分配 裝入前半?yún)^(qū) F 1 elseF 15 2 兩個(gè)緩沖區(qū)的輸入模式 控制線數(shù)據(jù)線X 固定長(zhǎng)度的存儲(chǔ)空間 16 預(yù)處理程序 作用 1 減少內(nèi)存空間占用 2 減輕掃描器實(shí)質(zhì)性處理的負(fù)擔(dān) 預(yù)處理程序主要任務(wù) 1 濾掉源程序中的非單詞成分 如無(wú)用空格 換行符等 2 實(shí)際的預(yù)處理工作 17 濾掉注釋 宏替換 文件包含的嵌入 條件編譯的嵌入 設(shè)計(jì)工具 FA作為掃描器的狀態(tài)轉(zhuǎn)換圖的構(gòu)造 step1 對(duì)語(yǔ)言的各類單詞分別構(gòu)造狀態(tài)圖 step2 將各類狀態(tài)圖合并 構(gòu)成一個(gè)能識(shí)別該語(yǔ)言所有單詞的狀態(tài)圖 18 1 將各類單詞的狀態(tài)圖的初態(tài)合并為一個(gè)惟一初態(tài) 2 調(diào)整沖突編號(hào) 例3 2設(shè)某語(yǔ)言由標(biāo)識(shí)符和無(wú)符號(hào)正整數(shù)兩類單詞構(gòu)成 標(biāo)識(shí)符和無(wú)符號(hào)正整數(shù)的詞法規(guī)則 L a b z A B ZD 0 1 9 L L D DD 19 step1 對(duì)語(yǔ)言的各類單詞分別構(gòu)造狀態(tài)圖 20 其中 other表示非L D 字符 其中 other表示非D字符 step1 step2 將各類狀態(tài)圖合并 構(gòu)成一個(gè)能識(shí)別該語(yǔ)言所有單詞的狀態(tài)圖 21 其中 other表示非L D 字符 其中 other表示非D字符 step2 4 5 詞法分析方法 直接分析法 例 設(shè)C語(yǔ)言子集由下列單詞符號(hào)構(gòu)成 以正規(guī)式的形式表示 關(guān)鍵字 int if for標(biāo)識(shí)符 字母 字母 數(shù)字 無(wú)符號(hào)整常數(shù) 數(shù)字 數(shù)字 運(yùn)算符或分界符 22 23 24 25 26 語(yǔ)言詞法規(guī)則狀態(tài)轉(zhuǎn)換圖 FA 可行的掃描器存儲(chǔ)和激活問(wèn)題 數(shù)據(jù)中心法程序中心法 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)之一 數(shù)據(jù)中心法將狀態(tài)轉(zhuǎn)換圖看成一種數(shù)據(jù)結(jié)構(gòu) 狀態(tài)矩陣表 用總控程序控制輸入的源程序串在其上運(yùn)行 27 狀態(tài)矩陣二級(jí)目錄表主表 數(shù)據(jù)項(xiàng) 狀態(tài) 分表地址或子程序入口狀態(tài) 終態(tài)時(shí) 分表地址為子程序入口狀態(tài) 非終態(tài)時(shí) 為分表入口2 分表 數(shù)據(jù)項(xiàng) 當(dāng)前輸入字符 轉(zhuǎn)換狀態(tài) 主表分表 28 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)之二 程序中心法 將狀態(tài)轉(zhuǎn)換圖看成一個(gè)流程圖 從初態(tài)開始對(duì)它的每個(gè)節(jié)點(diǎn) 狀態(tài) 編寫一函數(shù)或直接跟蹤狀態(tài)圖從初態(tài)開始的轉(zhuǎn)換完成所有分支的跟蹤來(lái)編寫程序 例3 5設(shè)單一小寫字母或單一數(shù)字或 為合法單詞 表示它們的狀態(tài)轉(zhuǎn)換圖如圖所示 29 charchar1 char1 nextchar if state i switch char1 case a z J chartype char1 break case 0 9 K chartype char1 break case L chartype char1 break default error 其中 J K L為狀態(tài)j k l所對(duì)應(yīng)的函數(shù) nextchar 為一函數(shù) 功能是從當(dāng)前掃描的源程序讀取下一個(gè)字符 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) intstate 0 enumlettet a z enumnumber 0 9 charchar1 while 1 char1 nextchar switch state case0 switch char1 case a z state 1 break 0 9 state 3 break casecase state 5 break case state 6 break case state 7 break case state 11 break case state 12 break default state 13 break 31 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) case1 while char1 letter number char1 nextchar state 2 break case2 untread return 02 value orreturn 01 value break 函數(shù)untread 功能是回退一個(gè)已讀進(jìn)的字符 屬性01表示關(guān)鍵字 屬性02表示標(biāo)識(shí)符 case3 while char1 number char1 nextchar state 4 break case4 untread return 03 value break 屬性03表示無(wú)符號(hào)整常數(shù) case5 return 04 break 屬性04表示 case6 return 05 break 屬性05表示 32 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) case7 char1 nextchar if char1 state 9 elseif char1 state 10 elsestate 8 break case8 untread return 08 break 屬性08表示 case9 return 09 break 屬性09表示 case10 return 12 break 屬性12表示 case11 return 10 break 屬性10表示 case12 return 11 break 屬性11表示 case13 error error是語(yǔ)法錯(cuò)處理函數(shù) 33 一 自動(dòng)生成思想 一個(gè)詞法分析程序產(chǎn)生器它接收用正規(guī)式表示的定義在某語(yǔ)言字母表 上的單詞 然后從此正規(guī)式出發(fā) 1 構(gòu)造能識(shí)別正規(guī)式描述的單詞集 正規(guī)集 的非確定有限自動(dòng)機(jī)NFAM 此步構(gòu)造算法定義為X 2 用子集法 子集法實(shí)現(xiàn)算法命名為Y 將M 確定化 得到與其等價(jià)的DFAM 3 用劃分算法 命名為Z 對(duì)M化簡(jiǎn) 得到DFAM 則這個(gè)DFAM 即是理論上的掃描器 34 LEX運(yùn)行與應(yīng)用過(guò)程 35 二 用LEX建立詞法分析程序的過(guò)程 LEX編譯器 LEX源程序lex 1 語(yǔ)言x的詞法分析器 LEX編譯器接收LEX源程序 由LEX編譯器處理LEX源程序 產(chǎn)生一個(gè)詞法分析器作為輸出 在UNIX環(huán)境中 LEX編譯器的輸出是一個(gè)具有標(biāo)準(zhǔn)文件lex yy c的C程序 經(jīng)過(guò)C編譯器的編譯產(chǎn)生a out文件 a out是一個(gè)實(shí)際可以運(yùn)行的詞法分析器 練習(xí) 例 設(shè)有識(shí)別C語(yǔ)言 的NFA如下 36 例 設(shè)有識(shí)別C語(yǔ)言 的NFA如下 37 0123