1、LI Wensheng, SCST, BUPT 第第3 3章章 詞法分析詞法分析基礎(chǔ)知識(shí)：基礎(chǔ)知識(shí)：PASCALPASCAL、C C語(yǔ)言、正規(guī)表達(dá)式語(yǔ)言、正規(guī)表達(dá)式 正規(guī)文法、有限自動(dòng)機(jī)知識(shí)點(diǎn)：詞法分析器的作用、地位知識(shí)點(diǎn)：詞法分析器的作用、地位 記號(hào)、模式 詞法分析器的狀態(tài)轉(zhuǎn)換圖Wensheng Li BUPT 20082/78詞法分析詞法分析 簡(jiǎn)介簡(jiǎn)介3.1 3.1 詞法分析程序與語(yǔ)法分析程序的關(guān)系詞法分析程序與語(yǔ)法分析程序的關(guān)系3.2 3.2 詞法分析程序的輸入與輸出詞法分析程序的輸入與輸出3.3 3.3 記號(hào)的描述和識(shí)別記號(hào)的描述和識(shí)別3.4 3.4 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程

2、序的設(shè)計(jì)與實(shí)現(xiàn)3.5 3.5 軟件工具軟件工具LEXLEX 小結(jié)小結(jié)Wensheng Li BUPT 20083/78簡(jiǎn)介簡(jiǎn)介n任務(wù)：把構(gòu)成源程序的字符串轉(zhuǎn)換成語(yǔ)義上關(guān)聯(lián)的記號(hào)序列任務(wù)：把構(gòu)成源程序的字符串轉(zhuǎn)換成語(yǔ)義上關(guān)聯(lián)的記號(hào)序列n編譯程序是在單詞的級(jí)別上來分析和翻譯源程序，因此，詞編譯程序是在單詞的級(jí)別上來分析和翻譯源程序，因此，詞法分析是編譯的基礎(chǔ)法分析是編譯的基礎(chǔ)n本章內(nèi)容安排本章內(nèi)容安排 討論用手工方式設(shè)計(jì)并實(shí)現(xiàn)詞法分析程序的方法和步驟討論用手工方式設(shè)計(jì)并實(shí)現(xiàn)詞法分析程序的方法和步驟詞法分析程詞法分析程序序的作用的作用詞法分析程序的地位詞法分析程序的地位源程序的輸入與詞法分析程源程序

3、的輸入與詞法分析程序序的輸出的輸出單詞符號(hào)的描述及識(shí)別單詞符號(hào)的描述及識(shí)別詞法分析程詞法分析程序序的設(shè)計(jì)與實(shí)現(xiàn)的設(shè)計(jì)與實(shí)現(xiàn) 詞法分析程詞法分析程序自動(dòng)序自動(dòng)生成工具生成工具LEXLEX簡(jiǎn)介簡(jiǎn)介Wensheng Li BUPT 20084/78詞法分析程序的作用詞法分析程序的作用n源程序由單詞組成，單詞是最小的語(yǔ)義單位源程序由單詞組成，單詞是最小的語(yǔ)義單位n詞法分析程詞法分析程序序的作用：的作用： 掃描源程序字符流掃描源程序字符流 按照源語(yǔ)言的詞法規(guī)則識(shí)別出各類單詞符號(hào)按照源語(yǔ)言的詞法規(guī)則識(shí)別出各類單詞符號(hào) 產(chǎn)生用于語(yǔ)法分析的記號(hào)序列產(chǎn)生用于語(yǔ)法分析的記號(hào)序列 詞法檢查詞法檢查 創(chuàng)建符號(hào)表創(chuàng)建符

4、號(hào)表 把識(shí)別出來的標(biāo)識(shí)符插入符號(hào)表中把識(shí)別出來的標(biāo)識(shí)符插入符號(hào)表中 與用戶接口的一些任務(wù)：與用戶接口的一些任務(wù)：跳過源程序中的注釋和空白跳過源程序中的注釋和空白把錯(cuò)誤信息和源程序聯(lián)系起來把錯(cuò)誤信息和源程序聯(lián)系起來Wensheng Li BUPT 20085/783.1 3.1 詞法分析程序與語(yǔ)法分析程序的關(guān)系詞法分析程序與語(yǔ)法分析程序的關(guān)系n詞法分析程序與語(yǔ)法分析程序之間的三種關(guān)系詞法分析程序與語(yǔ)法分析程序之間的三種關(guān)系詞法分析程序作為獨(dú)立的一遍詞法分析程序作為獨(dú)立的一遍詞法分析程詞法分析程序序作為語(yǔ)法分析程作為語(yǔ)法分析程序序的子程序的子程序詞法分析程詞法分析程序序與語(yǔ)法分析程與語(yǔ)法分析程序序

5、作為協(xié)同程序作為協(xié)同程序n分離詞法分析程分離詞法分析程序序的好處的好處n詞法分析的一些難點(diǎn)詞法分析的一些難點(diǎn)Wensheng Li BUPT 20086/78詞法分析程序作為獨(dú)立的一遍詞法分析程序作為獨(dú)立的一遍n輸出放入一個(gè)中間文件輸出放入一個(gè)中間文件 磁盤文件磁盤文件 內(nèi)存文件內(nèi)存文件字符串源程序字符串源程序字符字符詞法分析程序詞法分析程序記號(hào)記號(hào)記號(hào)流源程序記號(hào)流源程序Wensheng Li BUPT 20087/78詞法分析程序作為語(yǔ)法分析程詞法分析程序作為語(yǔ)法分析程序序的子程序的子程序n避免了中間文件避免了中間文件n省去了取送符號(hào)的工作省去了取送符號(hào)的工作n有利于提高編譯程有利于提高編

6、譯程序序的效率的效率語(yǔ)法語(yǔ)法分析器分析器詞法詞法分析器分析器取下一記號(hào)取下一記號(hào)字符串字符串源程序源程序字符字符記號(hào)記號(hào)符號(hào)表符號(hào)表Wensheng Li BUPT 20088/78詞法分析程序與語(yǔ)法分析程詞法分析程序與語(yǔ)法分析程序序作為協(xié)同程序作為協(xié)同程序n協(xié)同程序：協(xié)同程序： 如果兩個(gè)或兩個(gè)以上的程如果兩個(gè)或兩個(gè)以上的程序，它們之間交叉地執(zhí)行，序，它們之間交叉地執(zhí)行，這些程序稱為協(xié)同程序。這些程序稱為協(xié)同程序。詞法分析程序與語(yǔ)法分析程詞法分析程序與語(yǔ)法分析程序在同一遍中，以生產(chǎn)者和序在同一遍中，以生產(chǎn)者和消費(fèi)者的關(guān)系同步運(yùn)行。消費(fèi)者的關(guān)系同步運(yùn)行。P1P2喚醒喚醒P2喚醒喚醒P1喚醒喚醒P

