1、1,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 蔣凌云 教材：編譯技術(shù)原理及其實(shí)現(xiàn)方法王汝傳 編著,編 譯 原 理 Compiler Principles,2,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文

2、法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,3,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正

3、規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言L

4、EX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,4,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,5,3.1 引 言經(jīng)過第一章的學(xué)習(xí)，我們已經(jīng)初步了解了編譯過程及各階段的功能，從本章開始我門將詳細(xì)敘述各階段是如何工作的。首先來看一下詞法分析，這是編譯的第一步，也是編譯的重點(diǎn)，

5、下面我們將將詳細(xì)介紹詞法分析的方法。,源程序,詞法 分析 程序,語法 分析 程序,語義 分析 程序,中間 代碼 生成,代碼 優(yōu)化 程序,目標(biāo) 代碼 生成,目標(biāo)程序,信 息 表 管 理 程 序,錯 誤 檢 查 和 處 理 程 序,6,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,7,3.1

6、 引言 一、詞法分析基本思想 掃描源程序 識別單詞 變成中間程序L1（內(nèi)部編碼）。 即從左到右逐個字符地掃描源程序，產(chǎn)生一個個獨(dú)立的單詞， 并將其改變成等價的中間程序，記為：L1。實(shí)際上是機(jī)器的 內(nèi)部編碼,符號序列,單詞序列,詞 法 分 析,8,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣

7、法,9,3.1 引 言 二、詞法分析任務(wù) 1. 識別單詞 掃描源程序的一個個字符，按照語言的詞法規(guī)則，識別出各類有獨(dú)立意義的單詞。 如：begin ， procedure ， + ， 5.43 ， abc等。,10,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,11,3.1 引 言 二、

8、詞法分析任務(wù) 2. 消除無用字符 對源程序文本進(jìn)行處理，消除源程序文本中的注釋、空格、換行符以及其他一切對語法分析和代碼生成均無關(guān)的信息。,12,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,13,3.1 引 言 二、詞法分析任務(wù) 3. 變成內(nèi)部編碼 將長度不一、種類不同的單詞變成長度統(tǒng)

9、一、格式規(guī)整、分類清晰的一種內(nèi)部機(jī)器碼表示。,14,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,15,3.1 引 言 二、詞法分析任務(wù) 4. 建立各種表格 在詞法分析時，可以根據(jù)單詞特點(diǎn)建立不同表格，如： 名字表（標(biāo)識符表）：源程序中的標(biāo)識符集中在表中 常數(shù)表 數(shù)組向量表、過程表等 界

10、限表：包含了保留字、運(yùn)算符等,16,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,17,3.1 引 言 二、詞法分析任務(wù) 5. 分配存貯單元（靜態(tài)變量） 對簡單變量、常量及數(shù)組進(jìn)行靜態(tài)存貯分配 靜態(tài)存貯分配：在編譯時就可以決定應(yīng)分配內(nèi)存的大小。 動態(tài)存貯分配：到運(yùn)行時才進(jìn)行的存貯分配。

11、如：變界數(shù)組、動態(tài)變量。 靜態(tài)存貯分配可以在詞法分析階段進(jìn)行，也可以在語法分析階段進(jìn)行，隨具體編譯系統(tǒng)而定。,18,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,19,3.1 引 言 二、詞法分析任務(wù) 6. 進(jìn)行詞法檢查 將一些單詞錯誤檢查出來， 如保留字PROGRAM、 VAR； 又例

12、如變量是否有說明或是否重復(fù)說明等。,20,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,21,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)

13、行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,22,3.1 引 言 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 在多遍掃描的編譯程序中，詞法分析可以單獨(dú)作為一遍掃描來完成，此時可將詞法分析程序的輸出放在一個中間文件上，語法分析程序可以從該文件上取得它的輸入。 詞法分析從語法分析獨(dú)立出來的原因： （1）便于集中進(jìn)行語法分析 （2）便于建立有效詞法分析技術(shù) （3）將給語法分析提供更多更詳細(xì)信息,字符串表示 的源程序,詞法分析程序,符號串表示的源程序,字符,單詞,23,第三

14、章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1. 識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,24,3.1 引 言 三、詞法分析方式 2. 將詞法分析程序編寫成一個獨(dú)立子程序 在一遍掃描的編譯程序中，往往將詞法分析編成語法分析的一個子程序，供語法分析時隨時調(diào)用，每調(diào)用一次，則從源程序字符串中讀出一個具有獨(dú)立意義的單詞。,優(yōu)點(diǎn)：不需要在內(nèi)存

