編譯原理第3章-詞法分析

詞法分析第三講

詞法分析概述

詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析

詞法分析程序的自動(dòng)構(gòu)造詞法分析概述

詞法分析程序（Lexical

Analyzer）或詞法掃描程序（Scanner）的作用

從左至右掃描構(gòu)成源程序的字符流識(shí)別出有詞法意義的單詞（Lexemes）返回單詞記錄（由單詞記號(hào)（Token）和單詞的屬性值組成），或詞法錯(cuò)誤信息除以上主要任務(wù)外，常伴有如下任務(wù)

濾掉空格，跳過注釋、換行符，追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開，……

也可能包含訪問符號(hào)表的操作

編譯程序主題中如何組織詞法分析程序

可以作為單獨(dú)的一遍較常用的方式是由語(yǔ)法分析程序調(diào)用基本任務(wù)都是識(shí)別單詞詞法分析概述

例：Pascal

程序文本

position:=initial+rate*60；

經(jīng)詞法分析程序處理后，轉(zhuǎn)換為下列單詞序列詞法單元（對(duì)應(yīng)一個(gè)單詞記號(hào)）

單詞屬值

標(biāo)識(shí)符

position

賦值算符(:=)

標(biāo)識(shí)符

initial

加算符(+)

標(biāo)識(shí)符

rate

乘算符(*)

整數(shù)常量

60

分號(hào)(；)

詞法分析概述

常用的單詞描述工具擴(kuò)展巴克斯范式（EBNF）

狀態(tài)轉(zhuǎn)換圖

正規(guī)表達(dá)式

有限狀態(tài)自動(dòng)機(jī)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)

實(shí)例:

某語(yǔ)言詞法分析程序的設(shè)計(jì)

單詞類別的

EBNF描述

詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)

實(shí)例:

某語(yǔ)言詞法分析程序的設(shè)計(jì)

詞法單位

詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)

實(shí)例:

某語(yǔ)言詞法分析程序的設(shè)計(jì)

詞法規(guī)則的狀態(tài)轉(zhuǎn)換圖詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)

技術(shù)個(gè)案

如何區(qū)分標(biāo)識(shí)符與保留字預(yù)設(shè)一個(gè)保留字表，通過查表來(lái)確定是否保留字

字符退還

在識(shí)別雙符號(hào)運(yùn)算符之類的單詞時(shí)，要注意到可能需要進(jìn)行字符退還例:在讀取字符‘<’后，若下一字符不是‘=’，則識(shí)別的單詞是小于號(hào)‘<’，但要退還這個(gè)非<字符，以保證下一次仍讀到那個(gè)非<字符

其他技術(shù)個(gè)案

詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)

……

詞法分析程序自動(dòng)構(gòu)造的典型過程

步驟一使用者用正規(guī)表達(dá)式作為詞法規(guī)則的形式描述，每一類詞法單元都對(duì)應(yīng)一個(gè)正規(guī)表達(dá)式，所有正規(guī)表達(dá)式以文本方式作為自動(dòng)構(gòu)造工具的輸入詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典型過程

步驟二自動(dòng)構(gòu)造工具將每一個(gè)正規(guī)表達(dá)式轉(zhuǎn)換成有限自動(dòng)機(jī)的形式，比如使用Thompson

構(gòu)造法將正規(guī)表達(dá)式轉(zhuǎn)換成-NFA

詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典型過程

步驟三(可選)增加一個(gè)新的開始狀態(tài)，從該狀態(tài)引一條-轉(zhuǎn)移邊到上述每一個(gè)-NFA的初態(tài)，得到一個(gè)新的-NFA詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典型過程

步驟四必要時(shí)自動(dòng)構(gòu)造工具會(huì)將這些-NFA

確定化，比如使用子集構(gòu)造法得到DFA詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典型過程

步驟五必要時(shí)，自動(dòng)構(gòu)造工具會(huì)將有限自動(dòng)機(jī)最小化，得到等價(jià)擁有狀態(tài)數(shù)目最少的DFA詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典行過程

步驟六若執(zhí)行過第3步，那么就模擬單個(gè)完整的自動(dòng)機(jī)；否則，自動(dòng)構(gòu)造工具按照一定的控制策略生成詞法分析程序中掃描程序的代碼，該掃描程序可以選擇對(duì)每一類詞法單元所對(duì)應(yīng)的有限自動(dòng)機(jī)依次模擬運(yùn)行，并從當(dāng)前輸入符號(hào)序列中識(shí)別下一個(gè)單詞，然后返回相應(yīng)的單詞記錄詞法分析程序的自動(dòng)構(gòu)造

詞法分析程序自動(dòng)構(gòu)造的典行過程

可選的正規(guī)表達(dá)式設(shè)計(jì)方法先設(shè)計(jì)自動(dòng)機(jī)

直接設(shè)計(jì)正規(guī)表達(dá)式有時(shí)比較困難

例如：假若想要為Java程序中所允許的注釋給

出正規(guī)表達(dá)式，這類注釋以”/*”開始，以”*/”

結(jié)束，在”/*”和”*/”之間，除了”*/”序列外，可

以出現(xiàn)任意字符。對(duì)此類注釋，構(gòu)造DFA比構(gòu)

造正規(guī)表達(dá)式更容易，所以可先構(gòu)造DFA，然

后再轉(zhuǎn)換為正規(guī)表達(dá)式。詞法分析程序的自動(dòng)構(gòu)造課后作業(yè)針對(duì)第7頁(yè)中EBNF描述的各單詞類別，設(shè)計(jì)相應(yīng)的正規(guī)表達(dá)式。（非書面作業(yè)）針對(duì)第18頁(yè)中所描述的“注釋”單詞類別，設(shè)計(jì)相應(yīng)的正規(guī)表達(dá)式。你可以先試著直接設(shè)計(jì)這個(gè)正規(guī)表達(dá)式，若覺得復(fù)雜，就采用第18頁(yè)所述的方法進(jìn)行設(shè)計(jì)。如果有興趣，還可以在第一