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

《《編譯原理》第三章詞法分析.ppt》由會員分享，可在線閱讀，更多相關《《編譯原理》第三章詞法分析.ppt（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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