15、中構(gòu)造和保留中間文件所以節(jié)省內(nèi)存容量,字符串表示 的源程序,詞法分析程序,語法分析程序,字符,取一單詞,返 回,25,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1.識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,26,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1.識別單詞 2. 消除無用字符 3. 變

16、成內(nèi)部編碼 4. 建立各種表格 5. 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,27,3.1 引 言 三、詞法分析方法 1. 直接分析方法 根據(jù)詞法分析任務(wù)編成多個不同獨(dú)立子程序（如：讀符號子 程序、取單詞子程序、拼標(biāo)識符子程序、處理無符號數(shù)子程 序），對源程序進(jìn)行分析加工處理。,28,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 1.識別單詞 2. 消除無用字符 3. 變成內(nèi)部編碼 4. 建立各種表格 5.

17、 分配存貯單元（靜態(tài)變量） 6. 進(jìn)行詞法檢查 三、詞法分析方式 1. 將詞法分析和語法分析程序分開 2. 將詞法分析程序編寫成一個獨(dú)立子程序 四、詞法分析方法 1. 直接分析方法 2. 狀態(tài)矩陣法,29,3.1 引 言 三、詞法分析方法 2. 狀態(tài)矩陣法 根據(jù)一張二維狀態(tài)矩陣表對源程序進(jìn)行控制分析。,30,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序

18、的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,31,第三章 詞 法 分 析,3

19、.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)

20、表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,32,第三章 詞 法 分 析,3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 1 . 單詞類別 2. 單詞自身值,33,第三章 詞 法 分 析,3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 1 . 單詞類別 2. 單詞自身值,34,3.2 單詞的內(nèi)部編碼 一、單詞 這部分內(nèi)容在第一章中已介紹，在此簡單回顧一下。 所謂單詞，是指那些具有獨(dú)立含義的最小語法單位 。單詞

21、可分為以下 幾種類型： （）保留字：PROGRAM, VAR, IF, FOR, AND等 。 （）標(biāo)識符：是用戶選來表示常量、變量、類型、過程等名字。 （ 3 ）常數(shù)：分為整型、實(shí)型、布爾型、字符型等，如2，3.1416等。 （）運(yùn)算符：分為算術(shù)運(yùn)算符（，*，等），邏輯運(yùn)算符 （，），關(guān)系運(yùn)算符（=）等。 （）界限符：如逗號、分號、括號等。,35,第三章 詞 法 分 析,3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 1 . 單詞類別 2. 單詞自身值,36,對于單詞類別可以用整數(shù)表示，用來指示單詞的種類 。例如上面的例子，我們可以用個不同的整數(shù)作為它們單詞類別的編碼 。單詞的內(nèi)部編碼是詞法

22、分析的輸出形式,3.2 單詞的內(nèi)部編碼 二、內(nèi)部編碼 1 . 單詞類別,單詞類型,單詞自身值,37,3.2 單詞的內(nèi)部編碼 二、內(nèi)部編碼 2. 單詞自身值 可以是單詞某種形式內(nèi)部編碼，也可以是該單詞在某些表格中地址碼。如第一章所講，保留字、運(yùn)算符和界限符用內(nèi)部固定編碼值作為單詞值；標(biāo)識符取其在標(biāo)識符表中的地址碼 ；常量取其在常數(shù)表中的地址碼。 例如：有下列單詞： 單詞 內(nèi)部編碼 單詞 內(nèi)部編碼 IF 002 + 025 THEN 003 * 026 ELSE 004 034,38,單詞 內(nèi)部編碼 （ 035 ） 036 ：= 037 單詞 地址碼 a1 200 b1 201 c1 202 d1

23、 203 b 204 0 100 3 101,語句：if a10 then b1:=(c1+3) else b:=0 經(jīng)詞法分析變成如下的內(nèi)部編碼形式： If a1 0 then b1 := ( C1 + 3 ) else b := 0,1 002,2 200,4 034,3 100,1 003,2 201,5 037,5 035,2 202,4 024,3 101,5 036,1 004,2 204,5 037,3 102,39,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3

24、.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自

25、動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,40,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四

26、、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,41,第三章 詞 法 分 析,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,42,第三章 詞 法 分