7、2喚醒喚醒P1Wensheng Li BUPT 20089/78分離詞法分析程序的好處分離詞法分析程序的好處n可以簡(jiǎn)化設(shè)計(jì)可以簡(jiǎn)化設(shè)計(jì)詞法程詞法程序序很容易識(shí)別并去除空格、注釋，使語(yǔ)法分析程很容易識(shí)別并去除空格、注釋，使語(yǔ)法分析程序序致力于語(yǔ)法分析，結(jié)構(gòu)清晰，易于實(shí)現(xiàn)。致力于語(yǔ)法分析，結(jié)構(gòu)清晰，易于實(shí)現(xiàn)。n可以改進(jìn)編譯程可以改進(jìn)編譯程序序的效率的效率利用專門的讀字符和處理記號(hào)的技術(shù)構(gòu)造更有效的詞法分利用專門的讀字符和處理記號(hào)的技術(shù)構(gòu)造更有效的詞法分析程析程序序。n可以加強(qiáng)編譯程可以加強(qiáng)編譯程序序的可移植性的可移植性在詞法分析程在詞法分析程序序中處理特殊的或非標(biāo)準(zhǔn)的符號(hào)。中處理特殊的或非標(biāo)準(zhǔn)的符

8、號(hào)。Wensheng Li BUPT 200810/78詞法分析的一些難點(diǎn)詞法分析的一些難點(diǎn)n位置對(duì)準(zhǔn)位置對(duì)準(zhǔn)FortranFortran要求某些結(jié)構(gòu)出現(xiàn)在輸入行的固定位置要求某些結(jié)構(gòu)出現(xiàn)在輸入行的固定位置n空白不作為分隔符空白不作為分隔符FortranFortran中空格是無意義的，可以隨便加入中空格是無意義的，可以隨便加入DO 5 I = 1.25 （賦值語(yǔ)句，（賦值語(yǔ)句，DO5I是標(biāo)識(shí)符）是標(biāo)識(shí)符）DO 5 I = 1,25 （循環(huán)語(yǔ)句，（循環(huán)語(yǔ)句，DO是關(guān)鍵字）是關(guān)鍵字）n關(guān)鍵字不保留關(guān)鍵字不保留PL/IPL/I語(yǔ)言的關(guān)鍵字不保留語(yǔ)言的關(guān)鍵字不保留IF THEN THEN THEN=E

9、LSE; ELSE ELSE=THENWensheng Li BUPT 200811/783.2 3.2 詞法分析程序的輸入與輸出詞法分析程序的輸入與輸出一、詞法分析程一、詞法分析程序序的實(shí)現(xiàn)方法的實(shí)現(xiàn)方法二、設(shè)置緩沖區(qū)的必要性二、設(shè)置緩沖區(qū)的必要性三、配對(duì)緩沖區(qū)三、配對(duì)緩沖區(qū)四、詞法分析程四、詞法分析程序序的輸出的輸出Wensheng Li BUPT 200812/78一、詞法分析程序的實(shí)現(xiàn)方法一、詞法分析程序的實(shí)現(xiàn)方法n利用詞法分析程利用詞法分析程序自動(dòng)序自動(dòng)生成器生成器從基于正規(guī)表達(dá)式的規(guī)范說明自動(dòng)生成詞法分析程從基于正規(guī)表達(dá)式的規(guī)范說明自動(dòng)生成詞法分析程序序。生成器提供用于源程序字符流

10、讀入和緩沖的若干子程序生成器提供用于源程序字符流讀入和緩沖的若干子程序n利用傳統(tǒng)的系統(tǒng)程序設(shè)計(jì)語(yǔ)言來編寫利用傳統(tǒng)的系統(tǒng)程序設(shè)計(jì)語(yǔ)言來編寫利用該語(yǔ)言所具有的輸入利用該語(yǔ)言所具有的輸入/ /輸出能力來處理讀入操作輸出能力來處理讀入操作n利用匯編語(yǔ)言來編寫利用匯編語(yǔ)言來編寫直接管理源程序字符流的讀入直接管理源程序字符流的讀入Wensheng Li BUPT 200813/78二、設(shè)置緩沖區(qū)的必要性二、設(shè)置緩沖區(qū)的必要性n超前搜索：為了得到某一個(gè)單詞符號(hào)的確切性質(zhì)，超前搜索：為了得到某一個(gè)單詞符號(hào)的確切性質(zhì)，需要超前掃描若干個(gè)字符。需要超前掃描若干個(gè)字符。例：有合法的例：有合法的FORTRANFORT

