西安電子科技大學(xué)《編譯原理》.ppt

《西安電子科技大學(xué)《編譯原理》.ppt》由會員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)《編譯原理》.ppt（25頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1 第二章詞法分析 詞法分析 x y z 60 0 id1 id2 id3 60 0 詞法的雙重含義 規(guī)定單詞形成的規(guī)則 也被稱為構(gòu)詞規(guī)則或詞法規(guī)則 它的作用相當(dāng)于立法 規(guī)定什么樣的輸入序列是語言所允許的合法單詞 根據(jù)構(gòu)詞規(guī)則識別輸入序列 也被稱為詞法分析 它的作用相當(dāng)于執(zhí)法 根據(jù)規(guī)則識別出合法的單詞和指出非法的輸入序列 本章主要內(nèi)容 與詞法分析有關(guān)的基本概念和相關(guān)問題模式的形式化描述 正規(guī)式記號的識別 有限自動機(jī) NFA DFA 詞法分析器的構(gòu)造 從正規(guī)式到DFA上機(jī)作業(yè) 第一部分 函數(shù)繪圖語言的詞法分析器 2 2 1詞法分析中的若干問題2 1 1記號 模式與單詞 單詞的基本分類 關(guān)鍵字 保留字 kw keyword 標(biāo)識符id identifier 字面量literal特殊符號ks keysymbol orspecialsymbol 例2 1語句position initial rate 60idksidksidksnumber注意 稱識別出id而不是rate或initial 問題 根據(jù)什么識別這些詞法的基本單位 詞法元素 3 2 1 1記號 模式與單詞 續(xù)1 三個(gè)術(shù)語 模式 patten 產(chǎn)生和識別元素的規(guī)則記號 token 按照某個(gè)模式 或規(guī)則 識別出的元素 一組 單詞 lexeme 被識別出的元素自身的值 一個(gè) 也稱為詞值 記號的類別單詞舉例模式的非形式化描述const 01 constconstif 03 ififrelation 81 或 或 id 82 pi count D2字母打頭的字母數(shù)字串num 83 3 1416 0 6 02E23任何數(shù)值常數(shù)literal 84 coredumped 雙引號之間的任意字符串Comment xisaninteger 括號之間的任意字符串 返回 4 2 1 2記號的屬性 記號是按照某個(gè)模式識別出的元素 再考察賦值句position initial rate 60position initial和rate均為標(biāo)識符 即它們的種類均是id 問題 當(dāng)識別出一個(gè)id時(shí) 如何判定是哪個(gè)id 同樣 當(dāng)識別出一個(gè)relations時(shí) 究竟是 還是25由三個(gè)記號組成 類別屬性 828183 mycount 525 記號的類別單詞舉例記號的非形式化描述if 03 ififrelation 81 或 或 id 82 pi count D2字母打頭的字母數(shù)字串 注意 5與25的區(qū)別 根據(jù)記號的類別 25與 25 的區(qū)別 如何區(qū)別 5 2 1 3詞法分析器的作用與工作方式 特征 任務(wù) 編譯器中唯一與源程序打交道的部分 濾掉源程序中的無用成分 如注釋 空格 回車等處理與具體平臺有關(guān)的輸入 如文件結(jié)束符的不同表示等 識別記號 并交給語法分析器 根據(jù)模式識別記號調(diào)用符號表管理器或出錯(cuò)處理器 進(jìn)行相關(guān)處理 工作方式 單獨(dú)一遍掃描 作為語法分析器的子程序 并行方式 6 2 2模式的形式化描述2 2 1字符串與語言 從詞法分析的角度看程序設(shè)計(jì)語言 它是由記號組成的集合 從本章開始 我們用定義的方式表示一些重要的概念 目的是希望同學(xué)們深刻理解并牢固記憶這些基本概念 由于不同的教材 或出版物 對相同的概念有不同的稱謂 因此希望同學(xué)們掌握概念的實(shí)質(zhì) 而不是死記幾個(gè)名詞術(shù)語 定義2 1語言L是有限字母表 上有限長度字符串的集合 字母表是組成字符串的所有字符的集合 換句話說 字符串中的所有字符取自字母表 定義中強(qiáng)調(diào)兩個(gè)有限 因?yàn)橛?jì)算機(jī)的表示能力有限 字母表是有限的 即字母表中元素是有限多個(gè) 字符串的長度是有限的 即字符串中字符個(gè)數(shù)是有限多個(gè) 由于字符串的有序性 使得以字符串作為元素的集合 與一般意義下的集合有所不同 反映在集合運(yùn)算上 強(qiáng)調(diào)了有序 7 字符串的基本概念 表2 2 2 2 1字符串與語言 續(xù)1 表示 術(shù)語 S S1S2SnS的前綴XS的后綴XS的子串XS的真前綴 真后綴 真子串S的子序列X 舉例 abc 3 0 abc def abcdef abc 3 abcabcabc abc 的前綴可以是 a ab abc abc 的前綴可以是 c bc abc abc 的子串可以是 a b c abc 的真前綴可以是 a ab abdf 是 abcdef 的一個(gè)子序列 S中去掉0或若干個(gè)不一定連續(xù)的字符后形成的字符串 8 字符串集合的運(yùn)算 表2 3 2 2 1字符串與語言 續(xù)2 表示 術(shù)語 X L MX L MX LMX L X L 意義空集合 即元素個(gè)數(shù)為0的集合空串作為唯一元素的集合X是集合L和M的并 X s s Lors M X是集合L和M的交 X s s Lands M X是集合L和M的連接 X st s Landt M X是集合L的 星 閉包 X L0 L1 L2 X是集合L的正閉包 X L1 L2 L3 若L a b M c d 則LM ac bc ad bd L a b aa bb ab ba aaa L a b aa bb ab ba aaa 9 2 2 2正規(guī)式與正規(guī)集 定義2 2令 是一個(gè)有限字母表 則 上的正規(guī)式及其表示的集合遞歸定義如下 1 是正規(guī)式 它表示集合L 2 若a是 上的字符 則a是正規(guī)式 它表示集合L a a 3 若正規(guī)式r和s分別表示集合L r 和L s 則 a r s是正規(guī)式 表示集合L r L s b rs是正規(guī)式 表示集合L r L s c r 是正規(guī)式 表示集合 L r d r 是正規(guī)式 表示的集合仍然是L r 加括弧改變優(yōu)先級 結(jié)合性 可用正規(guī)式描述的語言稱為正規(guī)語言或正規(guī)集 運(yùn)算的優(yōu)先級與結(jié)合性若正規(guī)式優(yōu)先級和結(jié)合性做下述約定 1 三種運(yùn)算均具有左結(jié)合性質(zhì) 2 優(yōu)先級從高到低順序排列為 閉包運(yùn)算 連接運(yùn)算 或運(yùn)算 則正規(guī)式中不必要的括號可以被省略 例如 a b c 可以簡化成a b c 10 正規(guī)式的等價(jià)2 2 2正規(guī)式與正規(guī)集 續(xù)1 不同算術(shù)表達(dá)式可以表示同一個(gè)數(shù) 如3 5 5 3 2 6等均表示8 不同正規(guī)式也可以表示同一個(gè)正規(guī)集 即正規(guī)式與正規(guī)集之間是多對一的關(guān)系 定義2 3若正規(guī)式P和Q表示了同一個(gè)正規(guī)集 則稱P和Q是等價(jià)的 記為P Q 例2 3設(shè)字母表 a b c 則 上的部分正規(guī)式和正規(guī)集如下 正規(guī)式對應(yīng)正規(guī)集a b c a b c a b b a a b a b a a b a aa ab aba abb aab a為首的ab字符串 a b c aa ab ac ba bb bc abc 例2 4令L x a b L y c d 則L x y a b c d L y x a b c d 11 正規(guī)式等價(jià)的判定 證明 2 2 2正規(guī)式與正規(guī)集 續(xù)2 正規(guī)式的代數(shù)性質(zhì) 表2 4 r s s r rs t r st r s t r s t r r rr s t rs rtr r s t r sr trr r 利用正規(guī)式的等價(jià)性可以化簡復(fù)雜的正規(guī)式 正規(guī)式的等價(jià)性判定可以采用兩種方法 根據(jù)定義 證明不同的正規(guī)式表示同一集合 例2 4 根據(jù)下述正規(guī)式的代數(shù)性質(zhì)進(jìn)行運(yùn)算 12 2 2 3記號的說明 正規(guī)式可以嚴(yán)格地規(guī)定記號的模式 用正規(guī)式說明記號的公式為 記號 正規(guī)式可以讀作為 左邊 記號定義為 右邊 正規(guī)式 或者 記號是正規(guī)式 例如id a a b 可以讀作為 id定義為a a b 通常在不引起混淆的情況下 也把說明記號的公式簡稱為正規(guī)式 或者規(guī)則 例2 5記號relation id和num分別是Pascal的關(guān)系運(yùn)算符 標(biāo)識符和無符號數(shù) 它們的正規(guī)式表示如下所示 relation id a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 num 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 E 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 13 簡化正規(guī)式描述2 2 3記號的說明 續(xù)1 a 正閉包若r是表示L r 的正規(guī)式 則r 是表示 L r 的正規(guī)式 且下述等式成立 r rr r r r r 與 具有相同的運(yùn)算結(jié)合性和優(yōu)先級例如 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 可以化簡為 0 1 2 3 4 5 6 7 8 9 b 可缺省若r是正規(guī)式 則r 是表示L r 的正規(guī)式 且下述等式成立 r r 也可以與 具有相同的運(yùn)算結(jié)合性和優(yōu)先級注意 引入算符 的主要目的是為了回避不可以直接通過鍵盤輸入的字符 例如 E 可以改寫為 E 14 2 2 3記號的說明 續(xù)2 c 字符組若r是僅由 運(yùn)算構(gòu)成的正規(guī)式 則可改寫為 r 其中r 可以有如下兩種形式 枚舉 如 abc 它等價(jià)于a b c分段 如 0 9a z 它等價(jià)于 0123456789abcdefghijklmnopqrstuvwxyz d 非字符組若 r 是一個(gè)字符組形式的正規(guī)式 則 r 是表示 L r 的正規(guī)式 例如 若 a b c d e f g 則L abc d e f g 引入輔助定義輔助定義的形式與正規(guī)式一樣 因?yàn)樗旧硪彩且粋€(gè)正規(guī)式 但它不與任何模式匹配 換句話說 作為輔助定義的正規(guī)式僅供內(nèi)部使用 而不用于說明記號 15 2 2 3記號的說明 續(xù)3 例2 6引入正規(guī)式的縮寫形式和輔助定義式后 id和num的正規(guī)定義式可重寫如下 char a zA Z digit 0 9 digits digit optional fraction digits optional exponent E digits id char char digit num digitsoptional fractionoptional exponent 對比 id a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 num 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 E 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 16 2 3記號的識別 有限自動機(jī) 模式的描述 正規(guī)式記號的識別 有限自動機(jī) 確定 不確定 2 3 1不確定的有限自動機(jī) NondeterministicFiniteAutomaton NFA 定義2 4NFA是一個(gè)五元組 5 tuple M S move s0 F 其中 1 S是有限個(gè)狀態(tài) state 的集合 2 是有限個(gè)輸入字符 包括 的集合 3 move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù) move si ch sj表示 當(dāng)前狀態(tài)si下若遇到輸入字符ch 則轉(zhuǎn)移到狀態(tài)sj 4 s0是唯一的初態(tài) 也稱開始狀態(tài) 5 F是終態(tài)集 也稱接受狀態(tài)集 它是S的子集 包含了所有的終態(tài) 17 直觀的表示方式2 3 1不確定的有限自動機(jī) 續(xù)1 狀態(tài)轉(zhuǎn)換圖 用一個(gè)有向圖來直觀表示NFA NFA中的每個(gè)狀態(tài) 對應(yīng)轉(zhuǎn)換圖中的一個(gè)節(jié)點(diǎn) NFA中的每個(gè)move si a sj 對應(yīng)轉(zhuǎn)換圖中的一條有向邊 它表示從si節(jié)點(diǎn)出發(fā) 進(jìn)入sj節(jié)點(diǎn) 字符a 或 是邊上的標(biāo)記 狀態(tài)轉(zhuǎn)換矩陣 用一個(gè)二維數(shù)組來直觀表示NFA 矩陣中 一個(gè)狀態(tài)對應(yīng)一行 一個(gè)字符對應(yīng)一列 每個(gè)矩陣元素M si a 中的內(nèi)容 是從狀態(tài)si出發(fā) 經(jīng)字符a 或 所到達(dá)的下一狀態(tài)sj 在轉(zhuǎn)換矩陣中 一般以矩陣第一行所對應(yīng)的狀態(tài)為初態(tài) 而終態(tài)需要特別指出 18 不確定的有限自動機(jī) 續(xù)2 例2 7識別正規(guī)式 a b abb所描述正規(guī)集的NFA的三種表示形式分別如下 其中 轉(zhuǎn)換矩陣表示中0為初態(tài) 3為終態(tài) 按定義 S 0 1 2 3 a b s0 0 F 3 move move 0 a 0 move 0 a 1 move 0 b 0 move 1 b 2 move 2 b 3 記號在NFA中的表現(xiàn) NFA如何識別記號 對字符串 從初態(tài)開始 經(jīng)過一系列狀態(tài)轉(zhuǎn)移 最后到達(dá)終態(tài) 例如 對于字符串a(chǎn)bb 有定義 move 0 a 1 move 1 b 2 move 2 b 3轉(zhuǎn)換矩陣 m 0 a 0 1 m 1 b 2 m 2 b 3轉(zhuǎn)換圖 0a1b2b3顯然 轉(zhuǎn)換圖最直觀 即每一個(gè)記號 實(shí)質(zhì)上是從初態(tài)開始到某個(gè)終態(tài)的路徑上的標(biāo)記 19 不確定的有限自動機(jī) 續(xù)3 例2 8識別表2 1中記號relation id和num的轉(zhuǎn)換圖 20 NFA 識別記號 的特點(diǎn)不確定的有限自動機(jī) 續(xù)4 NFA識別記號的最大特點(diǎn)是它的不確定性 即在當(dāng)前狀態(tài)下對同一字符有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移 不確定性的表現(xiàn)定義 move函數(shù)是1對多的 轉(zhuǎn)換圖 同一狀態(tài)有多于一條邊標(biāo)記相同字符轉(zhuǎn)移到不同的狀態(tài) 轉(zhuǎn)換矩陣 M si a 是一個(gè)狀態(tài)的集合 按定義 S 0 1 2 3 a b s0 0 F 3 move move 0 a 0 move 0 a 1 move 0 b 0 move 1 b 2 move 2 b 3 21 NFA識別輸入序列的一般方法確定的有限自動機(jī) 續(xù)5 反復(fù)試探所有路徑 直到到達(dá)終態(tài) 或者到達(dá)不了終態(tài) 不確定性識別記號的困惑識別輸入序列時(shí) 在當(dāng)前狀態(tài)下遇到同一字符 應(yīng)轉(zhuǎn)移到哪個(gè)下一狀態(tài) 例2 9在正規(guī)式 a b abb的NFA上識別輸入序列abb和abab 非終態(tài) 不接受 試探下一路徑 終態(tài) 接受 NFA識別記號存在的問題 a 只有嘗試了全部可能的路徑 才能確定一個(gè)輸入序列不被接受 而這些路徑的條數(shù)隨著路徑長度的增長成指數(shù)增長 b 識別過程中需要進(jìn)行大量回溯 時(shí)間復(fù)雜度升高且算法趨于復(fù)雜 22 2 3 2確定的有限自動機(jī) DeterministicFiniteAutomaton DFA 問題 是否可以構(gòu)造這樣的有限自動機(jī) 它識別正規(guī)式所描述的字符串 且在任何一個(gè)終態(tài)下遇到同一字符最多有一個(gè)終態(tài)轉(zhuǎn)移 定義2 5DFA是NFA的一個(gè)特例 其中 1 沒有狀態(tài)具有 狀態(tài)轉(zhuǎn)移 transition 即狀態(tài)轉(zhuǎn)換圖中沒有標(biāo)記 的邊 2 對每一個(gè)狀態(tài)s和每一個(gè)字符a 最多有一個(gè)下一狀態(tài) 與NFA相比 DFA的特征 確定性 定義 move si a 函數(shù)是1對1的 轉(zhuǎn)換圖 從一個(gè)節(jié)點(diǎn)出發(fā)的邊上標(biāo)記均不相同 轉(zhuǎn)換矩陣 M si a 是一個(gè)狀態(tài) 且字母表不包括 實(shí)質(zhì)上 DFA是通過對NFA施加兩條限制形成的 正是這兩條限制消除了NFA的不確定性 23 2 3 2確定的有限自動機(jī) 續(xù)1 限制1 沒有 狀態(tài)轉(zhuǎn)移限制2 同一狀態(tài)下沒有重復(fù)字符的狀態(tài)轉(zhuǎn)移 例2 10正規(guī)式 a b abb的DFA和識別輸入序列abb和abab的過程 識別abb 0a1b2b3 狀態(tài) 接受識別abab 0a1b2a1b2 將在DFA上識別輸入序列的過程形式化為算法 該算法被稱為模擬器 模擬DFA的行為 或驅(qū)動器 用DFA的數(shù)據(jù)驅(qū)動分析動作 算法與DFA一起 即構(gòu)成識別記號的詞法分析器的核心 它的最大特點(diǎn)是算法與模式無關(guān) 僅DFA與模式相關(guān) 24 算法2 1模擬DFA2 3 2確定的有限自動機(jī) 續(xù)2 s s0 ch nextchar whilech eofloops move s ch ch nextchar endloop ifsisinFthenreturn yes elsereturn no endif 用算法2 1識別abb 1 s 0 ch a2 s 1 ch b3 s 2 ch b4 s 3 ch eof5 yes 用算法2 1識別abab 1 s 0 ch a2 s 1 ch b3 s 2 ch a4 s 1 ch b5 s 2 ch eof6 no 輸入DFAD和輸入字符串x eof D的初態(tài)為s0 終態(tài)集為F 輸出若D接受x 回答 yes 否則回答 no 方法用下述過程識別x 25 2 3 3有限自動機(jī)的等價(jià) 定義2 6若有限自動機(jī)M和M 識別同一正規(guī)集 則稱M和M 是等價(jià)的 記為M M 特別提示 正規(guī)式與有限自動機(jī)從兩個(gè)側(cè)面表示正規(guī)集 正規(guī)式是描述 自動機(jī)是識別 因此 當(dāng)它們表示相同的集合時(shí) 均存在等價(jià)的問題 想一想 有幾種可能的等價(jià)