27、析,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,43,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 在介紹詞法分析程序的設(shè)計(jì)之前，先來看一下正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 它們是詞法分析的理論基礎(chǔ)。 一、正規(guī)文法 正規(guī)文法就是喬姆斯基(Chomsky)文法分類中的3型文法，如果P中 規(guī)則形式為 ： A=a B 或 A=a 其中A,BVN，aVT，則稱文法G為右線性文法。如P中規(guī)則形式為: A=B a 或 A=a，則稱文法G為左線性文法 。 3型文法與詞法分析密切相關(guān)

28、 如： =字母|字母|數(shù)字 左線性文法 又如：=+|-|*|/ 正規(guī)文法,44,第三章 詞 法 分 析,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,45,第三章 詞 法 分 析,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,46,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 轉(zhuǎn)換圖實(shí)際上是一個有限方向圖，

29、圖中結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。 狀態(tài)之間用箭弧連接，箭弧上標(biāo)記（字符如x，y）代表射出結(jié)（即箭 弧始結(jié)）狀態(tài)下可能出現(xiàn)的輸入字符 . 如：,該狀態(tài)轉(zhuǎn)換圖表示在狀態(tài)1下讀入x轉(zhuǎn)到狀態(tài)2，若在狀態(tài)1下讀入字符y，則轉(zhuǎn)到狀態(tài)3。,1,X,2,3,Y,47,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 二、狀態(tài)轉(zhuǎn)換圖 2. 功能 一個狀態(tài)轉(zhuǎn)換圖可以用于識別（或接受）一 定的字符串。例如：識別標(biāo)識符的轉(zhuǎn)換圖如 下圖所示,0,字母,字母或數(shù)字,其他,*,1,48,其中為初態(tài)，為終態(tài)（雙圓圈表示）。 這個轉(zhuǎn)換圖識別（接受）標(biāo)識符過程是： （1）從初態(tài)開始，若在狀態(tài)之下輸入字符是一個字母則轉(zhuǎn)入狀態(tài)。 （2）在狀態(tài)之下，若下一

30、個輸入字符為字母或數(shù)字，則讀進(jìn)它，并重新 進(jìn)入狀態(tài)1。 （3） 重復(fù)（2），直到狀態(tài)發(fā)現(xiàn)輸入字符不再是字母或數(shù)字時就進(jìn)入 狀態(tài)。狀是終態(tài)，它意味著到此已識別出一個標(biāo)識符，識別 過程宣告終止。 終態(tài)結(jié)上打個星號，表示多讀進(jìn)一個不屬于標(biāo)識符的字符， 應(yīng)把它退還給輸入串。 （4） 如果在開始狀態(tài)0下，輸入字符不是字母，則意味著識別不出標(biāo)識符 按同樣的方法，同學(xué)們可以考慮一下整數(shù)的識別狀態(tài)轉(zhuǎn)換圖及識別過程,49,(1)= (2)= (3)= (4)=0 (5)=1 (6)=2 (7)=3 (8)=4 (9)=5 (10)=6 (11)=7 (12)=8 (13)=9,50,第三章 詞 法 分 析,3.

31、3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,51,第三章 詞 法 分 析,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 1. 定義 2. 功能 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1. 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞）,52,對于一個左線性文法GE ： U =a 或 U=Ba U,BVN ，aVT （1）設(shè)一個開始狀態(tài)S， SVN （2）對于每一條規(guī)則U =a ，從狀態(tài)S向狀態(tài)U畫一條箭弧，標(biāo)記為a a S U (3)

32、對于每一條規(guī)則U =Ba ，從狀態(tài)B向狀態(tài)U畫一條箭弧，標(biāo)記為a a B U (4) 識別符E為狀態(tài)轉(zhuǎn)換圖的終態(tài) 由以上規(guī)則，我們就可以構(gòu)造一個左線性文法狀態(tài)轉(zhuǎn)換圖。,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 1.由正規(guī)文法(左線性文法)構(gòu)造狀態(tài)轉(zhuǎn)換圖,53,例如：設(shè)有左線性文法（，）， 其中： ，U， ， U U 由該文法所確定的語言為 ， 根據(jù)上述構(gòu)造狀態(tài)轉(zhuǎn)換圖的規(guī)則，該文法狀態(tài)轉(zhuǎn)換圖如下圖所示。,54,3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 2. 由正規(guī)文法狀態(tài)轉(zhuǎn)換圖識別句子（單詞） 如：符號串0110是上述文法的句子，因?yàn)椋?從開始狀態(tài)S出發(fā)，讀入0轉(zhuǎn)入V