11、RAN語(yǔ)句：語(yǔ)句： DO99K=1,10 DO99K=1,10 和和 DO99K=1.10DO99K=1.10 為了區(qū)別這兩個(gè)語(yǔ)句，必須超前掃描到等號(hào)后的第一個(gè)為了區(qū)別這兩個(gè)語(yǔ)句，必須超前掃描到等號(hào)后的第一個(gè)分界符處分界符處。例：例：PascalPascal語(yǔ)言中：語(yǔ)言中：、:=:=、（、（* *例：例：C C語(yǔ)言中：語(yǔ)言中：=、/ /* *、/、+n 方便實(shí)現(xiàn)讀字符和退字符操作，提高詞法分析器方便實(shí)現(xiàn)讀字符和退字符操作，提高詞法分析器的效率的效率Wensheng Li BUPT 200814/78三、配對(duì)緩沖區(qū)三、配對(duì)緩沖區(qū)n原因：不論緩沖器多大都不能保證單詞不被它的邊原因：不論緩沖器多大都

12、不能保證單詞不被它的邊界打斷界打斷n把一個(gè)緩沖器分為相同的兩半，每半各含把一個(gè)緩沖器分為相同的兩半，每半各含N N個(gè)字符，個(gè)字符，一般一般N=1KBN=1KB或或4KB4KB。n基本方法基本方法開始指針開始指針 向前指針向前指針 i f x = y t h e n j : = j + 2 ; eof Wensheng Li BUPT 200815/78測(cè)試指針的過程測(cè)試指針的過程(1)(1)IF (向前指針在左半?yún)^(qū)的終點(diǎn)向前指針在左半?yún)^(qū)的終點(diǎn)) 讀入字符串，填充右半?yún)^(qū)讀入字符串，填充右半?yún)^(qū);向前指針前移一個(gè)位置向前指針前移一個(gè)位置;ELSE IF (向前指針在右半?yún)^(qū)的終點(diǎn)向前指針在右半?yún)^(qū)的終點(diǎn)

13、) 讀入字符串，填充左半?yún)^(qū)讀入字符串，填充左半?yún)^(qū); 向前指針移到緩沖區(qū)的開始位置向前指針移到緩沖區(qū)的開始位置; ELSE 向前指針前移一個(gè)位置向前指針前移一個(gè)位置;Wensheng Li BUPT 200816/78每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器開始指針開始指針向前指針向前指針 i f x = y t h eof e n j : = j + 2 ; eof eofn 基本方法的缺點(diǎn)：基本方法的缺點(diǎn)：更新向前指針時(shí)要做二次測(cè)試更新向前指針時(shí)要做二次測(cè)試n 改進(jìn)：每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器改進(jìn)：每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器更新向前指針時(shí)只要做一次測(cè)試更新向前指針時(shí)只要做一次測(cè)試

14、Wensheng Li BUPT 200817/78測(cè)試指針的過程測(cè)試指針的過程(2)(2)向前指針前移一個(gè)位置；向前指針前移一個(gè)位置；IF (向前指針指向向前指針指向 eof ) IF (向前指針在左半?yún)^(qū)的終點(diǎn)向前指針在左半?yún)^(qū)的終點(diǎn)) 讀入字符串，填充右半?yún)^(qū)讀入字符串，填充右半?yún)^(qū); 向前指針前移一個(gè)位置向前指針前移一個(gè)位置; ELSE IF (向前指針在右半?yún)^(qū)的終點(diǎn)向前指針在右半?yún)^(qū)的終點(diǎn)) 讀入字符串，填充左半?yún)^(qū)讀入字符串，填充左半?yún)^(qū); 向前指針指向緩沖區(qū)的開始位置向前指針指向緩沖區(qū)的開始位置; ; ELSE 終止詞法分析終止詞法分析;Wensheng Li BUPT 200818/78四、

15、詞法分析程序的輸出四、詞法分析程序的輸出記號(hào)記號(hào)n記號(hào)、模式和單詞記號(hào)、模式和單詞 記號(hào)：是指某一類單詞符號(hào)的種別編碼，如標(biāo)識(shí)符的記號(hào)記號(hào)：是指某一類單詞符號(hào)的種別編碼，如標(biāo)識(shí)符的記號(hào)為為id，數(shù)的記號(hào)為，數(shù)的記號(hào)為num等。等。 模式：是指某一類單詞符號(hào)的構(gòu)詞規(guī)則，如標(biāo)識(shí)符的模式模式：是指某一類單詞符號(hào)的構(gòu)詞規(guī)則，如標(biāo)識(shí)符的模式是是“由字母開頭的字母數(shù)字串由字母開頭的字母數(shù)字串”。 單詞：是指某一類單詞符號(hào)的一個(gè)特例，如單詞：是指某一類單詞符號(hào)的一個(gè)特例，如position是是標(biāo)識(shí)符。標(biāo)識(shí)符。機(jī)內(nèi)表示機(jī)內(nèi)表示外部表示外部表示構(gòu)詞規(guī)則構(gòu)詞規(guī)則1.關(guān)鍵字關(guān)鍵字 記號(hào)的種類記號(hào)的種類2.標(biāo)識(shí)符標(biāo)識(shí)

16、符 3.常數(shù)常數(shù)4.運(yùn)算符運(yùn)算符5.分界符分界符Wensheng Li BUPT 200819/78記號(hào)的屬性記號(hào)的屬性n詞法分析程序在識(shí)別出一個(gè)記號(hào)后，要把與之有關(guān)的信息作詞法分析程序在識(shí)別出一個(gè)記號(hào)后，要把與之有關(guān)的信息作為它的屬性保留下來。為它的屬性保留下來。n記號(hào)影響語(yǔ)法分析的決策，屬性影響記號(hào)的翻譯。記號(hào)影響語(yǔ)法分析的決策，屬性影響記號(hào)的翻譯。n在詞法分析階段，對(duì)記號(hào)只能確定一種屬性在詞法分析階段，對(duì)記號(hào)只能確定一種屬性關(guān)鍵字：一字一種或全體一種，前一種方法較好關(guān)鍵字：一字一種或全體一種，前一種方法較好標(biāo)識(shí)符：一般統(tǒng)歸一種，也可分為若干種標(biāo)識(shí)符：一般統(tǒng)歸一種，也可分為若干種常數(shù)：一般

17、統(tǒng)歸一種，也可按類型分種常數(shù)：一般統(tǒng)歸一種，也可按類型分種運(yùn)算符：一符一種或一類一種運(yùn)算符：一符一種或一類一種分界符：一般用一符一種分界符：一般用一符一種n記號(hào)的屬性是指記號(hào)的特征或特性，反映特征或特性的值是記號(hào)的屬性是指記號(hào)的特征或特性，反映特征或特性的值是屬性值屬性值n一種一符則種別值可以認(rèn)為是屬性值，一種多符則需給出屬一種一符則種別值可以認(rèn)為是屬性值，一種多符則需給出屬性值性值Wensheng Li BUPT 200820/78total:=total+ratetotal:=total+rate* *4 4 的詞法分析結(jié)果的詞法分析結(jié)果Wensheng Li BUPT 200821/78

18、3.3 3.3 記號(hào)的描述和識(shí)別記號(hào)的描述和識(shí)別n識(shí)別單詞是按照記號(hào)的模式進(jìn)行的，一種記號(hào)的模識(shí)別單詞是按照記號(hào)的模式進(jìn)行的，一種記號(hào)的模式匹配一類單詞的集合。式匹配一類單詞的集合。為設(shè)計(jì)詞法程序，對(duì)模式要給出規(guī)范、系統(tǒng)的描述。為設(shè)計(jì)詞法程序，對(duì)模式要給出規(guī)范、系統(tǒng)的描述。n正規(guī)表達(dá)式和正規(guī)文法是描述模式的重要工具。正規(guī)表達(dá)式和正規(guī)文法是描述模式的重要工具。二者具有同等表達(dá)能力二者具有同等表達(dá)能力正規(guī)表達(dá)式：清晰、簡(jiǎn)潔正規(guī)表達(dá)式：清晰、簡(jiǎn)潔正規(guī)文法：便于識(shí)別正規(guī)文法：便于識(shí)別 一、詞法與正規(guī)文法一、詞法與正規(guī)文法 二、記號(hào)的文法二、記號(hào)的文法 三、狀態(tài)轉(zhuǎn)換圖與記號(hào)的識(shí)別三、狀態(tài)轉(zhuǎn)換圖與記號(hào)的識(shí)

19、別Wensheng Li BUPT 200822/78一、詞法與正規(guī)文法一、詞法與正規(guī)文法n把源語(yǔ)言的文法把源語(yǔ)言的文法G G分解為若干子文法：分解為若干子文法：G G0 0、 G G1 1、G G2 2、G Gn n 正規(guī)文法正規(guī)文法 上下文無關(guān)文法上下文無關(guān)文法 語(yǔ)法語(yǔ)法 詞法詞法n詞法：描述語(yǔ)言的標(biāo)識(shí)符、常數(shù)、運(yùn)算符和標(biāo)點(diǎn)符詞法：描述語(yǔ)言的標(biāo)識(shí)符、常數(shù)、運(yùn)算符和標(biāo)點(diǎn)符號(hào)等記號(hào)的文法號(hào)等記號(hào)的文法n語(yǔ)法：借助于記號(hào)來描述語(yǔ)言的結(jié)構(gòu)的文法語(yǔ)法：借助于記號(hào)來描述語(yǔ)言的結(jié)構(gòu)的文法文法？文法？Wensheng Li BUPT 200823/78二、記號(hào)的文法二、記號(hào)的文法n標(biāo)識(shí)符標(biāo)識(shí)符n常數(shù)常數(shù)整

20、數(shù)整數(shù)無符號(hào)數(shù)無符號(hào)數(shù)n運(yùn)算符運(yùn)算符n分界符分界符n關(guān)鍵字關(guān)鍵字Wensheng Li BUPT 200824/78標(biāo)識(shí)符標(biāo)識(shí)符n標(biāo)識(shí)符定義為標(biāo)識(shí)符定義為“由字母打頭的、由字母或數(shù)字組成由字母打頭的、由字母或數(shù)字組成的符號(hào)串的符號(hào)串”n描述標(biāo)識(shí)符集合的正規(guī)表達(dá)式：描述標(biāo)識(shí)符集合的正規(guī)表達(dá)式：letter(letter|digit)*n表示標(biāo)識(shí)符集合的正規(guī)定義式：表示標(biāo)識(shí)符集合的正規(guī)定義式： letter A|B|Z|a|b|z digit 0|1|9 id letter(letter|digit)*正規(guī)表達(dá)式？正規(guī)表達(dá)式？Wensheng Li BUPT 200825/78把正規(guī)定義式轉(zhuǎn)換為相

21、應(yīng)的正規(guī)文法把正規(guī)定義式轉(zhuǎn)換為相應(yīng)的正規(guī)文法 ( letter | digit )* = | ( letter | digit )+ = | ( letter | digit ) ( letter | digit )* = | letter ( letter | digit )* | digit ( letter | digit )* = | (A|Z|a|z) ( letter | digit )* | (0|9)( letter | digit )* = | A ( letter | digit )* | | Z ( letter | digit )* | a ( letter | dig

22、it )* | | z ( letter | digit )* | 0 ( letter | digit )* | | 9 ( letter | digit )* Wensheng Li BUPT 200826/78標(biāo)識(shí)符的正規(guī)文法標(biāo)識(shí)符的正規(guī)文法 id A rid|Z rid|a rid|z ridrid |A rid|B rid|Z rid |a rid|b rid|z rid |0 rid|1 rid|9 ridn一般寫作：一般寫作： id letter ridrid | letter rid | digit ridWensheng Li BUPT 200827/78常數(shù)常數(shù)整數(shù)整數(shù)n描

23、述整數(shù)結(jié)構(gòu)的正規(guī)表達(dá)式為：描述整數(shù)結(jié)構(gòu)的正規(guī)表達(dá)式為： (digit)+n對(duì)此正規(guī)表達(dá)式進(jìn)行等價(jià)變換：對(duì)此正規(guī)表達(dá)式進(jìn)行等價(jià)變換： (digit)+ = digit(digit)* (digit)* = | digit(digit)*n整數(shù)的正規(guī)文法：整數(shù)的正規(guī)文法： digits digit remainder remainder | digit remainder Wensheng Li BUPT 200828/78常數(shù)常數(shù)無符號(hào)數(shù)無符號(hào)數(shù)n無符號(hào)數(shù)的正規(guī)表達(dá)式為：無符號(hào)數(shù)的正規(guī)表達(dá)式為：(digit)+ (.(digit)+)? (E(+|-)?(digit)+)?n正規(guī)定義式為正規(guī)定義

24、式為digit 0|1|9digits digit+optional_fraction (.digits)?optional_exponent (E(+|-)?digits)?num digits optional_fraction optional_exponentWensheng Li BUPT 200829/78把正規(guī)定義式轉(zhuǎn)換為正規(guī)文法把正規(guī)定義式轉(zhuǎn)換為正規(guī)文法 ( digit )+ ( . ( digit )+ )? ( E( + | - )?( digit )+ )?=( digit )+ ( . ( digit )+ | ) ( E(+ |- | ) ( digit )+ | )

25、=digit (digit)* ( . digit ( digit )*| ) ( E (+|-| ) digit ( digit )* | )num1 num1 表示無符號(hào)數(shù)的第一個(gè)數(shù)字之后的部分表示無符號(hào)數(shù)的第一個(gè)數(shù)字之后的部分num2 num2 表示小數(shù)點(diǎn)以后的部分表示小數(shù)點(diǎn)以后的部分num3 num3 表示小數(shù)點(diǎn)后第一個(gè)數(shù)字以后的部分表示小數(shù)點(diǎn)后第一個(gè)數(shù)字以后的部分num4 num4 表示表示E E之后的部分之后的部分num5 num5 表示表示(digit)(digit)* *digits digits 表示表示(digit)(digit)+Wensheng Li BUPT 2008

26、30/78無符號(hào)數(shù)分析圖無符號(hào)數(shù)分析圖 digit (digit)* (. digit (digit)*|) (E (+|-|) digit (digit)* |)num3num2num1num4numnum digit num1num1 digit num1 | . num2 | E num4 | num2 digit num3num3 digit num3 | E num4 | num4 + digits | - digits | digit num5digits digit num5num5 digit num5 | Wensheng Li BUPT 200831/78無符號(hào)數(shù)的正規(guī)文法

27、無符號(hào)數(shù)的正規(guī)文法 num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits | - digits | digit num5 digits digit num5 num5 digit num5 | Wensheng Li BUPT 200832/78無符號(hào)數(shù)無符號(hào)數(shù) 4.6E-8 4.6E-8 的分析樹的分析樹numdigit num1. num2digit num3E num4- digitsdigit num5 468 Wenshen

28、g Li BUPT 200833/78運(yùn)算符運(yùn)算符n關(guān)系運(yùn)算符的正規(guī)表達(dá)式為：關(guān)系運(yùn)算符的正規(guī)表達(dá)式為： |= | = | | = | n正規(guī)定義式：正規(guī)定義式：relop |= | = | | = | n關(guān)系運(yùn)算符的正規(guī)文法：關(guān)系運(yùn)算符的正規(guī)文法：relop | equal | = | | equalgreater equal =Wensheng Li BUPT 200834/78三、狀態(tài)轉(zhuǎn)換圖與記號(hào)的識(shí)別三、狀態(tài)轉(zhuǎn)換圖與記號(hào)的識(shí)別n狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖n利用狀態(tài)轉(zhuǎn)換圖識(shí)別記號(hào)利用狀態(tài)轉(zhuǎn)換圖識(shí)別記號(hào)n為線性文法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖為線性文法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖狀態(tài)集合的構(gòu)成狀態(tài)集合的構(gòu)成狀態(tài)

29、之間邊的形成狀態(tài)之間邊的形成Wensheng Li BUPT 200835/78狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖n狀態(tài)轉(zhuǎn)換圖是一張有限的方向圖狀態(tài)轉(zhuǎn)換圖是一張有限的方向圖圖中結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。圖中結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用有向邊連接。狀態(tài)之間用有向邊連接。邊上的標(biāo)記代表在射出結(jié)狀態(tài)下，可能出現(xiàn)的輸入符號(hào)或邊上的標(biāo)記代表在射出結(jié)狀態(tài)下，可能出現(xiàn)的輸入符號(hào)或字符類。字符類。123xyWensheng Li BUPT 200836/78標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖n標(biāo)識(shí)符的文法產(chǎn)生式：標(biāo)識(shí)符的文法產(chǎn)生式：id letter ridrid | letter rid | digit rid

30、n標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖012letter/digitletterother*Wensheng Li BUPT 200837/78利用狀態(tài)轉(zhuǎn)換圖識(shí)別記號(hào)利用狀態(tài)轉(zhuǎn)換圖識(shí)別記號(hào)n語(yǔ)句語(yǔ)句 DO99K=1.10 DO99K=1.10 中中標(biāo)識(shí)符標(biāo)識(shí)符 DO99KDO99K 的識(shí)別過程：的識(shí)別過程：012letter/digitletterother*狀態(tài)狀態(tài) 0讀入讀入D狀態(tài)狀態(tài)1讀入讀入O狀態(tài)狀態(tài)1讀入讀入9狀態(tài)狀態(tài)1讀入讀入K狀態(tài)狀態(tài)1讀入讀入=狀態(tài)狀態(tài)2讀入讀入9狀態(tài)狀態(tài)1Wensheng Li BUPT 200838/78為線性文法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖為線性文法構(gòu)造相應(yīng)的狀態(tài)

31、轉(zhuǎn)換圖n狀態(tài)集合的構(gòu)成狀態(tài)集合的構(gòu)成對(duì)文法對(duì)文法G G的每一個(gè)非終結(jié)符號(hào)設(shè)置一個(gè)對(duì)應(yīng)的狀態(tài)的每一個(gè)非終結(jié)符號(hào)設(shè)置一個(gè)對(duì)應(yīng)的狀態(tài)文法的開始符號(hào)對(duì)應(yīng)的狀態(tài)稱為初態(tài)文法的開始符號(hào)對(duì)應(yīng)的狀態(tài)稱為初態(tài)增加一個(gè)新的狀態(tài)，稱為終態(tài)。增加一個(gè)新的狀態(tài)，稱為終態(tài)。n狀態(tài)之間邊的形成狀態(tài)之間邊的形成對(duì)產(chǎn)生式對(duì)產(chǎn)生式A AaBaB，從，從A A狀態(tài)到狀態(tài)到B B狀態(tài)畫一條標(biāo)記為狀態(tài)畫一條標(biāo)記為a a的邊的邊對(duì)產(chǎn)生式對(duì)產(chǎn)生式A Aa a，從，從A A狀態(tài)到終態(tài)畫一條標(biāo)記為狀態(tài)到終態(tài)畫一條標(biāo)記為a a的邊的邊對(duì)產(chǎn)生式對(duì)產(chǎn)生式A A，從，從A A狀態(tài)到終態(tài)畫一條標(biāo)記為狀態(tài)到終態(tài)畫一條標(biāo)記為 的邊的邊Wensheng Li

32、 BUPT 200839/78無符號(hào)數(shù)的右線性文法的狀態(tài)轉(zhuǎn)換圖無符號(hào)數(shù)的右線性文法的狀態(tài)轉(zhuǎn)換圖numnum1num2num3num4num5digits024digit1digit3digit6digitother7digitEE5+/-digitdigit*other.other num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit num3 | E num4 | num4 + digits | - digits | digit num5 digits digit num5 num5 dig

33、it num5 | Wensheng Li BUPT 200840/783.4 3.4 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)步驟：步驟：1.1. 給出描述該語(yǔ)言各種單詞符號(hào)的詞法規(guī)則給出描述該語(yǔ)言各種單詞符號(hào)的詞法規(guī)則2.2. 畫出狀態(tài)轉(zhuǎn)換圖畫出狀態(tài)轉(zhuǎn)換圖3.3. 根據(jù)狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器根據(jù)狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器一、文法及狀態(tài)轉(zhuǎn)換圖一、文法及狀態(tài)轉(zhuǎn)換圖1. 1. 語(yǔ)言說明語(yǔ)言說明2. 2. 記號(hào)的正規(guī)文法記號(hào)的正規(guī)文法3. 3. 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖二、詞法分析程二、詞法分析程序序的構(gòu)造的構(gòu)造三、詞法分析程三、詞法分析程序序的實(shí)現(xiàn)的實(shí)現(xiàn)1. 1. 輸出形式輸出形式2. 2.

34、 設(shè)計(jì)全局變量和過程設(shè)計(jì)全局變量和過程3. 3. 編制詞法分析程編制詞法分析程序序Wensheng Li BUPT 200841/78一、文法及狀態(tài)轉(zhuǎn)換圖一、文法及狀態(tài)轉(zhuǎn)換圖n語(yǔ)言說明語(yǔ)言說明標(biāo)識(shí)符標(biāo)識(shí)符：以字母開頭的、后跟字母或數(shù)字組成的符號(hào)串。：以字母開頭的、后跟字母或數(shù)字組成的符號(hào)串。保留字保留字：標(biāo)識(shí)符的子集。：標(biāo)識(shí)符的子集。無符號(hào)數(shù)無符號(hào)數(shù)：同：同PASCAL語(yǔ)言中的無符號(hào)數(shù)。語(yǔ)言中的無符號(hào)數(shù)。關(guān)系運(yùn)算符關(guān)系運(yùn)算符：、=、=、=、。標(biāo)點(diǎn)符號(hào)標(biāo)點(diǎn)符號(hào)：+、-、*、/、(、)、:、 、；等。、；等。賦值號(hào)賦值號(hào)： :=注釋標(biāo)記注釋標(biāo)記：以：以/*開始，以開始，以*/結(jié)束。結(jié)束。單詞符號(hào)間

35、的分隔符單詞符號(hào)間的分隔符：空格：空格Wensheng Li BUPT 200842/78記號(hào)的正規(guī)文法記號(hào)的正規(guī)文法n標(biāo)識(shí)符的文法標(biāo)識(shí)符的文法 id letter ridrid | letter rid | digit ridn無符號(hào)整數(shù)的文法無符號(hào)整數(shù)的文法 digits digit remainderremainder | digit remainderWensheng Li BUPT 200843/78n無符號(hào)數(shù)的文法無符號(hào)數(shù)的文法 num digit num1 num1 digit num1 | . num2 | E num4 | num2 digit num3 num3 digit

36、 num3 | E num4 | num4 + digits | - digits |digit num5 digits digit num5 num5 digit num5 | n關(guān)系運(yùn)算符的文法關(guān)系運(yùn)算符的文法relop |equal | = |equalgreater equal =記號(hào)的正規(guī)文法記號(hào)的正規(guī)文法( (續(xù)續(xù)) )Wensheng Li BUPT 200844/78n賦值號(hào)的文法賦值號(hào)的文法assign_op :equal equal =n標(biāo)點(diǎn)符號(hào)的文法標(biāo)點(diǎn)符號(hào)的文法single + | - | * | / | ( | ) | : | | ;n注釋頭符號(hào)的文法注釋頭符號(hào)的文法