33、，再讀入1轉(zhuǎn)入Z，再讀入1轉(zhuǎn)入U，最后讀 入0轉(zhuǎn)入Z，且Z是終態(tài)。 又如：符號串101001也是該文法的一個句子。實(shí) 際上這是一個自底向上分析方法進(jìn)行分析。,由此可以看出正規(guī)文法的狀態(tài)轉(zhuǎn)換圖有助于識別正規(guī)文法產(chǎn)生的句子。,步驟 當(dāng)前狀態(tài) x的余留部分 1 S 101001 2 U 01001 3 Z 1001 4 U 001 5 Z 01 6 V 1 7 Z,識別字符串x=101001,句子101001語法樹,Z,V,1,Z,U,Z,U,0,0,1,0,1,55,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部

34、編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)

35、的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,56,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀

36、態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,57,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語

37、言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),58,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),59,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 1. 內(nèi)存比較大的情況下,直接輸入到內(nèi)存的一個源程序區(qū) (1)一個字符占一個字節(jié) (2)詞法分析程序從源程序區(qū)讀入字符 2. 內(nèi)存不足的情況下，將源程序以

38、文件的形式存貯在外部 介質(zhì)上，如磁盤、磁帶等 ?？梢韵仍趦?nèi)存中開辟一個 大小適宜的緩沖區(qū)，這個緩沖區(qū)稱為 輸入緩沖區(qū)。詞法 分析程序工作時，先從外部介質(zhì)上將輸入 符號串分批讀 入緩沖區(qū)，單詞符號的識別可在這個緩沖區(qū)中進(jìn)行.具 體處理時還要開辟一個掃描緩沖區(qū)。,60,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),61,第三章 詞 法 分 析,3.4 詞

39、法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),62,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 二、掃描緩沖區(qū)及預(yù)處理 1. 掃描緩沖區(qū) （1）定義：掃描緩沖區(qū)就是在內(nèi)存中開辟一部分單元，供識別 單詞用。 注意：掃描緩沖區(qū)和緩沖區(qū)是不同的，緩沖區(qū)是從 外存上讀入部分字符，而掃描緩沖區(qū)僅是為識別單詞用。 （2）工作原理 在掃描緩沖區(qū)中一般設(shè)兩個指示器，一個指向當(dāng)前正在識別 單詞開始位置，另一個用于

40、向前搜索尋找單詞的終點(diǎn)。不論 掃描緩沖區(qū)定為多大都不能保證單詞符號不會被它的邊界所打斷， 因此，掃描緩沖區(qū)最好使用如下所示的一分為二的區(qū)域（每半?yún)^(qū) 可容120個字符 ）： 掃描緩沖區(qū)1 掃描緩沖區(qū)2 起始指示器 搜索指示器,63,1) 開始時掃描緩沖區(qū)皆為空 。 2) 調(diào)用預(yù)處理子程序，將120個字符填滿掃描緩沖區(qū) 。并將兩個指示器指向掃描緩沖區(qū)的第個字符 。 3) 將搜索指示器向后移動,當(dāng)識別出一個單詞之后，搜索指示器已指向 下一個單詞的第一個字符,然后再將起始指示器移到搜索指示器指向 字符,接著搜索指示器又開始掃描第二個單詞。 當(dāng)搜索指示器越界時，說明緩沖區(qū)中的字符不足一個單詞，這時 再調(diào)

41、用預(yù)處理子程序，再將120個字符填滿掃描緩沖區(qū)，再將 搜索指示器掃描緩沖區(qū)第個字符。這樣，兩個掃描緩沖區(qū)交替 工作 。 4) 一般描緩沖區(qū)長度可以存放最長一個單詞，即可正常工作 ；否則， 就不能保證單詞符號不會被緩沖區(qū)邊界所打斷。 ,64,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 二、掃描緩沖區(qū)及預(yù)處理 2、預(yù)處理 預(yù)處理目的是將一些無用的空白符、跳格符、回車換行符等編輯性字符剔除掉 。 其工作原理是每次從緩沖區(qū)讀入一個字符后，便進(jìn)行判斷，如屬于無用字符則將其刪除不用，再讀下一個字符，直至讀出一個有用字符為止。,65,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及

42、預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),66,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),67,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 三、超前搜索 1、問題的提出,所謂超前讀字符（也稱超前