37、note / starstar *記號(hào)的正規(guī)文法記號(hào)的正規(guī)文法( (續(xù)續(xù)) )Wensheng Li BUPT 200845/78狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)換換圖圖讀去注釋狀態(tài)讀去注釋狀態(tài)錯(cuò)誤處理狀態(tài)錯(cuò)誤處理狀態(tài)digitEother *35digit2digit4digit7digitdigit.E6+/-digit other * other *0letter1letter / digitother *8other *9=other *=：10=other *+ / - / * / ( / ) / ; / /11*other *1213other轉(zhuǎn)入口轉(zhuǎn)入口出口出口入口入口 Wensheng Li BU

38、PT 200846/78二、詞法分析程序的構(gòu)造二、詞法分析程序的構(gòu)造根據(jù)上述狀態(tài)轉(zhuǎn)換圖，再加上相應(yīng)的語(yǔ)義動(dòng)作，根據(jù)上述狀態(tài)轉(zhuǎn)換圖，再加上相應(yīng)的語(yǔ)義動(dòng)作，就可以構(gòu)造出的詞法分析程就可以構(gòu)造出的詞法分析程序序的算法框圖。的算法框圖。Wensheng Li BUPT 200847/78開始開始讀字符讀字符空白？空白？YNToken := 字母？字母？Y 組合標(biāo)識(shí)符組合標(biāo)識(shí)符 R查保留字表查保留字表保留字？保留字？YN輸出保留字輸出保留字輸出標(biāo)識(shí)符輸出標(biāo)識(shí)符N數(shù)字？數(shù)字？Y組數(shù)組數(shù) R輸出無符號(hào)數(shù)輸出無符號(hào)數(shù)N ？ YN讀字符讀字符 = ？Y輸出輸出 ？Y輸出輸出 N R輸出輸出 ？ Y讀字符讀字符