43、搜索或向前掃描），是指僅向前讀取字符，判別該字符是什么，不做別的處理工作。當(dāng)判明情況以后,再回過頭來處理已讀過的字符 。 如：某語句 ABCDE := 2,從A開始依次讀字符，直到E還不能判斷出標(biāo)識符ABCDE已結(jié)束，還需繼續(xù)讀下面的字符，當(dāng)發(fā)現(xiàn)E后字符既不是字母又不是數(shù)字時，才確定ABCDE為標(biāo)識符。 又如：如FORTRAN語言，只設(shè)關(guān)鍵字（如DO，IF，GOTO等），而無保留字。在語句中，關(guān)鍵字、標(biāo)號和標(biāo)識符之間，并無明顯的分界符，為了識別這些單詞，就要采用超前搜索的方法。 ,68,（）DO99K=1,10 （）DO99K=1.10 這兩個語句都是正確的語句。語句（）是語句，它是 以關(guān)鍵字

44、開頭。語句（）是賦值語句，它是以用戶自己定義的標(biāo)識符 K開頭的。 語句（）和（）區(qū)別在于等號之后第一個界限符，語句（）是逗號， 語句（）是句末號。對于語句（）和（）來說，盡管都以“”兩個 字符開頭，我們不能一見“”就認(rèn)定是語句。我們必須超前搜索，看 看是否有等號，如果有，再向前搜索，若下個界限符是逗點(diǎn)，則是關(guān)鍵 字，否則為非關(guān)鍵字，它只是用戶定義標(biāo)識符頭兩個字母。,例如有以下兩個語言的語句：,69,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 三、超前搜索 2. 工作原理 向前搜索由起始指示器和搜索指示器協(xié)同工作，搜索指示器一直向前搜索直到可以判斷單詞類別后在退回原來位置。 ,70,第三章 詞 法 分 析,

45、3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),71,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),72,3.4 詞法分析程序設(shè)計(jì)

46、與實(shí)現(xiàn) 四、由詞法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 .語言子集單詞符號 下表列出了這個語言所有單詞符號，以及它們種別編碼和內(nèi)部值。,基本符號 種別編碼 助記符 內(nèi)碼值 BEGIN 1 $BEGIN END 2 $END WHILE 3 $WHILE DO 4 $SEMI 標(biāo)識符 5 $ID 內(nèi)部字符串 整常數(shù) 6 $INT 標(biāo)準(zhǔn)二進(jìn)制形式 ; 7 $SEMT + 8 $PLUS * 9 $STAR := 10 $ASSIGN = 11 $LE 12 $LT : 13 $COLON,73,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 四、由詞法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 2. 單詞的正規(guī)文法規(guī)則 對于表.中的基本符號（單詞）可用下述正

47、規(guī)文法規(guī)則 (左線性）加以描述： 標(biāo)識符字母標(biāo)識符數(shù)字標(biāo)識符字母 整常數(shù)數(shù)字整常數(shù)數(shù)字 單分界符；* 雙分界符冒號小于號 冒號 ： 小于號 ,74,3. 構(gòu)造狀態(tài)轉(zhuǎn)換圖 （1）先構(gòu)造每一個單詞的狀態(tài)轉(zhuǎn)換圖。 例如 := 字母| 字母| 數(shù)字 按照前面所述規(guī)則 U:=a U:=Ba :=數(shù)字|數(shù)字,S,U,a,B,U,a,S,標(biāo)志符,字母,字母/數(shù)字,出口,其他符號,S,整常數(shù),數(shù)字,數(shù)字,出口,非數(shù)字,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖,75,（2）將所有單詞的狀態(tài)轉(zhuǎn)換圖合并成一張狀態(tài)轉(zhuǎn)換圖。,0,字母,1,3,8,11,字母或數(shù)字,*,*,*,*,非字母或數(shù)字,非

48、數(shù)字,非,非,數(shù)字,數(shù)字,;,+,*,:,其他,76,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),77,第三章 詞 法 分 析,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 1、掃描緩沖區(qū) 2、預(yù)處理 三、超前搜索 1、問題的提出 2、工作原理 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 1、語言子集單詞符號 2、單詞的正規(guī)文法規(guī)則 3