39、=？ Y輸出輸出 =N R輸出輸出 ：？：？Y讀字符讀字符 =? Y輸出賦值號(hào)輸出賦值號(hào) :=:=N R輸出冒號(hào)：輸出冒號(hào)：N / ? 讀字符讀字符 * ?讀去注釋讀去注釋N R輸出斜杠輸出斜杠 / /NYY轉(zhuǎn)入口轉(zhuǎn)入口N 標(biāo)點(diǎn)符號(hào)？標(biāo)點(diǎn)符號(hào)？Y輸出標(biāo)點(diǎn)符號(hào)輸出標(biāo)點(diǎn)符號(hào)N錯(cuò)誤處理錯(cuò)誤處理出口出口說明：說明： R 為一過程，其功能是向前指針回退一個(gè)字符；為一過程，其功能是向前指針回退一個(gè)字符； Token 為字符數(shù)組，用于存放單詞符號(hào)為字符數(shù)組，用于存放單詞符號(hào) Wensheng Li BUPT 200848/78三、詞法分析程序的實(shí)現(xiàn)三、詞法分析程序的實(shí)現(xiàn)n輸出形式輸出形式n設(shè)計(jì)全局變量和過程

40、設(shè)計(jì)全局變量和過程n編制詞法分析程編制詞法分析程序序Wensheng Li BUPT 200849/78輸出形式輸出形式n利用翻譯表，將識(shí)別出的單詞的記號(hào)以二元式的利用翻譯表，將識(shí)別出的單詞的記號(hào)以二元式的形式加以輸出形式加以輸出n二元式的形式：二元式的形式： Wensheng Li BUPT 200850/78正規(guī)表達(dá)式正規(guī)表達(dá)式記號(hào)記號(hào)屬性屬性ifififif- -thenthenthenthen- -elseelseelseelse- -idididid符號(hào)表入口指針符號(hào)表入口指針numnumnumnum常數(shù)表入口指針常數(shù)表入口指針 reloprelopLTLT=reloprelopLE

41、LE= =reloprelopEQEQreloprelopNENE reloprelopGTGT=reloprelopGEGE:=:=assign-opassign-op- -+ + +- - - - -* * *- -/ / /- -( ( (- -) ) )- - - -; ; ;- -: : :- -Wensheng Li BUPT 200851/78設(shè)計(jì)全局變量和過程設(shè)計(jì)全局變量和過程n轉(zhuǎn)換圖中的每一狀態(tài)，分別用一段程序?qū)崿F(xiàn)。轉(zhuǎn)換圖中的每一狀態(tài)，分別用一段程序?qū)崿F(xiàn)。n如果某一狀態(tài)有若干條射出邊，則程序：如果某一狀態(tài)有若干條射出邊，則程序：讀一個(gè)字符讀一個(gè)字符根據(jù)讀到的字符，選擇標(biāo)記與之

42、匹配的邊到達(dá)下一個(gè)根據(jù)讀到的字符，選擇標(biāo)記與之匹配的邊到達(dá)下一個(gè)狀態(tài)，即程序控制轉(zhuǎn)去執(zhí)行下一個(gè)狀態(tài)對(duì)應(yīng)的語(yǔ)句序狀態(tài)，即程序控制轉(zhuǎn)去執(zhí)行下一個(gè)狀態(tài)對(duì)應(yīng)的語(yǔ)句序列。列。Wensheng Li BUPT 200852/78(1) (1) C：字符變量，存放當(dāng)前讀進(jìn)的字符。：字符變量，存放當(dāng)前讀進(jìn)的字符。(2) (2) iskey：整型變量：整型變量(3) (3) token：字符數(shù)組，存放單詞的字符串。：字符數(shù)組，存放單詞的字符串。(4) (4) lexemebegin：字符指針，指向輸入緩沖區(qū)中當(dāng)前單：字符指針，指向輸入緩沖區(qū)中當(dāng)前單詞的開始位置。詞的開始位置。(5) (5) forward：字符

43、指針，向前掃描指針。：字符指針，向前掃描指針。(6) (6) buffer：字符數(shù)組，輸入緩沖區(qū)。：字符數(shù)組，輸入緩沖區(qū)。(7) (7) get_char：讀字符過程，每調(diào)用一次，讀進(jìn)一個(gè)字符，：讀字符過程，每調(diào)用一次，讀進(jìn)一個(gè)字符，并把它放入并把它放入charchar中，且向前指針中，且向前指針forwardforward指向下一個(gè)字符。指向下一個(gè)字符。(8) (8) get_nbc：過程，每次調(diào)用時(shí)，檢查：過程，每次調(diào)用時(shí)，檢查charchar中是否為空字中是否為空字符，若是，則反復(fù)調(diào)用該過程，直到符，若是，則反復(fù)調(diào)用該過程，直到charchar進(jìn)入一個(gè)非空進(jìn)入一個(gè)非空字符為止。字符為止。

44、設(shè)計(jì)全局變量和過程（續(xù)）設(shè)計(jì)全局變量和過程（續(xù)）Wensheng Li BUPT 200853/78(9) (9) cat：過程，每次調(diào)用把當(dāng)前：過程，每次調(diào)用把當(dāng)前charchar中的字符與中的字符與tokentoken中的中的字符串連接起來。字符串連接起來。(10) (10) letter和和digit：布爾函數(shù)，分別判斷：布爾函數(shù)，分別判斷charchar中的字符是中的字符是否為字母或數(shù)字，若是則返回否為字母或數(shù)字，若是則返回truetrue，否則返回，否則返回falsefalse。(11) (11) retract：過程，向前掃描指針：過程，向前掃描指針forwardforward后退

45、一個(gè)字符。后退一個(gè)字符。(12) (12) reserve：函數(shù)，查保留字表，若此函數(shù)的返回值為：函數(shù)，查保留字表，若此函數(shù)的返回值為0 0，則表示則表示tokentoken中的字符串是標(biāo)識(shí)符，否則為保留字。中的字符串是標(biāo)識(shí)符，否則為保留字。(13) (13) DTB：十：十/ /二進(jìn)制的轉(zhuǎn)換過程，它將二進(jìn)制的轉(zhuǎn)換過程，它將tokentoken中的數(shù)字串轉(zhuǎn)中的數(shù)字串轉(zhuǎn)換成二進(jìn)制的數(shù)值表示。換成二進(jìn)制的數(shù)值表示。(14) (14) table_insert：過程，將標(biāo)識(shí)符插入符號(hào)表。：過程，將標(biāo)識(shí)符插入符號(hào)表。(15) (15) error：錯(cuò)誤處理函數(shù)。：錯(cuò)誤處理函數(shù)。(16) (16) re

46、turn：返回過程，收集并攜帶必要的信息返回調(diào)用程：返回過程，收集并攜帶必要的信息返回調(diào)用程序。序。設(shè)計(jì)全局變量和過程（續(xù)）設(shè)計(jì)全局變量和過程（續(xù)）Wensheng Li BUPT 200854/78編制詞法分析程序（編制詞法分析程序（方法一方法一）token=;get_char;get_nbc;SWITCH (C) CASE a.z: WHILE (letter | digit) cat; get_char; retract; iskey=reserve; IF iskey=0 table_insert; return(ID, 指向該標(biāo)識(shí)符在符號(hào)表的入口指針指向該標(biāo)識(shí)符在符號(hào)表的入口指針);

47、 ; ELSE return (關(guān)鍵字的記號(hào)，關(guān)鍵字的記號(hào)，-); BREAK;Wensheng Li BUPT 200855/78CASE 0.9: WHILE (digit|.|E|+|-) cat; get_char; retract; return(num, DTB(token); BREAK;CASE ) return(relop, NE); ELSE retract; return(relop, LT); BREAK;CASE = : return(relop, EQ); BREAK;CASE : get_char; IF (C=) return(relop, GE); ELSE

48、retract; return(relop, GT); BREAK;編制詞法分析器（續(xù)）編制詞法分析器（續(xù)）Wensheng Li BUPT 200856/78CASE : : get_char; IF (C=) return(assign-op, -); retract; return(:, -); BREAK;CASE + : return(+, -); BREAK;CASE - : return(-, -); BREAK;CASE ( : return(, -); BREAK;CASE ) : return(), -); BREAK;CASE ; : return(;, -); BREA

49、K;編制詞法分析器（續(xù)）編制詞法分析器（續(xù)）Wensheng Li BUPT 200857/78CASE / : get_char; IF (C=*) loop_1: get_char; WHILE (!*) get_char; get_char; IF (C=/) BREAK; GOTO loop_1; ; ELSE retract; return(/,-); BREAK; / end of case /DEFAULT: error(); /end of switch編制詞法分析器（續(xù)）編制詞法分析器（續(xù)）Wensheng Li BUPT 200858/78編制詞法分析器（方法二）編制詞法分

50、析器（方法二）token=;B=1; state=0;WHILE (B) get_char; get_nbc; SWITCH (state) CASE 0: SWITCH (C) CASEa.z: cat; stata=1; BREAK; CASE0.9: cat; state=2; BREAK; CASE :state=8; BREAK; CASE + : return(+, -); BREAK; CASE 1: SWITCH (C) CASE a.z: cat; state=1; BREAK; CASE 0.9: cat; state=1; BREAK; DEFAULT: /*處理標(biāo)識(shí)符和

51、關(guān)鍵字程序處理標(biāo)識(shí)符和關(guān)鍵字程序*/;B=0; BREAK; CASE 2: Wensheng Li BUPT 200859/783.5 3.5 軟件工具軟件工具LEXLEXn使用使用LEXLEX的流程的流程: :LEXLEX源程序源程序lex.llex.lLEXLEX編譯器編譯器Lex.yy.cLex.yy.clex.yy.clex.yy.cC C編譯器編譯器Lex.yy.oLex.yy.o 或或a.outa.out字符流源程序字符流源程序a.outa.out記號(hào)序列記號(hào)序列Lex.yy.oLex.yy.o可以和其它程序的目標(biāo)代碼連接可以和其它程序的目標(biāo)代碼連接a.outa.out是可執(zhí)行的

52、目標(biāo)程序，可以作為獨(dú)立運(yùn)行的詞法分析是可執(zhí)行的目標(biāo)程序，可以作為獨(dú)立運(yùn)行的詞法分析器器Wensheng Li BUPT 200860/78說明部分說明部分%翻譯規(guī)則翻譯規(guī)則%輔助過程輔助過程主要內(nèi)容主要內(nèi)容一、一、LEXLEX源程序源程序1. 1. 說明部分說明部分2. 2. 翻譯規(guī)則翻譯規(guī)則3. 3. 輔助過程輔助過程二、二、LEXLEX的工作原理的工作原理1. LEX1. LEX的工作過程的工作過程2. 2. 處理二義性問題的兩條規(guī)則處理二義性問題的兩條規(guī)則3. LEX3. LEX工作過程舉例工作過程舉例Wensheng Li BUPT 200861/78一、一、LEXLEX源程序源程序1