49、、構(gòu)造狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),78,3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 五、詞法分析程序的實(shí)現(xiàn) 有了狀態(tài)轉(zhuǎn)換圖很容易寫出詞法分析程序，下面考慮把詞法分析 程序作為一個子程序來構(gòu)造， 每當(dāng)語法分析程序需要一個單詞符號時 就調(diào)用這個子程序。在此對保留字不專設(shè)狀態(tài)轉(zhuǎn)換圖，只作標(biāo)識符處理 識別出標(biāo)識符后，再去查保留字表，以確定是保留字還是普通標(biāo)識符。 下面我們根據(jù)前述的狀態(tài)轉(zhuǎn)換圖來構(gòu)造由表3.2給出的PASCAL 子語言的詞法分析程序。首先我們引入一些變量和過程： （）字符變量，它存放著新讀入的源程序字符。 （）字符數(shù)組，它存放構(gòu)成單詞符號的字符串。 （）過程，讀入下一個源程序字符至中，

50、 并把字符指針后移一個位置。,79,（）過程GETNBC，先檢查CHAR中是否為空白字符，若是則反復(fù)調(diào) 用GETCHAR直至CHAR中讀入的是一個非空白字符。 （）過程CONCAT，將CHAR字符連接到TOKEN后面。例如，假定TOKEN原來的值為STUDENT，而CHAR中存放著 ，則調(diào)用過程 CONCAT之后，TOKEN的新值為STUDENTS。 （）布爾函數(shù)LETTER，若CHAR中字符為字母則返回TRUE，否則返回 FALSE。 （）布爾函數(shù)DIGIT，若CHAR中字符為數(shù)字則返回TRUE， 否則返回 FALSE。 （）函數(shù)RESERVE，由TOKEN字符串查保留字表，若TOKEN中字

51、符串 為保留字則返回其種別編碼，否則返回值為。 （）過程RETRACT，將字符指針向前移一個位置，CHAR置空白字符。,80,現(xiàn)在我們可以寫出前面所述的子語言的詞法分析程序： Start : token:= ; 置為空串 getchar; getnbc; CASE char OF AZ : BEGIN WHILE letter OR digit DO BEGIN Concat; getchar; END； retract； c := reserve IF c=0 THEN return ($ ID, token) ELSE return (c,) END；,81,0 9 : WHILE dig

52、it DO BEGIN Concat； getchar； END； retract； return （INT, DTB） END； ;: return ($SEMI，)； : return（$PLUS，）； *: return ($STAR，）；,82,: BEGIN； getchar； IF char THEN return （ $ASSIGN,）； ELSE retract； return ($COLON,) END； : BEGIN getchar； charTHEN return ($LE,)； ELSE retract; return($LT,) END END OF CASE； E

53、RROR；出錯處理 GOTO start； 返回開始處，進(jìn)行下一個單詞的識別,83,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.5 正規(guī)文法和有窮自動機(jī) 一、用正規(guī)文法描述單詞 二、由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖 三、有窮自動機(jī)FA 四、有窮自動機(jī)和正

54、規(guī)文法的關(guān)系 五、DFA與NFA的關(guān)系 3.6 正規(guī)表達(dá)式和有窮自動機(jī) 一、正規(guī)表達(dá)式和正規(guī)集的定義 二、正規(guī)表達(dá)式的性質(zhì) 三、正規(guī)文法、正規(guī)表達(dá)式與有窮自動機(jī) 四、由正規(guī)表達(dá)式構(gòu)造確定有窮自動機(jī) 五、確定有窮自動機(jī)的化簡 3.7 詞法分析程序的自動生成 一、問題的提出 二、語言LEX一般描述 三、LEX編譯程序的實(shí)現(xiàn) 四、LEX目標(biāo)程序,84,第三章 詞 法 分 析,3.1 引言 一、詞法分析基本思想 二、詞法分析任務(wù) 三、詞法分析方式 四、詞法分析方法 3.2 單詞的內(nèi)部編碼 一、單詞 二、內(nèi)部編碼 3.3 正規(guī)文法和狀態(tài)轉(zhuǎn)換圖 一、正規(guī)文法 二、狀態(tài)轉(zhuǎn)換圖 三、正規(guī)文法與狀態(tài)轉(zhuǎn)換圖 3.4 詞法分析程序設(shè)計(jì)與實(shí)現(xiàn) 一、源程序的輸入 二、緩沖區(qū)及預(yù)處理 三、超前搜索 四、由詞法語法規(guī)則畫狀態(tài)轉(zhuǎn)換圖 五、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn),3.