53、.1.說明部分說明部分n包括：包括：變量說明變量說明標(biāo)識(shí)符常量說明標(biāo)識(shí)符常量說明正規(guī)定義正規(guī)定義n正規(guī)定義中的名字可在翻譯規(guī)則中用作正規(guī)表達(dá)式正規(guī)定義中的名字可在翻譯規(guī)則中用作正規(guī)表達(dá)式的成分的成分nC C語(yǔ)言的說明必須用分界符語(yǔ)言的說明必須用分界符“ % ”% ”和和“ % ”% ”括起括起來。來。出現(xiàn)在括號(hào)中的任何東西都直接抄寫到詞法分析器出現(xiàn)在括號(hào)中的任何東西都直接抄寫到詞法分析器Lex.yy.cLex.yy.c中，不作為正規(guī)定義和翻譯規(guī)則的一部分。在第中，不作為正規(guī)定義和翻譯規(guī)則的一部分。在第三節(jié)中的輔助過程也按同樣方式處理三節(jié)中的輔助過程也按同樣方式處理Wensheng Li BUP

54、T 200862/78一、一、LEXLEX源程序源程序2.2.翻譯規(guī)則翻譯規(guī)則n形式：形式：P1 P1 動(dòng)作動(dòng)作1 1 P2 P2 動(dòng)作動(dòng)作2 2 PnPn 動(dòng)作動(dòng)作n n nPi Pi 是一個(gè)正規(guī)表達(dá)式，描述一種記號(hào)的模式。是一個(gè)正規(guī)表達(dá)式，描述一種記號(hào)的模式。n動(dòng)作動(dòng)作i i 是是C C語(yǔ)言的程序語(yǔ)句，表示當(dāng)一個(gè)串匹配模式語(yǔ)言的程序語(yǔ)句，表示當(dāng)一個(gè)串匹配模式PiPi時(shí)，詞法分析器應(yīng)執(zhí)行的動(dòng)作。時(shí)，詞法分析器應(yīng)執(zhí)行的動(dòng)作。Wensheng Li BUPT 200863/78一、一、LEXLEX源程序源程序3.3.輔助過程輔助過程n對(duì)翻譯規(guī)則的補(bǔ)充對(duì)翻譯規(guī)則的補(bǔ)充n翻譯規(guī)則部分中某些動(dòng)作需要調(diào)

55、用的過程，如果不翻譯規(guī)則部分中某些動(dòng)作需要調(diào)用的過程，如果不是是C C語(yǔ)言的庫(kù)函數(shù)，則要在此給出具體的定義。語(yǔ)言的庫(kù)函數(shù)，則要在此給出具體的定義。n這些過程也可以存入另外的程序文件中，單獨(dú)編譯，這些過程也可以存入另外的程序文件中，單獨(dú)編譯，然后和詞法分析器連接裝配在一起。然后和詞法分析器連接裝配在一起。Wensheng Li BUPT 200864/78LEXLEX源程序舉例源程序舉例nLEXLEX生成的詞法分析器的執(zhí)行：最長(zhǎng)匹配原則生成的詞法分析器的執(zhí)行：最長(zhǎng)匹配原則n傳遞單詞的屬性，是把屬性值賦給全程變量傳遞單詞的屬性，是把屬性值賦給全程變量yylvalyylvaln正規(guī)定義式：正規(guī)定義式

56、：if ifthen thenelse elserelop | = | = | | | =id letter(letter|digit)*num digit+(.digit+)?(E(+|-)?digit+)?Wensheng Li BUPT 200865/78相應(yīng)的相應(yīng)的LEXLEX規(guī)格說明規(guī)格說明 /* 說明部分說明部分 */%#include /* C語(yǔ)言描述的標(biāo)識(shí)符常量的定義，如語(yǔ)言描述的標(biāo)識(shí)符常量的定義，如 LT、LE、EQ、NE、GT、GE、IF、THEN、ELSE、ID、NUMBER、RELOP */extern yylval;% /* 正規(guī)定義式正規(guī)定義式 */delim tn

57、ws delim+letter A-Za-zdigit 0-9id letter(letter|digit)* num digit+(.digit+)?(E+-?digit+)?%Wensheng Li BUPT 200866/78/* 規(guī)則部分規(guī)則部分 */ws /* 沒有動(dòng)作，也不返回沒有動(dòng)作，也不返回 */if return(IF); then return(THEN); else return(ELSE); id yylval=install_id(); return(ID); num yylval=install_num(); return(NUMBER); “” yylval=LT

58、; return(RELOP); “=” yylval=LE; return(RELOP); “=” yylval=EQ; return(RELOP); “” yylval=NE; return(RELOP); “” yylval=GT; return(RELOP); “=” yylval=GE; return(RELOP); %相應(yīng)的相應(yīng)的LEXLEX規(guī)格說明（續(xù)）規(guī)格說明（續(xù)）如果沒有如果沒有return語(yǔ)句，則，處理完整個(gè)輸入之后才會(huì)返回！語(yǔ)句，則，處理完整個(gè)輸入之后才會(huì)返回！Wensheng Li BUPT 200867/78/* 輔助過程輔助過程 */int install_id()

59、 /* 把單詞插入符號(hào)表并返回該單詞在符號(hào)表中的位置把單詞插入符號(hào)表并返回該單詞在符號(hào)表中的位置 yytext指向該單詞的第一個(gè)字符指向該單詞的第一個(gè)字符 yyleng給出它的長(zhǎng)度給出它的長(zhǎng)度 */int install_num() /* 類似于上面的過程，但單詞是常數(shù)類似于上面的過程，但單詞是常數(shù) */相應(yīng)的相應(yīng)的LEXLEX規(guī)格說明（續(xù)）規(guī)格說明（續(xù)）Wensheng Li BUPT 200868/78LEXLEX解決沖突的方式解決沖突的方式1.1. 根據(jù)規(guī)則定義的先后次序根據(jù)規(guī)則定義的先后次序解決了例子中關(guān)鍵字和標(biāo)識(shí)符的沖突解決了例子中關(guān)鍵字和標(biāo)識(shí)符的沖突2.2. 最長(zhǎng)匹配原則最長(zhǎng)匹配原則解決了例子中諸如解決了例子中諸如 “ “” ” 和和 “ “=” =” 的沖突的沖突?Wensheng Li BUPT 200869/78二、二、LEXLEX的工作原理的工作原